오른쪽 회전

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 7번째.

노드의 왼쪽이 너무 높을 때, 우회전(right rotation)으로 이를 해결합니다. 불균형한 노드를 y라고 하고 그 왼쪽 자식을 x라고 합시다. 회전은 x를 y의 자리로 승격시킵니다. 즉, x가 새로운 서브트리의 루트가 되고, y는 x의 오른쪽 자식이 되며, x의 기존 오른쪽 서브트리(T2라고 함)는 y의 새로운 왼쪽 자식으로 다시 연결됩니다. 이는 T2의 모든 값이 여전히 x보다 크고 y보다 작기 때문입니다.

포인터를 다시 연결한 후, y와 x 모두 height를 다시 계산해야 하며, y가 이제 트리에서 더 낮은 위치에 있으므로 y를 먼저 계산합니다.

챌린지

쉬움

AVLTree에 rotateRight(y) 메서드를 작성하세요. x = y.left 그리고 T2 = x.right라고 가정합니다. x.right = y 및 y.left = T2로 설정하고, y와 x의 height를 각각 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;
}