التدوير لليمين

الدرس 7 من 16 في دورة شجرة AVL - سلسلة هياكل البيانات #10 على Coddy.

عندما يكون الجانب الأيسر للعقدة طويلاً جداً، فإن الدوران لليمين يقوم بإصلاح ذلك. لنسمِّ العقدة غير المتوازنة y وطفلها الأيسر x. يقوم الدوران بترقية x ليأخذ مكان y: حيث يصبح x هو الجذر الجديد للشجرة الفرعية، ويصبح y هو الطفل الأيمن لـ x، ويتم إعادة ربط الشجرة الفرعية اليمنى القديمة لـ x (لنسمِّها T2) كطفل أيسر جديد لـ y، بما أن كل قيمة في T2 لا تزال أكبر من x وأصغر من y.

بعد إعادة ربط المؤشرات، تحتاج كل من y و x إلى إعادة حساب الـ height الخاص بهما، y أولاً لأنها أصبحت الآن في مستوى أدنى في الشجرة.

التحدي

سهل

اكتب طريقة rotateRight(y) في AVLTree. ليكن x = y.left و T2 = x.right. قم بتعيين x.right = y و y.left = T2، ثم أعد حساب height لـ y ثم x كـ 1 + max(getHeight(left), getHeight(right))، وأرجع x كجذر جديد للشجرة الفرعية.

جرّب بنفسك

#include <stdio.h>
#include <string.h>
#include "avltree.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        if (strcmp(line, "1") == 0) {
            Node* y = Node_create(30);
            y->height = 3;
            Node* x = Node_create(20);
            x->height = 2;
            Node* t1 = Node_create(10);
            t1->height = 1;
            x->left = t1;
            y->left = x;
            Node* newRoot = AVLTree_rotateRight(tree, y);
            printf("%d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value);
        }
        if (strcmp(line, "2") == 0) {
            Node* y = Node_create(50);
            y->height = 3;
            Node* x = Node_create(30);
            x->height = 2;
            x->left = Node_create(20);
            x->left->height = 1;
            x->right = Node_create(40);
            x->right->height = 1;
            y->left = x;
            y->right = Node_create(60);
            y->right->height = 1;
            Node* newRoot = AVLTree_rotateRight(tree, y);
            printf("%d %d %d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value, newRoot->right->left->value, newRoot->right->right->value);
        }
    }
    return 0;
}