تكرار السؤال: …
الإجابة المختصرة
تضمن شجرة BST أن الابن الأيسر أصغر من العقدة والأيمن أكبر، لكن إدخال عناصر مرتبة يحولها إلى خط مستقيم مائل O(N)، لذا تتدخل الأشجار المتوازنة عبر الدوران (Rotations) لضمان عمق O(log N).
الشرح
أشجار AVL تفرض توازناً صارماً جداً؛ حيث لا يزيد فارق الارتفاع بين أي شجرتين فرعيتين عن 1، مما يجعلها مثالية للبحث السريع المتكرر. أشجار Red-Black تستخدم توازناً أكثر تساهلاً يعتمد على قواعد تلوين العقد بالأحمر والأسود، مما يقلل عدد الدورات المطلوبة أثناء الإدخال والحذف، ولذلك تُستخدم كبنية افتراضية في مكتبات اللغات الكبرى مثل TreeMap في Java و std::map في C++.
مثال بالكود
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def height(node):
return 0 if node is None else 1 + max(height(node.left), height(node.right))
degenerate = None
for k in range(1, 8): # sorted input
degenerate = insert(degenerate, k)
print(height(degenerate)) # 7 → behaves like a linked list, O(n)
balanced = None
for k in [4, 2, 6, 1, 3, 5, 7]:
balanced = insert(balanced, k)
print(height(balanced)) # 3 → O(log n); AVL/Red-Black keep this via rotationsأخطاء شائعة
- الاعتقاد بأن BST تضمن دائماً O(log N) دون الحاجة لآليات توازن ذاتي.