الأشجار المتوازنة (Balanced Trees)

المشكلة: شجرة البحث الثنائية قد تنهار لقائمة

تعلّمت أن شجرة البحث الثنائية (BST) تعطي بحثًا بسرعة O(log n) — لكن هذا غير مضمون دائمًا. لو أدرجت عناصر مرتّبة سلفًا (1، 2، 3، 4، 5...)، الشجرة تصبح فعليًا قائمة مترابطة بشكل شجرة، والبحث يتدهور لـ O(n):

إدراج 1, 2, 3, 4, 5 بترتيب تصاعدي في BST عادية:

1
 \
  2
   \
    3
     \
      4
       \
        5
شجرة "منحرفة" بالكامل — لا فائدة من كونها شجرة أصلًا!

الحل: التوازن الذاتي (Self-Balancing)

الأشجار المتوازنة تعيد ترتيب نفسها تلقائيًا بعد كل إدراج/حذف للحفاظ على ارتفاع منخفض (تقريبًا log n دائمًا)، بغض النظر عن ترتيب الإدخال. أشهر نوعين: AVL وRed-Black Tree.

AVL Tree — التوازن الصارم

بعد كل إدراج، AVL تتحقّق: هل فرق الارتفاع بين الشجرة الفرعية اليسرى واليمنى لأي عقدة أكبر من 1؟ إذا نعم، تُجري دورانًا (Rotation) لإعادة التوازن فورًا.

حالة غير متوازنة (فرق ارتفاع = 2):        بعد دوران يمين:
      3                                       2
     /                                       / \
    2                    ←→                 1   3
   /
  1

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1  # ارتفاع العقدة، يُحدَّث بعد كل عملية

def get_height(node):
    return node.height if node else 0

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x  # الجذر الجديد لهذا الجزء من الشجرة

أربع حالات اختلال ممكنة، كل منها له دوران مناسب: يسار-يسار (دوران يمين)، يمين-يمين (دوران يسار)، يسار-يمين، يمين-يسار (دوران مزدوج).

Red-Black Tree — توازن أخف تكلفة

Red-Black Tree تحقّق توازنًا "تقريبيًا" (أضعف صرامة من AVL) عبر تلوين كل عقدة أحمر أو أسود مع قواعد بسيطة (الجذر أسود دائمًا، عقدة حمراء لا تملك أبناء حمراء، كل مسار من الجذر للأوراق يحتوي نفس عدد العقد السوداء). التوازن الأخف يعني عمليات إعادة توازن أقل تكرارًا — لذلك تُستخدم بمكتبات قياسية كثيرة (مثل TreeMap بجافا وmap/set بـ C++).

AVL مقابل Red-Black — أيهما تختار؟

لماذا لا تبني هذا يدويًا عادةً؟

بالتطبيقات الحقيقية، نادرًا ما تكتب AVL/Red-Black من الصفر — تستخدم البنى الجاهزة بلغتك (TreeMap/TreeSet بجافا، std::map/std::set بـ C++، SortedList بمكتبات Python الخارجية). المهم فهم لماذا هي أسرع من BST العادية بأسوأ الحالات — هذا ما يُسأل عنه بالمقابلات التقنية غالبًا.

جدول سريع

أخطاء شائعة

• الظن أن كل شجرة بحث ثنائية سرعتها O(log n) — هذا مضمون فقط بالأشجار المتوازنة، لا BST العادية.
• محاولة حفظ الدورانات الأربعة عن ظهر قلب بدل فهم لماذا التوازن مهم أصلًا — الفهم أهم من التفاصيل التنفيذية بمعظم المقابلات.

🎯 التالي: لماذا الخوارزميات؟ — رحلة بصرية.