ما هي شجرة AVL؟ شرح مبسّط لأشجار البحث المتوازنة وكيف تعمل
شجرة AVL هي ببساطة شجرة بحث ثنائية (Binary Search Tree) تعيد توازن نفسها تلقائيًا بعد كل عملية إضافة أو حذف، بحيث لا يتجاوز الفرق في الارتفاع بين الفرع الأيسر والفرع الأيمن لأي عقدة القيمةَ 1. هذا الشرط الصارم هو ما يضمن أن تبقى عمليات البحث والإضافة والحذف بسرعة O(log n) مهما كان ترتيب البيانات الداخلة. الاسم مأخوذ من مبتكرَيها السوفييتيَّين أديلسون-فيلسكي ولانديس عام 1962، وكانت أول هيكل شجري متوازن ذاتيًا في التاريخ.
لكي تفهم قيمتها الحقيقية، عليك أن تفهم المشكلة التي حُلّت بها أولًا.
لماذا نحتاج شجرة AVL أصلًا؟
في شجرة البحث الثنائية العادية، ترتيب إدخال العناصر يحدد شكلها. إذا أدخلت أرقامًا مرتّبة تصاعديًا مثل 1، 2، 3، 4، 5، فلن تحصل على شجرة متفرّعة جميلة، بل على ما يشبه القائمة المترابطة (Linked List) المائلة إلى جهة واحدة. عندها يصبح ارتفاع الشجرة n بدل log n، ويتدهور زمن البحث من O(log n) إلى O(n) في أسوأ الحالات.
شجرة AVL تحلّ هذا بالضبط: هي تراقب توازنها بعد كل تعديل، وإذا اختلّ الميزان صحّحت نفسها فورًا عبر عملية تُسمى الدوران (Rotation). النتيجة شجرة تبقى «قصيرة وعريضة» دائمًا، أي ارتفاعها لوغاريتمي مضمون.
معامل التوازن: قلب الفكرة
كل عقدة في شجرة AVL تحمل قيمة تُسمى معامل التوازن (Balance Factor)، وهي حاصل طرح ارتفاع الفرع الأيمن من ارتفاع الفرع الأيسر:
معامل التوازن = ارتفاع الفرع الأيسر − ارتفاع الفرع الأيمن
الشجرة تُعتبر متوازنة طالما بقي هذا المعامل لكل عقدة ضمن القيم {-1، 0، 1}. بمجرد أن يصل إلى 2 أو -2 بعد عملية ما، نعرف أن العقدة اختلّ توازنها ويجب إجراء دوران لإصلاحها.
الدورانات الأربعة
الدوران هو إعادة ترتيب محلية لعدد قليل من العقد لاستعادة التوازن دون كسر خاصية شجرة البحث (اليسار أصغر، اليمين أكبر). هناك أربع حالات:
- حالة LL (يسار-يسار): الثقل مائل إلى اليسار عبر الابن الأيسر. الحل: دوران يميني واحد.
- حالة RR (يمين-يمين): الثقل مائل إلى اليمين عبر الابن الأيمن. الحل: دوران يساري واحد.
- حالة LR (يسار-يمين): الحل: دوران يساري على الابن ثم دوران يميني على الجَد (دوران مزدوج).
- حالة RL (يمين-يسار): الحل: دوران يميني على الابن ثم دوران يساري على الجَد (دوران مزدوج).
نصيحة عملية من التجربة: أكثر خطأ يقع فيه المبتدئون هو الخلط بين اتجاه الميلان واتجاه الدوران. تذكّر القاعدة البسيطة: نوع الحالة (LL، RR، LR، RL) يُقرأ من العقدة المختلّة نزولًا نحو العقدة المُضافة، لا العكس. ارسم الحالة على ورقة قبل كتابة الكود، فذلك يوفّر عليك ساعات من التنقيح.
كيف تعمل العمليات الثلاث؟
البحث: مطابق تمامًا للبحث في شجرة بحث ثنائية عادية. تبدأ من الجذر، وإذا كانت القيمة المطلوبة أصغر تذهب يسارًا، وإن كانت أكبر تذهب يمينًا. لا دورانات هنا لأن البحث لا يغيّر الشجرة. الزمن O(log n).
الإضافة: أدخِل العنصر كما في الشجرة العادية، ثم اصعد من العقدة الجديدة نحو الجذر محدّثًا معاملات التوازن، وعند أول عقدة يختلّ توازنها نفّذ الدوران المناسب. دوران واحد (بسيط أو مزدوج) يكفي دائمًا لإصلاح الإضافة.
الحذف: احذف العنصر كما في الشجرة العادية، ثم اصعد نحو الجذر مصحّحًا التوازن. الفرق المهم: الحذف قد يتطلب أكثر من دوران واحد صعودًا حتى الجذر، بعكس الإضافة.
AVL أم Red-Black؟ مقارنة عملية
كلاهما شجرة بحث متوازنة ذاتيًا، لكن لكل منهما مجال يتفوّق فيه:
| المعيار | شجرة AVL | شجرة Red-Black |
|---|---|---|
| صرامة التوازن | أعلى (فرق ارتفاع ≤ 1) | أقل صرامة |
| سرعة البحث | أسرع (شجرة أقصر) | جيدة لكن أبطأ قليلًا |
| سرعة الإضافة/الحذف | أبطأ (دورانات أكثر) | أسرع (دورانات أقل) |
| الاستخدام الأمثل | بحث كثيف، تعديل قليل | تعديل كثيف |
| أمثلة واقعية | قواعد بيانات للقراءة | خرائط std::map، نواة لينكس |
القاعدة العملية: إن كانت بياناتك تُقرأ كثيرًا وتُعدّل نادرًا، فـ AVL أفضل. أما إن كانت الإضافة والحذف متكررين، فـ Red-Black عادةً أكثر كفاءة رغم أنها أقل توازنًا.
متى تستخدم AVL ومتى تتجنبها؟
استخدمها حين تكون سرعة البحث أولوية قصوى والبيانات شبه ثابتة، مثل فهارس القواميس أو جداول البحث في الذاكرة. تجنّبها إن كان برنامجك يقوم بإضافات وحذوفات مكثّفة، إذ ستدفع ثمن الدورانات المتكررة دون فائدة تُذكر مقابل بدائل أخفّ.
الأسئلة الشائعة
هل شجرة AVL دائمًا أسرع من شجرة البحث الثنائية العادية؟ في البحث نعم، لأنها تضمن ارتفاعًا لوغاريتميًا. لكن في الإضافة والحذف قد تكون أبطأ قليلًا بسبب تكلفة الحفاظ على التوازن. الشجرة العادية أسرع فقط في حالة نادرة: عندما تكون البيانات عشوائية بما يكفي لتبقى متوازنة تلقائيًا.
كم دورانًا تحتاج عملية الإضافة الواحدة؟ دوران واحد فقط (بسيط أو مزدوج) كافٍ دائمًا لإعادة توازن الشجرة بعد أي إضافة. الحذف وحده هو الذي قد يحتاج عدة دورانات صعودًا نحو الجذر.
ما الفرق بين الدوران البسيط والمزدوج؟ البسيط دوران واحد يُستخدم في حالتَي LL وRR حين يكون الميلان مستقيمًا في اتجاه واحد. المزدوج هو دورانان متتاليان يُستخدمان في حالتَي LR وRL حين يكون الميلان «منكسرًا» بزاوية.
هل يمكن أن تحتوي شجرة AVL على قيم مكررة؟ تقليديًا لا، إذ تعتمد على ترتيب صارم. عند الحاجة لتخزين التكرارات يُضاف عادةً عدّاد داخل العقدة نفسها بدل إنشاء عقدة جديدة لكل قيمة مكررة.