أشجار AVL

من ويكي الهندسة المعلوماتية
اذهب إلى: تصفح، ابحث

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

معامل التوازن لعقدة: بالتعريف هو الفرق بين ارتفاع الشجرة الجزئية التي جذرها الإبن اليسار لهذه العقدة و ارتفاع الشجرة الجزئية التي جذرها الإبن اليمين لهذه العقدة.

عادة يخصص حقل ضمن الـ implementation لتخزين معامل توازن العقدة


AVL trees allow for faster searches for information by rotating the tree when one side becomes much longer than the other. AVL trees have 4 different rotations they can apply to maintain the necessary balance. For any possible imbalance, one of these rotations will rebalance the tree.

تسمح أشجار الـ AVL بتسريع عمليات البحث عن المعلومات من خلال إجراء دوران للشجرة عندما يصبح أحد طرفيها (فرعيها) أطول من الثاني .

لأشجار الـ ANVL أربعة أنواع من الدورانات تمكنها من المحافظة على التوازن الضروري .

من أجل أي اختلال للتوازن ، واحد من هذه الدورانات الأربع يعيد التوازن للشجرة .

الدوران Rotation

التعريف: نقل لبعض مكونات الشجرة من جهة إلى أخرى

الهدف: نحن نسعى دوما أن تكون الشجرة التي نتعامل معها أقرب ما يكون إلى متوازنة (لأن تعقيد العمليات على الشجرة المتوازنة أفضل)

و خلال الإضافة أو الحذف قد يختل توازن الشجرة , فنقوم بإجراء دوران أو أكثر لأعادة التوازن للشجرة من جديد كلفة الدوران: O(1) لأننا نقوم فقط بتغير مؤشرات

أنواع الدوران

الدوران إلى اليمين RR

Rr rotation.jpg

وهو دوران بسيط

  • P أصبحت root
  • q>p (لأنه كان p ابن يسار لـ q )إذا q يصبح ابن يميني لـ p
  • p>q & q<w)) إذا w>q إذا w يصبح ابن يميني لـ q
  • (p<v & q>v) إذا v ابن يساري لـ q
Procedure RR (var T: PTree)
        Aux: =T^.L
       T^.L:=aux^.R      aux^.R:=T


الدوران إلى اليسار LR

Lr rotation.jpg

وهو دوران بسيط

  • q أصبحت root
  • q

    q إذا w يصبح ابن يميني لـ q

  • (q>v & p<v) إذا v ابن يمين لـ p
Procedure LR (var T: PTree)
        Aux: =T^.R
       T^.R:=aux^.L      aux^.L:=T
        T: =aux

الدوران المركب يسار ثم يمين LRR

LRR rotation.jpg

الدوران المركب يمين ثم يسار RLR

Rlr rotation.jpg

ملاحظتين :

  • عندما نقوم بدوران بسيط نهتم بعقدتين
  • عندما نقوم بدوران مركب نهتم بثلاث عقد,ويعود معامل التوازن لهذه العقد يساوي الصفر
  • صـ 107 من كتاب الخوارزميات 2 يوجد خطأ , والصواب أن الإجراء المكتوب هو إجراء الـ insert و ليس search (كما هو مكتوب)
  • صـ 91 , السطر 9 (أول سطر من المثال ) الخطأ: مثال الشجرة كاملة و الصواب تامة

أشجار AvL

إن شرط الشجرة المتوازنة صعب التحقيق (معامل توازن جيع العقد معدوم) ولتيسير الأمور وضعت أشجار الـAVL و هي أشجار بحث ثنائية يكون معامل توازن كل عقدة فيها أصغر تماما من 2 أي يكون إما 0 أو 1 أو -1 .

تؤمن أشجار الـ AVL سرعة أكبر في أداء العمليات على شجرة البحث الثنائي,(تذكر دوما أن height = O(log n),)

إعادة التوازن إلى شجرة AVL

375px-AVL Tree Rebalancing.svg.png

بعد إجراء عملية حذف أو إضافة,فد يختل توازن الشجرة (يكون معامل التوازن أكبر من+1 أو أصغر من -1).

بعد أن نحذف أو نضيف عنصر نعدل في قيم معاملات التوازن لجميع العقد الأسلاف للعقدة التي أضيفت, بمعنى نعود للطريق (الغصن) الذي سلكناه و نعدل قيم معاملات التوازن إن كانت هذه العملية تؤدي إلى تغير بقيم معاملات التوازن, ربما لا نحتاج إلى تعديل قيم معاملات التوازن عند جميع الأسلاف من أجل أي عقدة من العقد الأسلاف .

لم يختل توازن العقدة : لا نفعل شيئاً .

رغم إضافة العنصر على الشجرة كما في الأعلى فإن الشجرة مازالت متوازنة و معاملات التوازن لعقد الطريق الذي سرنا عليه لا تزال ضمن المجال [-1,0,+1] ,لا حاجة لدورانات .

و إلا: اختل توازن عقدة ما :(أصبح 2±) يجب أن نقوم بدوران, هذا الدوران يكون عند أولاد العقدة التي اختل التوازن عندها.

ملاحظة: غالبا في الإمتحان يأتي سؤال الــ avl رسم الشجرة عند إضافة/حذف عنصر .

مثال :

أعطت المهندسة مثال طويل عريض عن الإضافة و الحذف من شجرة AVl ,هناك ما يشبهه تجدونه صـ 99 من كتاب الخوارزميات 2 .

نصيحة , قم بتحضير كأس من الشاي واجلس وتابع معنا ( تابع العمود اليساري ثم اليميني من كل صفحة).

مثال خارجي عن عمليات الإضافة منقول من النت للفائدة قم بإضافة العناصر التالية إلى شجرة AVL


مثال غير محلول (السؤال الأول من امتحان العملي 2009)

حذف عنصر من شجرة AVL :

تذكرة سريعة بالفكرة العامة لحذف عنصر من شجرة بحث ثنائية :

  1. بحث عن العنصر
  2. عندما نجده :
  • إن كان ورقة: نحذفه مباشرةً.
  • إن كان له ولد وحيد: نجعل الجد يؤشر على الحفيد + نحذف الأب .
  • وإلا نبحث عن أكبر عنصر في الشجرة الجزئية اليسارية وليكن M ثم نقوم بنسخ قيمته للخانة المطلوب حذفها ثم نستدعي عوديا إجرائية الحذف من أجل حذف العنصر M .

خطوات عملنا في إجرائية الحذف من AVL ستكون كالتالي :

بعدما بحثنا عن العنصر و وجدناه و قمنا بحذفه عوديا (وفق الطريقة التي شرحناها في الأعلى)...

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

نناقش قيم معاملات التوازن للعقد الموجودة على الطريق الذي سلكناه.

العقدة التي يختل عندها التوازن (أي إذا حصل تغير في ارتفاع الشجرة الجزئية) عندها نجري لها إصلاح, نناقش قيمة معامل التوازن عند العقدةnode التي جرت عندها الإضافة, و من ثم نجري الدوران المناسب إن لزم الأمر .



الإضافة إلى أشجار AVL

تتم الإضافة في أشجار الAVL عند الأوراق، حيث نتتبع مسار البحث حتى نصل إلى nil فنضيفه، ثم نعود بشكل عودي مروراً على عقد المسار وعند كل عقدة نفحص إن كان شرط التوازن محققاً أم لا، فإذا اختل الشرط نجري الدوران المطلوب.

عند إضافة عقدة في شجرة شجرة جزئية يسارية ل v نميز ثلاث حالات :

  1. إن كانت العقدة v ذات معامل توازن سالب (ارتفاع الشجرة الجزئية اليمنى أكبر من ارتفاع اليسرى) وتمت الإضافة في اليسرى، يزداد الارتفاع، وبالتالي يزداد معامل التوازن بمقدار 1
  2. إذا كانت العقدة ذات معامل معدوم وازداد ارتفاع الشجرة الجزئية اليسرى (بعد الإضافة إليها) يصبح معاملها ،1 وتبقى متوازنة ولكن يزداد الارتفاع.
  3. إذا كانت العقدة ذات معامل موجب (ارتفاع الشجرة الجزئية اليسرى أكبر من ارتفاع اليمنى) وازداد ارتفاع اليسرى، تصبح الشجرة التي رأسها هذه العقدة غير متوازنة ويجب تعديلها بالدوران حتى تصبح متوازنة.

فبالنسبة لإعادة التوازن:

  • في الحالتين (1-3) ينتهي العمل:
    • ففي الحالة الأولى: نضمن أن الشجرة التي رأسها v متوازنة وأن ارتفاع هذه الشجرة لم يتغير! (تغير ارتفاع يسارها فأصبح مساوياً ليمينها)
    • أما في الحالة الثالثة، فبعد أن يتم إصلاح الخلل، يصبح معامل توازن الجذر الجديد الجديد للشجرة "التي كان جذرها V" معدوماً، كما أن ارتفاع الشجرة يبقى على حاله و ينتهي العمل.
  • أما في الحالة الثانية فصحيح أن العقدة V بقيت متوازنة ولكن ارتفاع الشجرة التي رأسها V قد ازداد وبالتالي لم ينته العمل، و يجب فحص العقد السابقة لV في مسار البحث لأنها قد تختل بهذ الزيادة.
ومن هذه المناقشة نجد أن الشكل العام للخوارزمية الإضافة للشجرة المتوازنة كما يلي ..