BST ธรรมดาสามารถเสื่อมลงเป็นลิสต์ที่เชื่อมโยง (การดำเนินการ O(n)) ถ้าคีย์มาถึงในลำดับที่เรียงลำดับ BST ที่สมดุลตัวเอง — เช่น AVL และ ต้นไม้สีแดง-ดำ — หมุน โหนดอัตโนมัติหลังการแทรก/ลบเพื่อรักษาความสูง ~log n โดยรับประกันการดำเนินการ O(log n)
BST ธรรมดาสามารถเสื่อมลงเป็นลิสต์ที่เชื่อมโยง (การดำเนินการ O(n)) ถ้าคีย์มาถึงในลำดับที่เรียงลำดับ BST ที่สมดุลตัวเอง — เช่น AVL และ ต้นไม้สีแดง-ดำ — หมุน โหนดอัตโนมัติหลังการแทรก/ลบเพื่อรักษาความสูง ~log n โดยรับประกันการดำเนินการ O(log n)
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| ต้นไม้ AVL | ต้นไม้สีแดง-ดำ | |
|---|---|---|
| ความเข้มงวดของการสมดุล | เข้มงวด (สมดุลความสูง) | หลวม |
| การค้นหา | เร็วกว่า (สั้นกว่า) | ช้าลงเล็กน้อย |
| แทรก/ลบ | การหมุนมากขึ้น | การหมุนน้อยลง |
| ดีที่สุดสำหรับ | เวิร์กโหลดที่หนักในการอ่าน | เวิร์กโหลดที่หนักในการเขียน |
| การดำเนินการ | เวลา |
|---|---|
| ค้นหา | O(log n) |
| แทรก | O(log n) |
| ลบ | O(log n) |
ทั้งสองรักษาความสมดุลผ่าน การหมุน — การปรับปรุงใหม่ภายในท้องถิ่น O(1) ที่รักษาลำดับ BST ในขณะที่ลดความสูง
ต้นไม้ที่สมดุลสนับสนุนแผนที่ที่เรียงลำดับและชุดในไลบรารีมาตรฐาน (เช่น Java TreeMap C++ std::map ใช้ต้นไม้สีแดง-ดำ) ให้การวนซ้ำที่เรียงลำดับบวกกับการดำเนินการที่รับประกันลอการิทึม
พวกมันคือคำตอบเมื่อคุณต้องการการเรียงลำดับของ BST และ การรับประกันประสิทธิภาพที่ยากต่อการป้อนข้อมูลที่เกี่ยวข้อง
คลังคำถามสัมภาษณ์งาน IT พร้อมคำตอบโดยละเอียด — ตั้งแต่ระดับ Junior ถึง Senior
บริจาค