التدوير لليسار

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

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

نفس القاعدة بالنسبة للارتفاعات: أعد حساب x أولاً، ثم y، بما أن x هي الآن العقدة الأدنى.

التحدي

سهل

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

جرّب بنفسك

#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* x = Node_create(10);
            x->height = 3;
            Node* y = Node_create(20);
            y->height = 2;
            Node* t2 = Node_create(30);
            t2->height = 1;
            y->right = t2;
            x->right = y;
            Node* newRoot = AVLTree_rotateLeft(tree, x);
            printf("%d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value);
        }
        if (strcmp(line, "2") == 0) {
            Node* x = Node_create(20);
            x->height = 3;
            Node* y = Node_create(40);
            y->height = 2;
            y->left = Node_create(30);
            y->left->height = 1;
            y->right = Node_create(50);
            y->right->height = 1;
            x->left = Node_create(10);
            x->left->height = 1;
            x->right = y;
            Node* newRoot = AVLTree_rotateLeft(tree, x);
            printf("%d %d %d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value, newRoot->left->left->value, newRoot->left->right->value);
        }
    }
    return 0;
}