كيف هو مثال ويكيبيديا على شجرة AVL غير متوازنة غير متوازن حقًا؟

Question

الصورة أعلاه من "دخول ويكيبيديا على أشجار AVL" الذي يشير ويكيبيديا إلى غير متوازن. كيف لا تكون هذه الشجرة متوازنة بالفعل؟ إليك اقتباس من المقال:

عامل التوازن في العقدة هو ارتفاع الشجرة الفرعية اليمنى ناقص ارتفاع الشجرة الفرعية اليسرى وعقدة مع عامل التوازن 1 أو 0 أو -1 تعتبر متوازنة. تعتبر العقدة مع أي عامل توازن آخر غير متوازن وتتطلب إعادة توازن الشجرة. يتم تخزين عامل التوازن إما مباشرة في كل عقدة أو محسوبة من ارتفاعات القطع الفرعية.

يبلغ ارتفاع كل من القطع الفرعية اليسرى والأيمن 4. الشجرة الفرعية اليمنى للشجرة اليسرى لها ارتفاع 3 لا يزال أقل من 1 فقط من 4. هل يمكن لأي شخص أن يشرح ما أفتقده؟

Answer 1

لتكون متوازنة ، يجب على كل عقدة في الشجرة ، أيضًا ،

• ليس لديك أطفال ، (كن عقدة "ورقة")
• لدي ولدين.

• أو ، إذا كان لديه طفل واحد فقط ، يجب أن يكون هذا الطفل ورقة.

  في المخطط الذي نشرته ، 9 و 54 و 76 ينتهك القاعدة الأخيرة.

متوازنة بشكل صحيح ، ستبدو الشجرة:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

تحديث: (بعد حوالي 9 سنوات ، قمت بإنشاء مخطط رائع عبر الإنترنت للرسوم البيانية في Draw.io)

Answer 2

العقدة 76 غير متوازنة ، على سبيل المثال ، لأن الشجرة الفرعية اليمنى لها من ارتفاع 0 واليسر من ارتفاع 3.

Answer 3

بشكل حدسي ، لأنه ليس صغيرًا قدر الإمكان. على سبيل المثال ، يجب أن يكون 12 الوالد من 9 و 14. كما هو ، 9 لا يوجد لديه شجرة فرعية اليسار ، لذا فهي غير متوازنة. الشجرة هي بنية بيانات هرمية ، لذا فإن قاعدة مثل "متوازنة" غالبًا ما تنطبق على كل عقدة وليس فقط عقدة الجذر.

أنت تصحح أن عقدة الجذر متوازنة ، ولكن ليس كل العقد من الشجرة.

Answer 4

هناك طريقة أخرى للنظر إلى هذا وهي أن الارتفاع h يتم إعطاء أي عقدة بواسطة:

h = 1 + max( left.height, right.height )

والعقدة غير متوازنة كلما:

abs( left.height - right.height ) > 1

النظر إلى الشجرة أعلاه:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

لتحديد ما إذا كانت العقدة 9 متوازنة أم لا ننظر إلى ارتفاع أطفالها:

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

الآن حل لإظهار أن العقدة 9 غير متوازنة:

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

يمكن إجراء حسابات مماثلة لكل عقدة أخرى.