شجرة AVL في بايثون - فهم التوازن والتدوير لبيانات أسرع

🌳 شجرة AVL: الحل الذكي لمشكلة عدم التوازن في الأشجار!

مرحباً بك! في الدرس السابق، تعلمنا عن شجرة البحث الثنائية (BST) وكيف أن أداءها الرائع (بحث، إدراج، حذف في وقت O(log n)) يعتمد كلياً على كونها متوازنة. لكن ماذا لو أدرجنا بيانات مرتبة (مثل 1، 2، 3، 4، 5)؟ ستتحول الشجرة إلى قائمة مرتبة! ويصبح أداؤها O(n) ⚠️.

هنا يأتي دور شجرة AVL، وهي أول بنية بيانات من نوع شجرة بحث ثنائية ذاتية التوازن تم اختراعها. سميت على اسم مخترعيها (Adelson-Velsky and Landis). فكرتها العبقرية بسيطة: تراقب الشجرة توازنها بعد كل عملية إدراج أو حذف، وتصحح نفسها تلقائياً باستخدام عمليات تسمى التدوير، لتبقى أداء عمليات البحث سريعاً دائماً! 🚀

⚖️ المفتاح السحري: عامل التوازن (Balance Factor)

لكي تفهم كيف تعرف الشجرة أنها غير متوازنة، عليك أولاً فهم مفهوم عامل التوازن.

تعريف عامل التوازن لأي عقدة:

عامل التوازن = ارتفاع الشجرة الفرعية اليسرى - ارتفاع الشجرة الفرعية اليمنى

حيث الارتفاع هو طول أطول مسار من تلك العقدة إلى أبعد ورقة (عقدة ليس لها أبناء).

قاعدة شجرة AVL الأساسية:

عامل التوازن لأي عقدة في الشجرة يجب أن يكون أحد هذه القيم: -1، 0، 1.

إذا كان عامل التوازن لعقدة ما هو 2 أو -2 أو أي قيمة خارج النطاق [-1, 0, 1]، فهذا يعني أن الشجرة غير متوازنة عند هذه العقدة، ويجب علينا إعادة توازنها.

# تعريف عقدة شجرة AVL (امتداد للعقدة العادية في BST)
class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None    # الابن الأيسر
        self.right = None   # الابن الأيمن
        self.height = 1     # ارتفاع الشجرة الجذرية لهذه العقدة (مهم جداً!)

# دالة مساعدة لحساب ارتفاع عقدة (تتعامل مع العقد الفارغة بذكاء)
def get_height(node):
    if not node: # إذا كانت العقدة فارغة (None)
        return 0
    return node.height

# دالة مساعدة لحساب عامل التوازن لعقدة
def get_balance_factor(node):
    if not node:
        return 0
    # عامل التوازن = ارتفاع اليسار - ارتفاع اليمين
    return get_height(node.left) - get_height(node.right)

🔄 كيف نصلح عدم التوازن؟ عمليات التدوير (Rotations)

عندما نكتشف أن عقدة ما أصبح عامل توازنها خارج النطاق المسموح، نحدد نوع الخلل ثم نطبق عملية تدوير مناسبة لإعادة التوازن. هناك 4 حالات أساسية:

1. التدوير الأيسر الأيسر (Left Left Case - LL) ➡️

الموقف: العقدة غير المتوازنة (A) لديها ابن أيسر (B)، وB لديها ابن أيسر (C) أو يكون عامل توازن B موجب. الحل: تدوير لليمين حول العقدة A.

2. التدوير الأيمن الأيمن (Right Right Case - RR) ⬅️

الموقف: العقدة غير المتوازنة (A) لديها ابن أيمن (B)، وB لديها ابن أيمن (C) أو يكون عامل توازن B سالب. الحل: تدوير لليسار حول العقدة A.

3. التدوير الأيسر الأيمن (Left Right Case - LR) ↪️

الموقف: العقدة غير المتوازنة (A) لديها ابن أيسر (B)، ولكن B لديها ابن أيمن (C) هو السبب. الحل: تدوير لليسار حول B أولاً (لتحويل الحالة إلى LL)، ثم تدوير لليمين حول A.

4. التدوير الأيمن الأيسر (Right Left Case - RL) ↩️

الموقف: العقدة غير المتوازنة (A) لديها ابن أيمن (B)، ولكن B لديها ابن أيسر (C) هو السبب. الحل: تدوير لليمين حول B أولاً (لتحويل الحالة إلى RR)، ثم تدوير لليسار حول A.

# دالة لتنفيذ التدوير البسيط لليمين حول العقدة 'z' (لمعالجة حالة LL)
def rotate_right(z):
    y = z.left      # الابن الأيسر لـ z يصبح y
    T3 = y.right    # حفظ الشجرة الفرعية اليمنى لـ y

    # تنفيذ التدوير
    y.right = z     # تصبح z الابن الأيمن لـ y
    z.left = T3     # تصبح T3 الابن الأيسر لـ z

    # تحديث ارتفاعات العقد المتأثرة (z ثم y)
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    # العقدة الجديدة التي أصبحت في مكان z (وهي y) تُرجع
    return y

# دالة لتنفيذ التدوير البسيط لليسار حول العقدة 'z' (لمعالجة حالة RR)
def rotate_left(z):
    y = z.right     # الابن الأيمن لـ z يصبح y
    T2 = y.left     # حفظ الشجرة الفرعية اليسرى لـ y

    # تنفيذ التدوير
    y.left = z      # تصبح z الابن الأيسر لـ y
    z.right = T2    # تصبح T2 الابن الأيمن لـ z

    # تحديث ارتفاعات العقد المتأثرة
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    # العقدة الجديدة التي أصبحت في مكان z (وهي y) تُرجع
    return y

🧩 تجميع كل شيء: خوارزمية الإدراج في شجرة AVL

عملية الإدراج تشبه الإدراج في شجرة البحث الثنائية العادية، ولكن بعد الإدراج، نرجع لأعلى الشجرة (من العقدة المدرجة حتى الجذر) نحدّث الارتفاعات و نتحقق من عامل التوازن ونطبق التدوير المناسب إذا لزم الأمر.

# الدالة الرئيسية لإدراج مفتاح جديد في شجرة AVL
def insert_avl(root, key):
    # 1. تنفيذ الإدراج العادي كما في BST
    if not root:
        return AVLNode(key) # إنشاء عقدة جديدة إذا كان الموضع فارغاً
    elif key < root.key:
        root.left = insert_avl(root.left, key) # اذهب لليسار
    else: # key >= root.key
        root.right = insert_avl(root.right, key) # اذهب لليمين

    # 2. تحديث ارتفاع العقدة الحالية (root)
    root.height = 1 + max(get_height(root.left), get_height(root.right))

    # 3. الحصول على عامل التوازن لهذه العقدة للتحقق من عدم التوازن
    balance = get_balance_factor(root)

    # 4. تحديد حالة عدم التوازن وتطبيق التدوير المناسب

    # الحالة Left Left (LL)
    if balance > 1 and key < root.left.key:
        return rotate_right(root)

    # الحالة Right Right (RR)
    if balance < -1 and key > root.right.key:
        return rotate_left(root)

    # الحالة Left Right (LR)
    if balance > 1 and key > root.left.key:
        root.left = rotate_left(root.left) # حولها إلى حالة LL
        return rotate_right(root)

    # الحالة Right Left (RL)
    if balance < -1 and key < root.right.key:
        root.right = rotate_right(root.right) # حولها إلى حالة RR
        return rotate_left(root)

    # إذا كانت العقدة متوازنة، أرجع العقدة نفسها بدون تغيير
    return root

🔍 البحث في شجرة AVL

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

# دالة البحث في شجرة AVL (مطابقة لبحث BST تماماً)
def search_avl(root, key):
    # إذا كانت الجذر فارغاً أو المفتاح موجود في الجذر
    if not root or root.key == key:
        return root

    # إذا كان المفتاح أصغر من مفتاح الجذر، ابحث في الشجرة اليسرى
    if key < root.key:
        return search_avl(root.left, key)

    # وإلا فإن المفتاح أكبر، فابحث في الشجرة اليمنى
    return search_avl(root.right, key)

📊 ملخص: لماذا شجرة AVL رائعة؟

• ضمان الأداء: تضمن أن عمليات البحث والإدراج والحذف ستكون في وقت O(log n) حتى في أسوأ سيناريوهات إدخال البيانات.
• التوازن الصارم: تحافظ على فرق ارتفاع لا يزيد عن 1 بين الشجرتين الفرعيتين لأي عقدة.
• مناسبة للتطبيقات التي: يكون فيها البحث متكرراً أكثر بكثير من عمليات التحديث (الإدراج/الحذف)، لأن عمليات إعادة التوازن لها تكلفة إضافية.