أشجار AVL - دليل دراسة شامل

📚 مقدمة عن أشجار AVL

ما هي شجرة AVL؟

شجرة AVL هي شجرة بحث ثنائية ذاتية التوازن سُميت على اسم مخترعيها أدلسون-فيلسكي ولانديس. تحافظ على هيكل متوازن من خلال ضمان أن ارتفاعيّ الفرعين لأي عقدة داخلية يختلفان بمقدار واحد على الأكثر.

الخاصية الأساسية: لكل عقدة داخلية v، يمكن أن يختلف ارتفاعا الفرعين بمقدار واحد على الأكثر.

رياضياً: |ارتفاع(اليسار) - ارتفاع(اليمين)| ≤ 1

لماذا أشجار AVL؟

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

🎯 خصائص أشجار AVL

معامل التوازن

معامل التوازن للعقدة يحسب كالتالي:

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

قيم معامل التوازن المقبولة: -1, 0, +1

+1: الشجرة الفرعية اليسرى أطول بمستوى واحد
0: الشجرتان الفرعيتان متساويتان في الارتفاع
-1: الشجرة الفرعية اليمنى أطول بمستوى واحد
+2 أو -2: ⚠️ الشجرة غير متوازنة! (تحتاج إلى دوران)

ارتفاع شجرة AVL

h < 2log(n) + 2

لذلك: h = O(log n)

مفهوم برهان مهم:
لنفرض n(h) = أقل عدد من العقد في شجرة AVL بارتفاع h
• n(1) = 1
• n(2) = 2
• n(h) = 1 + n(h-1) + n(h-2)

بما أن n(h-1) > n(h-2)، نحصل على n(h) > 2n(h-2)
باستقراء رياضي: n(h) > 2^(h/2-1)
بأخذ اللوغاريتم: h < 2log n(h) + 2

🔄 دورانات الشجرة

الدوران هو العملية الأساسية المستخدمة لاستعادة التوازن في شجرة AVL. هناك 4 أنواع من الدورانات تعتمد على هيكل عدم التوازن.

متى نستخدم الدورانات؟

عندما يصبح معامل التوازن +2 أو -2
بعد عمليات الإدراج أو الحذف
للحفاظ على خاصية AVL

1️⃣ دوران يمين مفرد (حالة LL)

متى: عدم توازن يسار-يسار (نفس الإشارة)

النمط: الشجرة الفرعية اليسرى أطول، وعدم التوازن في الشجرة الفرعية اليسرى للطفل الأيسر

z (غير متوازن)
↙
y
↙
x

⬇ دوران يمين

y
↙ ↘
x z

2️⃣ دوران يسار مفرد (حالة RR)

متى: عدم توازن يمين-يمين (نفس الإشارة)

النمط: الشجرة الفرعية اليمنى أطول، وعدم التوازن في الشجرة الفرعية اليمنى للطفل الأيمن

z (غير متوازن)
  ↘
  y
  ↘
  x

⬇ دوران يسار

  y
↙ ↘
z   x

3️⃣ دوران يسار-يمين (حالة LR)

متى: عدم توازن يسار-يمين (إشارات متعاكسة)

النمط: الشجرة الفرعية اليسرى أطول، لكن عدم التوازن في الشجرة الفرعية اليمنى للطفل الأيسر

z
↙
y
↘
x

⬇ يسار ثم يمين

x
↙ ↘
y z

4️⃣ دوران يمين-يسار (حالة RL)

متى: عدم توازن يمين-يسار (إشارات متعاكسة)

النمط: الشجرة الفرعية اليمنى أطول، لكن عدم التوازن في الشجرة الفرعية اليسرى للطفل الأيمن

z
↘
y
↙
x

⬇ يمين ثم يسار

x
↙ ↘
z y

💡 قاعدة سريعة:

نفس الإشارة (كلاهما يسار أو كلاهما يمين) → دوران مفرد
إشارات متعاكسة (يسار-يمين أو يمين-يسار) → دوران مزدوج

إعادة هيكلة ثلاثية العقد

نهج عام للتعامل مع جميع حالات الدوران:

ليكن (a, b, c) هو السرد التصاعدي للعقد x, y, z
نقوم بعمليات دوران لجعل b العقدة العلوية
تصبح a الطفل الأيسر، وتصبح c الطفل الأيمن
يتم توزيع الأشجار الفرعية T₀, T₁, T₂, T₃ بشكل مناسب

➕ الإدراج في أشجار AVL

خطوات الخوارزمية

إدراج كما في شجرة البحث الثنائية: ابحث عن الموضع الصحيح وأدخل العقدة الجديدة
تحديث الارتفاعات: اذهب للأعلى من العقدة المدرجة، وقم بتحديث الارتفاعات
فحص التوازن: في كل عقدة أصل، افحص معامل التوازن
تنفيذ الدوران: إذا كانت غير متوازنة (|معامل التوازن| = 2)، نفذ الدوران المناسب
الاستمرار للأعلى: استمر في الفحص حتى الوصول للجذر

📝 مثال: إدراج 54

افترض شجرة AVL بالعقد: 44, 17, 78, 32, 50, 88, 48, 62

بعد إدراج 54:

تصبح العقدة 62 غير متوازنة (معامل التوازن = -2)
النمط: يمين-يسار (حالة RL)
الحل: دوران يمين عند 62، ثم إعادة هيكلة
النتيجة: شجرة متوازنة مع 54 في الموضع الصحيح

فكرة أساسية: فقط دوران واحد مطلوب للإدراج! الدوران يصلح جميع حالات عدم التوازن الناتجة عن الإدراج.

تحليل التعقيد

التعقيد الزمني: O(log n)

البحث عن مكان الإدراج: O(log n)
تحديث الارتفاعات: O(log n)
دوران مفرد: O(1)
المجموع: O(log n)

➖ الحذف في أشجار AVL

خطوات الخوارزمية

حذف كما في شجرة البحث الثنائية: احذف العقدة باستخدام حذف شجرة البحث الثنائية القياسي
ابدأ من الأب: ابدأ من أب العقدة المحذوفة
تحديث الارتفاعات: أعد حساب الارتفاعات أثناء الصعود لأعلى
فحص التوازن: افحص معامل التوازن في كل عقدة
تنفيذ الدورانات: إذا كانت غير متوازنة، نفذ الدوران المناسب
الاستمرار حتى الجذر: يجب الفحص طوال الطريق حتى الجذر

⚠️ فرق حاسم عن الإدراج:
الحذف قد يتطلب عدة دورانات وأنت تصعد للجذر! كل دوران قد يخلق عدم توازن جديد أعلى الشجرة.

📝 مثال: حذف 32

من شجرة بالعقد: 44, 17, 62, 32, 50, 78, 48, 54, 88

احذف العقدة 32 (عقدة ورقية)
تصبح العقدة 17 غير متوازنة
نفذ دوران عند 17
افحص العقد الأصل حتى الجذر
نفذ دورانات إضافية إذا لزم الأمر

حالات حذف شجرة البحث الثنائية

الحالة 1: العقدة ليس لها أطفال (ورقة) → احذف ببساطة
الحالة 2: العقدة لديها طفل واحد → استبدل العقدة بطفلها
الحالة 3: العقدة لديها طفلان → استبدل بالخليفة أو السلف التصاعدي

تحليل التعقيد

التعقيد الزمني: O(log n)

البحث عن العقدة: O(log n)
حذف العقدة: O(1)
إعادة التوازن (عدة دورانات): O(log n)
المجموع: O(log n)

⚡ تحليل الأداء

العملية	شجرة AVL (متوسط)	شجرة AVL (أسوأ حالة)	شجرة بحث ثنائية (متوسط)	شجرة بحث ثنائية (أسوأ حالة)
بحث	O(log n)	O(log n)	O(log n)	O(n)
إدراج	O(log n)	O(log n)	O(log n)	O(n)
حذف	O(log n)	O(log n)	O(log n)	O(n)
اجتياز	O(n)	O(n)	O(n)	O(n)

التعقيد المكاني

O(n) - أشجار AVL تخزن n عقدة بالإضافة إلى معلومات الارتفاع في كل عقدة

💡 لماذا أشجار AVL أفضل:

قابلة للتنبؤ: لا توجد عمليات أسوأ حالة O(n)
متوازنة: تحافظ دائماً على ارتفاع لوغاريتمي
فعالة: جميع العمليات مضمونة O(log n)
موثوقة: الأداء لا يعتمد على ترتيب الإدراج

💻 مفاهيم تنفيذ رئيسية

هيكل العقدة

public class AVLNode {
    int key;
    int height;
    AVLNode left, right;
    
    public AVLNode(int key) {
        this.key = key;
        this.height = 1;  // العقدة الجديدة بارتفاع 1 في البداية
    }
}

دوال أساسية

1. حساب الارتفاع

protected int height(Position p) {
    return tree.getAux(p);  // مخزن كبيانات مساعدة
}

protected void recomputeHeight(Position p) {
    int h = 1 + Math.max(height(left(p)), height(right(p)));
    tree.setAux(p, h);
}

2. فحص معامل التوازن

protected boolean isBalanced(Position p) {
    return Math.abs(height(left(p)) - height(right(p))) <= 1;
}

3. اختيار الطفل الأطول

protected Position tallerChild(Position p) {
    if (height(left(p)) > height(right(p))) 
        return left(p);    // اليسار أطول
    if (height(left(p)) < height(right(p))) 
        return right(p);   // اليمين أطول
    // ارتفاع متساو: نطابق اتجاه الأصل
    if (p == left(parent(p))) 
        return left(p);    // نرجع الطفل المحاذي
    else 
        return right(p);
}

4. إعادة التوازن بعد الإدراج

protected void rebalanceInsert(Position p) {
    rebalance(p);  // فحص التوازن وإصلاحه إذا لزم
}

protected void rebalance(Position p) {
    int oldHeight, newHeight;
    do {
        oldHeight = height(p);
        if (!isBalanced(p)) {
            // تنفيذ إعادة هيكلة ثلاثية العقد
            p = restructure(tallerChild(tallerChild(p)));
            recomputeHeight(left(p));
            recomputeHeight(right(p));
        }
        recomputeHeight(p);
        newHeight = height(p);
        p = parent(p);
    } while (oldHeight != newHeight && p != null);
}

5. إعادة التوازن بعد الحذف

protected void rebalanceDelete(Position p) {
    if (!isRoot(p))
        rebalance(parent(p));  // يجب الفحص من الأصل صعوداً للجذر
}

📖 نصائح دراسة وأخطاء شائعة

✅ مفاهيم رئيسية لإتقانها

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

⚠️ أخطاء شائعة يجب تجنبها

نسيان تحديث الارتفاعات بعد الدورانات
التوقف عند أول دوران أثناء الحذف (يجب الوصول للجذر!)
اختيار دوران خاطئ - تذكر نفس الإشارة = مفرد، مختلفة = مزدوج
عدم الحفاظ على خاصية شجرة البحث الثنائية أثناء الدورانات
حساب معامل التوازن بشكل خاطئ (يسار - يمين، وليس يمين - يسار)

🎯 مسائل تدريبية

أدرج العقد 45, 70, 35, 3, 74, 25, 81, 4 في شجرة AVL فارغة. اعرض جميع الدورانات.
احذف العقدة 25 من الشجرة المنشئة أعلاه. اعرض جميع خطوات إعادة التوازن.
بإعطاء شجرة بارتفاع h، أثبت أن أقل عدد من العقد هو تقريباً Fibonacci(h+2).
قارن أشجار AVL بأشجار Red-Black - متى تستخدم كل منها؟

🔍 مرجع سريع

شجرة قرار الدوران:

هل العقدة غير متوازنة (|معامل التوازن| = 2)؟
├─ لا → تابع فحص الأصل
└─ نعم → أي شجرة فرعية أطول؟
    ├─ يسار (معامل التوازن = +2)
    │   ├─ الشجرة اليسرى للطفل الأيسر أطول → LL: دوران يمين مفرد
    │   └─ الشجرة اليمنى للطفل الأيسر أطول → LR: دوران مزدوج (يسار-يمين)
    └─ يمين (معامل التوازن = -2)
        ├─ الشجرة اليمنى للطفل الأيمن أطول → RR: دوران يسار مفرد
        └─ الشجرة اليسرى للطفل الأيمن أطول → RL: دوران مزدوج (يمين-يسار)

📋 ملخص

مزايا شجرة AVL

✅ أداء مضمون O(log n) للبحث، الإدراج، الحذف
✅ أكثر توازناً من أشجار Red-Black
✅ أداء بحث أفضل (مقارنات أقل)
✅ أداء قابل للتنبؤ بغض النظر عن ترتيب المدخلات

عيوب شجرة AVL

❌ دورانات أكثر أثناء الإدراج/الحذف مقارنة بأشجار Red-Black
❌ مساحة إضافية لتخزين الارتفاع في كل عقدة
❌ تنفيذ أكثر تعقيداً من شجرة بحث ثنائية بسيطة
❌ إدراج وحذف أبطأ قليلاً مقارنة بأشجار Red-Black

🎓 تذكر للاختبارات

ارتفاع شجرة AVL ذات n عقدة: h = O(log n)
نطاق معامل التوازن: -1, 0, +1
جميع العمليات: O(log n)
التعقيد المكاني: O(n)
الإدراج: دوران واحد كحد أقصى
الحذف: O(log n) دوران ممكن
زمن الدوران: O(1)