ปัญหาของ BST ทั่วไป
Binary Search Tree (BST) มีค่าน้อยกว่าอยู่ซ้าย ค่ามากกว่าอยู่ขวา ความซับซ้อนเฉลี่ยในการค้นหา O(log n) ขึ้นอยู่กับความสูงของต้นไม้ แต่ต้นไม้อาจกลายเป็น Skewed (เอียง)
ต้นไม้แบบนี้เหมือน Linked List การค้นหาใช้เวลา O(n) ไม่มีประสิทธิภาพ
การแก้ไข: Height-Balanced Tree
สร้างต้นไม้ที่สมดุลทางความสูง (Height Balanced) บังคับให้แต่ละด้านของโหนดมี Subtree ที่ความสูงใกล้เคียงกัน
เทคนิคการสมดุล
- AVL Tree
- Red-Black Tree
ตัวอย่างต้นไม้สมดุล
