[c++] AVL 트리의 회전 연산(AVL Tree Rotations)

12 Dec 2023

AVL 트리는 이진 탐색 트리의 특별한 형태로, 균형잡힌 트리를 유지한다. AVL 트리를 조작하는 과정에서 회전 연산이 사용된다. 이 연산은 트리의 균형을 유지하고 새로운 노드를 삽입하거나 삭제할 때 발생하는 불균형을 해결하는 데 사용된다.

회전 연산의 종류

AVL 트리의 회전 연산은 크게 두 가지 유형으로 나뉜다.

LL 회전: 오른쪽으로 한 번 회전
RR 회전: 왼쪽으로 한 번 회전

이러한 회전 연산을 통해 트리의 균형을 유지한다.

LL 회전

LL 회전은 노드의 왼쪽 자식의 왼쪽에 노드를 삽입했을 때 발생한다. 이 경우 노드를 오른쪽으로 한 번 회전시켜 균형을 유지한다.

다음은 C++로 구현한 LL 회전의 예시이다.

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};
 
Node* llRotation(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
 
    x->right = y;
    y->left = T2;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}

RR 회전

RR 회전은 노드의 오른쪽 자식의 오른쪽에 노드를 삽입했을 때 발생한다. 이 경우 노드를 왼쪽으로 한 번 회전시켜 균형을 유지한다.

다음은 C++로 구현한 RR 회전의 예시이다.

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};
 
Node* rrRotation(Node* y) {
    Node* x = y->right;
    Node* T2 = x->left;
 
    x->left = y;
    y->right = T2;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}

결론

AVL 트리의 회전 연산은 트리의 균형을 유지하고 새로운 노드를 삽입하거나 삭제할 때의 불균형을 해결하는 데 중요한 역할을 한다. 이를 통해 AVL 트리가 항상 균형을 유지하며 빠르게 탐색이 가능하도록 보장한다.

참고 자료