Sağa Döndürme

Coddy'nin AVL Tree - Veri Yapıları Serisi #10 kursunda ders 7 / 16.

Bir düğümün sol tarafı çok yüksek olduğunda, bir sağa döndürme bunu düzeltir. Dengesiz düğüme y ve onun sol çocuğuna x diyelim. Döndürme işlemi, x'i y'nin yerine yükseltir: x yeni alt ağaç kökü olur, y x'in sağ çocuğu olur ve x'in eski sağ alt ağacı (buna T2 diyelim), T2'deki her değer hala x'ten büyük ve y'den küçük olduğu için y'nin yeni sol çocuğu olarak yeniden bağlanır.

İşaretçiler yeniden bağlandıktan sonra, hem y hem de x'in height değerinin yeniden hesaplanması gerekir; y artık ağaçta daha aşağıda olduğu için önce onunki hesaplanır.

Görev

Kolay

AVLTree üzerinde bir rotateRight(y) metodu yazın. x = y.left ve T2 = x.right olsun. x.right = y ve y.left = T2 olarak ayarlayın, y ve ardından x'in height değerini 1 + max(getHeight(left), getHeight(right)) olarak yeniden hesaplayın ve yeni alt ağaç kökü olarak x değerini döndürün.

Kendin dene

#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;
}