شجرة أدلسن فالسكي ولانديس

بدايةً، في علم الحاسوب، شجرة إي في إل هي شجرة بحث ثنائية متزنة، وهي أول بنية بيانات تم اختراعها. ونتناول فيما يلي مزيدًا من التفاصيل.
ومن ناحية أخرى، شجرة AVL سميت نسبة لمخترعَيها السوفيتيين، غيورغي ماكسيموفيتش أدلسن-فالسكي (Adelson-Velskii) ويفغيني لانديس (Landis). الذين نشراها في مقالهما سنة 1962 «خوارزمية لتنظيم المعلومات».
وفي السياق ذاته، في شجرة AVL، ارتفاع الأشجار الجزئية لأية عقدة تختلف بواحد على الأكثر.
وفي هذا الصدد، البحث، الإدخال، والحذف يتطلبون زمن (O(log n في كل من الحالات المتوسطة والأسوء، حيث أن n هو عدد العقد في شجرة قبل العملية. الإدخال والحذف قد يستلزم إعادة توازن الشجرة عن طريق دوران شجرة واحد أو أكثر.
من ناحية أخرى، أشجار أحمر-أسود هم أسرع بالإدخال والحذف.
وفي هذا السياق، عادة ما يتم مقارنة أشجار AVL مع أشجار أحمر-أسود لأنهما يدعمان نفس العمليات، ولأن أشجار أحمر-أسود يتطلبون زمن (O(log n في العمليات الأساسية. لأن أشجار AVL صارمون بالتوازن، هم أسرع من أشجار أحمر-أسود لتطبيقات المكثفة البحث.
علاوةً على ذلك، عامل التوازن لعقدة ما هو ارتفاع الشجرة الجزئية اليسرى ناقص ارتفاع الشجرة الفرعية اليمنى (أحيانا العكس). والعقدة مع عامل توازن 1، 0 أو -1 تعتبر متوازنة. عقدة مع عامل توازن غير ذلك تعتبر غير متوازنة وتتطلب إعادة توازن الشجرة. عامل التوازن إما أن يكون محفوظا في كل عقدة، أو يتم حسابه من ارتفاعات أشجاره الجزئية.
إدخال
وفي هذا الصدد، إذا كان معامل توازن L هو -1، نحتاج دوارنين. الدوران الأول هو دوران يساري مع L كالجذر. الدوران الثاني هو دوران يميني مع P كالجذر (حالة يسار-يمين).
من جانب آخر، إذا كان معامل توازن R هو +1، نحتاج دوارنين. الدوران الأول هو دوران يميني مع R كالجذر. الدوران الثاني هو دوران يساري مع P كالجذر (حالة يمين-يسار).
إضافةً إلى ذلك، بعد إدخال عقدة، لابد من التحقق من تمسك كل من أسلاف العقدة بقواعد AVL. لكل عقدة فحصت، إذا بقى عامل التوازن 1، 0 أو -1 إذن ليست هناك حاجة للدوران. من ناحية أخرى، إذا صار عامل التوازن ±2 إذن الشجرة الجزئية المبتدئة بهذه العقدة غير متوازنة. إذا تم الإدخال بشكل متسلسل، بعد كل إدخال، على الأكثر حالة واحدة من الحالات التالية يحب حلها لاستعادة قواعد AVL للشجرة كاملة.
حالة يمين-يمين وحالة يمين-يسار:
وفي السياق ذاته، إذا كان معامل توازن P هو +2 إذن يفوق ارتفاع الشجرة الجزئية اليسرى ارتفاع الشجرة الجزئية اليمنى، ويجب فحص معامل توازن الابن الأيسر (L). الدوران الأيمن مع P كالجذر ضروري.
حالة يسار-يسار وحالة يسار-يمين:
ومن ناحية أخرى، إذا كان معامل توازن R هو -1، نحتاج دوران يساري واحد (مع P كالجذر) (حالة يمين-يمين).
في هذا الإطار، إذا كان معامل توازن P هو -2 إذن يفوق ارتفاع الشجرة الجزئية اليمنى ارتفاع الشجرة الجزئية اليسرى، ويجب فحص معامل توازن الابن الأيمن (R). الدوران الأيسر مع P كالجذر ضروري.
وفي هذا الصدد، هنالك أربع حالات يجب التطرق لها، بحيث أن حالتين متماثلتان للاثنتين الأخرى ين. ليكن P جذر شجرة جزئية غير متوازنة، مع L الابن الأيسر وR الابن الأيمن لـ P.
علاوةً على ذلك، إذا كان معامل توازن L هو +1، نحتاج دوران يميني واحد (مع P كالجذر) (حالة يسار-يسار).
بحث
وفي السياق ذاته، إذا كان لكل عقدة سجلات أحجام شجرتها الجزئية (شاملا العقدة نفسها وأحفادها)، إذن يمكن استعادة العقدة بزمن (O(log n كذلك.
وفي هذا السياق، البحث في شجرة AVL يتم بالضبط مثل أية شجرة بحث ثنائية غير متوازنة. بسبب توازن ارتفاع الشجرة، يستغرق البحث زمن (O(log n، ولا يتم تعديل مبنى الشجرة في عملية البحث.
مقارنة مع بنى بيانات أخرى
- لشجرة بحجم :
- ارتفاع شجرة AVL أقل بدقة من:
- بحيث أن هو الرقم الذهبي.
في هذا الإطار، كلا من أشجار AVL وأشجار أحمر-أسود هم أشجار بحث ثنائية متوازنة ذاتيا، ولذلك هم متشابهون رياضيا. عمليتا إعادة التوازن الأشجار مختلفة، ولكن كلاهما يحدث في زمن (O(log n. الفرق الحقيقي بين الاثنتين هو تحديد الارتفاع.
ارتفاع شجرة أحمر-أسود هو على الأغلب
- انظر كذلك
- شجرة
- شجرة بحث ثنائية
- مراجع
وفي هذا الصدد، إن أشجار AVL أكثر صرامة بالتوازن من أشجار أحمر-أسود، مما يؤدي إلى إدخال وحذف أبطئ ولكن استرجاع أسرع.
حذف
من جانب آخر، وإلا، نبدلها بإما الأكبر في الشجرة الجزئية اليسرى (السابق inorder predecessor) أو الأصغر في الشجرة الجزئية اليمنى (اللاحق inorder successor)، ونزيل العقدة.
إذا كانت العقدة ورقة أو لها ابن واحد فقط، نزيلها.
عمليات
في هذا الإطار، العمليات الأساسية في شجرة AVL تشتمل على تنفيذ نفس الأعمال الممكن تنفيذها على شجرة بحث ثنائية غير متوازنة، ولكن تسبق التعديلات أو تليها عملية واحدة أو أكثر تسمى دوران شجرة، والتي تساعد على استعادة توازن ارتفاع الأشجار الجزئية.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟