왼쪽 회전

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

좌측 회전(left rotation)은 방금 작성한 우측 회전의 거울 이미지이며, 노드의 오른쪽이 너무 높을 때 사용됩니다. 불균형한 노드를 x라 부르고 그 오른쪽 자식을 y라고 합시다. y는 새로운 서브트리의 루트가 되고, x는 y의 왼쪽 자식이 되며, y의 기존 왼쪽 서브트리(T2)는 x의 새로운 오른쪽 자식으로 다시 연결됩니다.

높이에 대한 규칙도 동일합니다. x가 이제 더 낮은 노드가 되었으므로 x의 높이를 먼저 다시 계산한 다음 y의 높이를 계산합니다.

챌린지

쉬움

AVLTree에 rotateLeft(x) 메서드를 작성하세요. y = x.right이고 T2 = y.left라고 합시다. y.left = x와 x.right = T2로 설정하고, x와 y의 height를 순서대로 다시 계산한 후, 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;
}