يمكن لشجرة البحث الثنائية العادية أن تتدهور إلى قائمة مرتبطة (عمليات O(n)) إذا وصلت المفاتيح بترتيب مرتب. أشجار البحث الثنائية ذاتية التوازن — مثل AVL والأشجار الحمراء-السوداء — تقوم تلقائياً بـ تدوير العقد بعد الإدراج/الحذف للحفاظ على الارتفاع ~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) تحافظ على ترتيب البحث الثنائي مع تقليل الارتفاع.
تدعم الأشجار المتوازنة الخرائط والمجموعات المرتبة في المكتبات القياسية (مثل Java TreeMap، C++ std::map تستخدم أشجار حمراء-سوداء)، مما يوفر تكرار مرتب بالإضافة إلى عمليات لوغاريتمية مضمونة.
إنها الإجابة عندما تحتاج إلى ترتيب شجرة البحث الثنائية و ضمان أداء قوي ضد المدخلات الخبيثة.