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

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

لنفترض أن A هي العقدة الحرجة وB هي العقدة الجذرية للشجرة الفرعية اليسرى. إذا تم حذف العقدة X، الموجودة في الشجرة الفرعية اليمنى لـ A، فيمكن أن يكون هناك ثلاث حالات مختلفة:

دوران R0 (العقدة B لها عامل توازن 0)

إذا كانت العقدة B تحتوي على عامل توازن 0، واضطرب عامل التوازن للعقدة A عند حذف العقدة X، فسيتم إعادة توازن الشجرة عن طريق تدوير الشجرة باستخدام تدوير R0.

يتم نقل العقدة الحرجة A إلى يمينها وتصبح العقدة B جذر الشجرة مع T1 كشجرة فرعية يسرى. تصبح الشجرتان الفرعيتان T2 وT3 الشجرة الفرعية اليمنى واليسرى للعقدة A. تظهر الصورة التالية العملية المتضمنة في تدوير R0.

مثال:

احذف العقدة 30 من شجرة AVL الموضحة في الصورة التالية.

حل

في هذه الحالة، العقدة B لها عامل توازن 0، وبالتالي سيتم تدوير الشجرة باستخدام دوران R0 كما هو موضح في الصورة التالية. تصبح العقدة B(10) هي الجذر، بينما يتم نقل العقدة A إلى يمينها. سيصبح الآن الطفل الأيمن للعقدة B هو الابن الأيسر للعقدة A.

برنامج الميراث في بيثون

دوران R1 (العقدة B لها عامل التوازن 1)

يجب إجراء دوران R1 إذا كان عامل التوازن للعقدة B هو 1. في دوران R1، يتم نقل العقدة الحرجة A إلى يمينها مع وجود شجرتين فرعيتين T2 وT3 كفرعين يسار ويمين على التوالي. يجب وضع T1 كالشجرة الفرعية اليسرى للعقدة B.

تظهر العملية المتضمنة في تدوير R1 في الصورة التالية.

مثال

احذف العقدة 55 من شجرة AVL الموضحة في الصورة التالية.

حل :

يؤدي حذف 55 من شجرة AVL إلى إزعاج عامل التوازن للعقدة 50، أي العقدة A التي تصبح العقدة الحرجة. هذه هي حالة دوران R1 حيث سيتم نقل العقدة A إلى يمينها (كما هو موضح في الصورة أدناه). أصبح يمين B الآن يسار A (أي 45).

تظهر العملية المتضمنة في الحل في الصورة التالية.

تحويل السلسلة إلى عدد صحيح في Java

دوران R-1 (العقدة B لها عامل توازن -1)

يجب إجراء التدوير R-1 إذا كان للعقدة B عامل توازن -1. يتم التعامل مع هذه الحالة بنفس طريقة التعامل مع دوران LR. في هذه الحالة، العقدة C، وهي الابن الأيمن للعقدة B، تصبح العقدة الجذرية للشجرة مع B وA كأبناءها الأيسر والأيمن على التوالي.

تصبح الأشجار الفرعية T1 وT2 الأشجار الفرعية اليسرى واليمنى لـ B بينما تصبح T3 وT4 الأشجار الفرعية اليسرى واليمنى لـ A.

تظهر العملية المتضمنة في تدوير R-1 في الصورة التالية.

مثال

احذف العقدة 60 من شجرة AVL الموضحة في الصورة التالية.

حل:

في هذه الحالة، العقدة B لها عامل التوازن -1. يؤدي حذف العقدة 60 إلى الإخلال بعامل التوازن للعقدة 50، وبالتالي يجب تدوير R-1. العقدة C، أي 45، تصبح جذر الشجرة مع العقدة B(40) وA(50) باعتبارها فرعها الأيسر والأيمن.