تم اختراع شجرة AVL بواسطة GM Adelson - Velsky وEM Landis في عام 1962. وقد سُميت الشجرة AVL تكريمًا لمخترعيها.

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

يقال أن الشجرة متوازنة إذا كان عامل التوازن لكل عقدة يتراوح بين -1 إلى 1، وإلا فإن الشجرة ستكون غير متوازنة وتحتاج إلى التوازن.

عامل التوازن (ك) = الارتفاع (يسار(ك)) - الارتفاع (يمين(ك))

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

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

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

وترد شجرة AVL في الشكل التالي. يمكننا أن نرى أن عامل التوازن المرتبط بكل عقدة يقع بين -1 و+1. ولذلك فهو مثال على شجرة AVL.

تعقيد

العمليات على شجرة AVL

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

لماذا شجرة AVL؟

تتحكم شجرة AVL في ارتفاع شجرة البحث الثنائية من خلال عدم السماح لها بالانحراف. الوقت المستغرق لجميع العمليات في شجرة بحث ثنائية بارتفاع h هو أوه) . ومع ذلك، فمن الممكن أن يمتد إلى على) إذا أصبح BST منحرفًا (أي أسوأ الحالات). ومن خلال تحديد هذا الارتفاع بـ log n، تفرض شجرة AVL حدًا أعلى على كل عملية يا(سجل ن) حيث n هو عدد العقد.

دورات AVL

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

1. دوران L L: العقدة المدرجة في الشجرة الفرعية اليسرى للشجرة الفرعية اليسرى لـ A
2. دوران R R: العقدة المدرجة في الشجرة الفرعية اليمنى للشجرة الفرعية اليمنى لـ A
3. دوران L R: العقدة المدرجة في الشجرة الفرعية اليمنى من الشجرة الفرعية اليسرى من A
4. دوران R L: العقدة المدرجة في الشجرة الفرعية اليسرى من الشجرة الفرعية اليمنى من A

حيث العقدة A هي العقدة التي يكون عامل توازنها غير -1، 0، 1.

أول دورتين LL و RR عبارة عن دورات فردية والدوراتان التاليتان LR و RL عبارة عن دورات مزدوجة. لكي تكون الشجرة غير متوازنة، يجب أن يكون الحد الأدنى للارتفاع 2 على الأقل، دعونا نفهم كل دورة

1. دوران RR

عندما يصبح BST غير متوازن، بسبب إدراج عقدة في الشجرة الفرعية اليمنى للشجرة الفرعية اليمنى لـ A، فإننا نقوم بإجراء دوران RR، دوران RR هو دوران عكس اتجاه عقارب الساعة، والذي يتم تطبيقه على الحافة أسفل العقدة ذات عامل التوازن -2

في المثال أعلاه، العقدة A لها عامل توازن -2 لأنه تم إدراج العقدة C في الشجرة الفرعية اليمنى للشجرة الفرعية اليمنى. نقوم بإجراء دوران RR على الحافة الموجودة أسفل A.

2. دوران ليرة لبنانية

عندما يصبح BST غير متوازن، بسبب إدراج عقدة في الشجرة الفرعية اليسرى للشجرة الفرعية اليسرى لـ C، فإننا نقوم بإجراء دوران LL، دوران LL هو دوران في اتجاه عقارب الساعة، والذي يتم تطبيقه على الحافة أسفل العقدة التي لها عامل توازن 2.

في المثال أعلاه، تحتوي العقدة C على عامل توازن 2 لأنه تم إدراج العقدة A في الشجرة الفرعية اليسرى للشجرة الفرعية اليسرى لـ C. نقوم بإجراء دوران LL على الحافة الموجودة أسفل A.

3. دوران LR

تعتبر الدورات المزدوجة أصعب قليلاً من الدورة الفردية التي سبق أن أوضحناها أعلاه. دوران LR = دوران RR + دوران LL، أي يتم تنفيذ دوران RR الأول على الشجرة الفرعية ثم يتم تنفيذ دوران LL على الشجرة الكاملة، ونعني بالشجرة الكاملة العقدة الأولى من مسار العقدة المدرجة التي يكون عامل توازنها مختلفًا عن -1 أو 0 أو 1.

دعونا نفهم كل خطوة بوضوح شديد:

ولاية	فعل
	تم إدراج العقدة B في الشجرة الفرعية اليمنى من A، الشجرة الفرعية اليسرى من C، والتي أصبحت C بسببها عقدة غير متوازنة ذات عامل توازن 2. هذه الحالة هي دوران L R حيث: العقدة المدرجة في الشجرة الفرعية اليمنى من الشجرة الفرعية اليسرى من ج
	نظرًا لأن دوران LR = دوران RR + LL، وبالتالي يتم تنفيذ RR (عكس اتجاه عقارب الساعة) على الشجرة الفرعية المتجذرة عند A أولاً. عن طريق القيام بتدوير RR، عقدة أ ، أصبحت الشجرة الفرعية اليسرى لـ ب .
	بعد إجراء دوران RR، لا تزال العقدة C غير متوازنة، أي أن لديها عامل توازن 2، حيث أن العقدة المدرجة A موجودة على يسار يسار ج
	الآن نقوم بإجراء دوران LL في اتجاه عقارب الساعة على الشجرة الكاملة، أي على العقدة C.node ج أصبحت الآن الشجرة الفرعية اليمنى للعقدة B، وA هي الشجرة الفرعية اليسرى للعقدة B
	أصبح عامل التوازن لكل عقدة الآن إما -1 أو 0 أو 1، أي أن BST متوازن الآن.

4. دوران RL

كما تمت مناقشته سابقًا، فإن الدوران المزدوج أصعب قليلاً من الدوران الفردي الذي سبق أن أوضحناه أعلاه. دوران R L = دوران LL + دوران RR، أي يتم تنفيذ دوران LL الأول على الشجرة الفرعية ثم يتم تنفيذ دوران RR على الشجرة الكاملة، ونعني بالشجرة الكاملة العقدة الأولى من مسار العقدة المدرجة التي يكون عامل توازنها مختلفًا عن -1 أو 0 أو 1.

ولاية	فعل
	الأنود ب تم إدراجه في الشجرة الفرعية اليسرى لـ ج الشجرة الفرعية الصحيحة ل أ ، والتي بسببها أصبحت A عقدة غير متوازنة ذات عامل توازن - 2. هذه الحالة هي دوران RL حيث: العقدة المدرجة في الشجرة الفرعية اليسرى من الشجرة الفرعية اليمنى من A
	بما أن دوران RL = دوران LL + دوران RR، وبالتالي، LL (في اتجاه عقارب الساعة) على الشجرة الفرعية المتجذرة عند ج يتم تنفيذه أولا. عن طريق القيام بتدوير RR، عقدة ج أصبحت الشجرة الفرعية الصحيحة لـ ب .
	بعد إجراء دوران LL، عقدة أ لا تزال غير متوازنة، أي أن لها عامل توازن -2، وذلك بسبب الشجرة الفرعية اليمنى لعقدة الشجرة الفرعية اليمنى A.
	الآن نقوم بإجراء دوران RR (دوران عكس اتجاه عقارب الساعة) على الشجرة الكاملة، أي على العقدة A. العقدة ج أصبحت الآن الشجرة الفرعية اليمنى للعقدة B، وأصبحت العقدة A هي الشجرة الفرعية اليسرى للعقدة B.
	أصبح عامل التوازن لكل عقدة الآن إما -1 أو 0 أو 1، أي أن BST متوازن الآن.

س: أنشئ شجرة AVL تحتوي على العناصر التالية

ح، أنا، ي، ب، أ، ه، ج، و، د، ز، ك، ل

1. أدخل H، I، J

عند إدخال العناصر المذكورة أعلاه، خاصة في حالة H، يصبح BST غير متوازن حيث أن عامل التوازن لـ H هو -2. نظرًا لأن BST منحرف إلى اليمين، فسوف نقوم بإجراء دوران RR على العقدة H.

شجرة التوازن الناتجة هي:

2. أدخل ب، أ

رقم عشوائي في جافا

عند إدخال العناصر المذكورة أعلاه، خاصة في حالة A، يصبح BST غير متوازن لأن عامل التوازن لـ H وI هو 2، فإننا نعتبر العقدة الأولى من آخر عقدة مدرجة، أي H. نظرًا لأن BST من H منحرفة إلى اليسار، سنقوم بإجراء دوران LL على العقدة H.

شجرة التوازن الناتجة هي:

3. أدخل E

عند إدخال E، يصبح BST غير متوازن لأن عامل التوازن لـ I هو 2، لأنه إذا انتقلنا من E إلى I نجد أنه تم إدراجه في الشجرة الفرعية اليسرى من الشجرة الفرعية اليمنى لـ I، فسوف نقوم بإجراء دوران LR على العقدة I. LR = دوران RR + LL

3 أ) نقوم أولاً بإجراء دوران RR على العقدة B

الشجرة الناتجة بعد دوران RR هي:

3 ب) نقوم أولاً بإجراء دوران LL على العقدة I

الشجرة المتوازنة الناتجة بعد دوران LL هي:

4. أدخل C، F، D

عند إدخال C وF وD، يصبح BST غير متوازن لأن عامل التوازن لـ B وH هو -2، لأنه إذا انتقلنا من D إلى B نجد أنه تم إدراجه في الشجرة الفرعية اليمنى من الشجرة الفرعية اليسرى لـ B، فسنقوم بتنفيذ دوران RL على العقدة I. RL = دوران LL + RR.

4 أ) نقوم أولاً بإجراء دوران LL على العقدة E

الشجرة الناتجة بعد دوران LL هي:

4 ب) نقوم بعد ذلك بإجراء دوران RR على العقدة B

الشجرة المتوازنة الناتجة بعد دوران RR هي:

5. أدخل G

عند إدخال G، يصبح BST غير متوازن لأن عامل التوازن لـ H هو 2، لأنه إذا انتقلنا من G إلى H، نجد أنه تم إدراجه في الشجرة الفرعية اليسرى للشجرة الفرعية اليمنى لـ H، سنقوم بإجراء دوران LR على العقدة I. LR = دوران RR + LL.

5 أ) نقوم أولاً بإجراء دوران RR على العقدة C

الشجرة الناتجة بعد دوران RR هي:

5 ب) نقوم بعد ذلك بإجراء دوران LL على العقدة H

الشجرة المتوازنة الناتجة بعد دوران LL هي:

6. أدخل ك

عند إدخال K، يصبح BST غير متوازن لأن عامل التوازن I هو -2. نظرًا لأن BST منحرف إلى اليمين من I إلى K، فإننا سنقوم بإجراء دوران RR على العقدة I.

الشجرة المتوازنة الناتجة بعد دوران RR هي:

7. أدخل L

عند إدخال شجرة L، تظل متوازنة حيث أن عامل التوازن لكل عقدة هو الآن إما -1، 0، +1. ومن ثم فإن الشجرة هي شجرة AVL متوازنة