AVL 트리 (AVL Tree)
들어가는 말
이진 탐색 트리는 평균적으로 O(log n)의 빠른 탐색·삽입·삭제 성능을 제공한다.
하지만 트리가 한쪽으로 편향되면 높이가 커져 각 연산의 시간 복잡도가 최악의 경우 O(n)까지 증가할 수 있다.
AVL 트리는 회전을 통해 트리의 균형을 지속적으로 유지하여 이러한 문제를 해결한다.
AVL이라는 이름은 1962년에 이를 고안한 Adelson-Velsky와 Landis의 성에서 각각 따온 A, V, L을 조합한 것이다.
동작 원리
AVL 트리는 먼저 이진 탐색 트리의 조건을 그대로 따른다.
즉, 각 노드의 왼쪽 서브트리에는 더 작은 값만, 오른쪽 서브트리에는 더 큰 값만 존재한다.
이 조건에 더해 AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하라는 균형 조건을 항상 유지한다.
삽입이나 삭제로 높이 차이가 1을 초과하면 회전을 통해 균형 조건을 다시 만족시킨다.
균형 인수
트리의 균형 상태는 균형 인수(balance factor, BF)로 확인한다.
균형 인수는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.
이 글에서는 실제로 존재하는 단말 노드의 높이를 0으로 정한다.
자식 노드가 없어 포인터가 NULL인 경우에는 그 빈 서브트리의 높이를 -1로 정한다.
BF = 1 - 0 = 1 BF = 0 - 0 = 0 BF = 0 - 1 = -1
3 3 3
/ \ / \ / \
2 4 1 4 1 4
/ \
1 5루트 노드 3을 기준으로 보면 왼쪽과 오른쪽 서브트리의 높이 차이는 각각 1, 0, -1이다.
균형 인수가 1, 0, -1 중 하나이면 해당 노드는 균형 잡힌 상태다.
BF = 2 - 0 = 2
4
/ \
2 5
/ \
1 3
/
0루트 노드 4를 기준으로 보면 균형 인수가 2이므로 허용 범위를 벗어난 상태다.
삽입이나 삭제 뒤 이처럼 특정 노드의 균형 인수가 허용 범위를 벗어나면 회전으로 트리의 균형을 다시 맞춰야 한다.
불균형 유형과 회전
불균형이 생긴 방향에 따라 네 가지 경우로 나뉘며, 각 경우에 맞는 회전 방법을 적용한다.
LL 유형
BF = 1 - (-1) = 2 BF = 0 - 0 = 0
3 2
/ --> / \
2 1 3
/
1노드 3을 기준으로 왼쪽 서브트리의 높이는 1이고, 빈 오른쪽 서브트리의 높이는 -1이므로 균형 인수는 2다.
불균형이 발생한 노드 3에서 노드 2와 노드 1로 이어지는 경로가 모두 왼쪽 방향이므로 LL 유형이라고 한다.
균형을 회복하기 위해 노드 3을 대상으로 오른쪽 회전을 수행한다.
그 결과 왼쪽 자식이던 노드 2가 해당 서브트리의 새 루트가 되고, 노드 3은 노드 2의 오른쪽 자식으로 내려간다.
RR 유형
BF = -1 - 1 = -2 BF = 0 - 0 = 0
1 2
\ --> / \
2 1 3
\
3노드 1을 기준으로 빈 왼쪽 서브트리의 높이는 -1이고, 오른쪽 서브트리의 높이는 1이므로 균형 인수는 -2다.
불균형이 발생한 노드 1에서 노드 2와 노드 3으로 이어지는 경로가 모두 오른쪽 방향이므로 RR 유형이라고 한다.
균형을 회복하기 위해 노드 1을 대상으로 왼쪽 회전을 수행한다.
그 결과 오른쪽 자식이던 노드 2가 해당 서브트리의 새 루트가 되고, 노드 1은 노드 2의 왼쪽 자식으로 내려간다.
LR 유형
BF = 1 - (-1) = 2 BF = 1 - (-1) = 2 BF = 0 - 0 = 0
3 3 2
/ / / \
1 --> 2 --> 1 3
\ /
2 1노드 3을 기준으로 왼쪽 서브트리의 높이는 1이고, 빈 오른쪽 서브트리의 높이는 -1이므로 균형 인수는 2다.
불균형이 발생한 노드 3에서 노드 1로 이어지는 경로는 왼쪽 방향이고, 노드 1에서 노드 2로 이어지는 경로는 오른쪽 방향이므로 LR 유형이라고 한다.
균형을 회복하기 위해 먼저 노드 1을 대상으로 왼쪽 회전을 수행하여 LL 유형으로 만든다.
그다음 불균형이 발생한 노드 3을 대상으로 오른쪽 회전을 수행한다.
RL 유형
BF = -1 - 1 = -2 BF = -1 - 1 = -2 BF = 0 - 0 = 0
1 1 2
\ \ / \
3 --> 2 --> 1 3
/ \
2 3노드 1을 기준으로 빈 왼쪽 서브트리의 높이는 -1이고, 오른쪽 서브트리의 높이는 1이므로 균형 인수는 -2다.
불균형이 발생한 노드 1에서 노드 3으로 이어지는 경로는 오른쪽 방향이고, 노드 3에서 노드 2로 이어지는 경로는 왼쪽 방향이므로 RL 유형이라고 한다.
균형을 회복하기 위해 먼저 노드 3을 대상으로 오른쪽 회전을 수행하여 RR 유형으로 만든다.
그다음 불균형이 발생한 노드 1을 대상으로 왼쪽 회전을 수행한다.
삽입과 삭제
AVL 트리는 이진 탐색 트리에 균형 유지 기능을 추가한 자료구조다.
따라서 삽입과 삭제는 이진 탐색 트리와 같은 규칙으로 진행한다.
다만 삽입이나 삭제가 끝난 뒤에는 각 조상 노드의 높이와 균형 인수를 갱신하고, 필요하면 회전으로 균형을 맞춘다.
삽입과 삭제에 따른 회전 예시
LL 유형 예시
예시에서는 5, 4, 3, 2, 1을 순서대로 삽입한다.
3을 삽입하면 노드 5의 균형이 왼쪽으로 치우치고, 균형 인수는 2가 된다.
균형을 잡기 위해 오른쪽 회전이 필요하다.
After inserting 3 Rotate right at 5
5 4
/ / \
4 3 5
/
32를 삽입하고 1을 삽입하면 노드 3의 균형이 다시 왼쪽으로 치우친다.
노드 3을 기준으로 오른쪽 회전하면 다시 균형이 맞춰진다.
After inserting 1 Rotate right at 3
4 4
/ \ / \
3 5 2 5
/ / \
2 1 3
/
1모든 값을 삽입한 뒤 5를 삭제하면 루트 4의 균형 인수가 2가 되어 균형이 무너진다.
루트 4를 기준으로 오른쪽 회전하면 다시 균형이 맞춰진다.
After deleting 5 Rotate right at 4
4 2
/ / \
2 1 4
/ \ /
1 3 3RR 유형 예시
예시에서는 1, 2, 3, 4, 5를 순서대로 삽입한다.
3을 삽입하면 노드 1의 균형이 오른쪽으로 치우치고, 균형 인수는 -2가 된다.
균형을 잡기 위해 왼쪽 회전이 필요하다.
After inserting 3 Rotate left at 1
1 2
\ / \
2 1 3
\
34를 삽입하고 5를 삽입하면 노드 3의 균형이 다시 오른쪽으로 치우친다.
노드 3을 기준으로 왼쪽 회전하면 다시 균형이 맞춰진다.
After inserting 5 Rotate left at 3
2 2
/ \ / \
1 3 1 4
\ / \
4 3 5
\
5모든 값을 삽입한 뒤 1을 삭제하면 루트 2의 균형 인수가 -2가 되어 균형이 무너진다.
루트 2를 기준으로 왼쪽 회전하면 다시 균형이 맞춰진다.
After deleting 1 Rotate left at 2
2 4
\ / \
4 2 5
/ \ \
3 5 3LR 유형 예시
예시에서는 3, 1, 7, 2, 4, 6, 5를 순서대로 삽입한다.
6을 삽입하면 노드 7의 균형이 왼쪽으로 치우치고, 균형 인수는 2가 된다.
노드 7을 재균형화하는 과정에서 왼쪽 자식 4를 기준으로 먼저 왼쪽 회전한 뒤, 노드 7을 기준으로 오른쪽 회전한다.
After inserting 6 Rotate left at 4 Rotate right at 7
3 3 3
/ \ / \ / \
1 7 1 7 1 6
\ / \ / \ / \
2 4 2 6 2 4 7
\ /
6 4마지막으로 5를 삽입한 뒤의 트리는 다음과 같다.
After inserting 5
3
/ \
1 6
\ / \
2 4 7
\
5이제 6을 삭제하면 노드 7은 다시 왼쪽으로 치우쳐 균형 인수가 2가 된다.
이를 재균형화하기 위해 왼쪽 자식 노드 4를 기준으로 먼저 왼쪽 회전한 다음, 노드 7을 기준으로 오른쪽 회전한다.
After deleting 6 Rotate left at 4 Rotate right at 7
3 3 3
/ \ / \ / \
1 7 1 7 1 5
\ / \ / \ / \
2 4 2 5 2 4 7
\ /
5 4RL 유형 예시
예시에서는 0, 2, 1, 6, 5, 3, 4를 순서대로 삽입한다.
1을 삽입하면 노드 0의 균형이 오른쪽으로 치우치고, 균형 인수는 -2가 된다.
노드 0을 재균형화하는 과정에서 오른쪽 자식 2를 기준으로 먼저 오른쪽 회전한 뒤, 노드 0을 기준으로 왼쪽 회전한다.
After inserting 1 Rotate right at 2 Rotate left at 0
0 0 1
\ \ / \
2 1 0 2
/ \
1 26을 삽입하고 5를 삽입하면 노드 2의 균형이 다시 오른쪽으로 치우친다.
노드 2를 재균형화하는 과정에서 오른쪽 자식 6을 기준으로 먼저 오른쪽 회전한 뒤, 노드 2를 기준으로 왼쪽 회전한다.
After inserting 5 Rotate right at 6 Rotate left at 2
1 1 1
/ \ / \ / \
0 2 0 2 0 5
\ \ / \
6 5 2 6
/ \
5 63을 삽입하면 루트 1의 균형이 다시 오른쪽으로 치우치고, 균형 인수는 -2가 된다.
루트 1을 재균형화하는 과정에서 오른쪽 자식 5를 기준으로 먼저 오른쪽 회전한 뒤, 루트 1을 기준으로 왼쪽 회전한다.
After inserting 3 Rotate right at 5 Rotate left at 1
1 1 2
/ \ / \ / \
0 5 0 2 1 5
/ \ \ / / \
2 6 5 0 3 6
\ / \
3 3 6마지막으로 4를 삽입한 뒤의 트리는 다음과 같다.
After inserting 4
2
/ \
1 5
/ / \
0 3 6
\
4이제 1을 삭제하면 루트 2의 균형 인수가 -2가 되어 균형이 무너진다.
루트 2를 재균형화하는 과정에서 오른쪽 자식 5를 기준으로 먼저 오른쪽 회전한 뒤, 루트 2를 기준으로 왼쪽 회전한다.
After deleting 1 Rotate right at 5 Rotate left at 2
2 2 3
/ \ / \ / \
0 5 0 3 2 5
/ \ \ / / \
3 6 5 0 4 6
\ / \
4 4 6시간 복잡도
AVL 트리는 이진 탐색 트리에 높이 균형 조건을 추가해 한쪽으로 치우친 최악의 형태가 되는 것을 막는다.
따라서 탐색, 삽입, 삭제는 모두 O(log n) 시간에 수행된다.
소스 코드
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int value;
int height;
struct node* left;
struct node* right;
} Node;
int max_int(int a, int b)
{
return a > b ? a : b;
}
int get_height(const Node* node)
{
return node == NULL ? -1 : node->height;
}
void update_height(Node* node)
{
node->height = max_int(get_height(node->left), get_height(node->right)) + 1;
}
int get_balance(const Node* node)
{
return node == NULL ? 0 : get_height(node->left) - get_height(node->right);
}
Node* create_node(int value)
{
Node* new_node = malloc(sizeof(Node));
if (new_node == NULL)
return NULL;
new_node->value = value;
new_node->height = 0;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
Node* rotate_right(Node* node)
{
Node* new_root = node->left;
Node* new_root_right_subtree = new_root->right;
new_root->right = node;
node->left = new_root_right_subtree;
update_height(node);
update_height(new_root);
return new_root;
}
Node* rotate_left(Node* node)
{
Node* new_root = node->right;
Node* new_root_left_subtree = new_root->left;
new_root->left = node;
node->right = new_root_left_subtree;
update_height(node);
update_height(new_root);
return new_root;
}
Node* rebalance(Node* node)
{
int balance = get_balance(node);
if (balance > 1)
{
if (get_balance(node->left) < 0)
node->left = rotate_left(node->left);
return rotate_right(node);
}
if (balance < -1)
{
if (get_balance(node->right) > 0)
node->right = rotate_right(node->right);
return rotate_left(node);
}
return node;
}
Node* insert_node(Node* root, int value)
{
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert_node(root->left, value);
else if (value > root->value)
root->right = insert_node(root->right, value);
else
return root;
update_height(root);
return rebalance(root);
}
Node* find_min_node(Node* root)
{
while (root->left != NULL)
root = root->left;
return root;
}
Node* delete_node(Node* root, int value)
{
if (root == NULL)
return NULL;
if (value < root->value)
root->left = delete_node(root->left, value);
else if (value > root->value)
root->right = delete_node(root->right, value);
else
{
if (root->left == NULL && root->right == NULL)
{
free(root);
return NULL;
}
if (root->left == NULL)
{
Node* right_child = root->right;
free(root);
return right_child;
}
if (root->right == NULL)
{
Node* left_child = root->left;
free(root);
return left_child;
}
Node* successor = find_min_node(root->right);
root->value = successor->value;
root->right = delete_node(root->right, successor->value);
}
update_height(root);
return rebalance(root);
}
void print_inorder(const Node* root)
{
if (root == NULL)
return;
print_inorder(root->left);
printf("%d ", root->value);
print_inorder(root->right);
}
void destroy_tree(Node* root)
{
if (root == NULL)
return;
destroy_tree(root->left);
destroy_tree(root->right);
free(root);
}
Node* insert_values(const int values[], size_t count)
{
Node* root = NULL;
for (size_t i = 0; i < count; i++)
root = insert_node(root, values[i]);
return root;
}
int main(void)
{
int ll_arr[] = { 5, 4, 3, 2, 1 };
int lr_arr[] = { 3, 1, 7, 2, 4, 6, 5 };
int rr_arr[] = { 1, 2, 3, 4, 5 };
int rl_arr[] = { 0, 2, 1, 6, 5, 3, 4 };
Node* root;
// LL rotations occur when inserting 3 and 1, and when deleting 5.
root = insert_values(ll_arr, sizeof(ll_arr) / sizeof(ll_arr[0]));
root = delete_node(root, 5);
print_inorder(root);
printf("\n");
destroy_tree(root);
// LR rotations occur when inserting and deleting 6.
root = insert_values(lr_arr, sizeof(lr_arr) / sizeof(lr_arr[0]));
root = delete_node(root, 6);
print_inorder(root);
printf("\n");
destroy_tree(root);
// RR rotations occur when inserting 3 and 5, and when deleting 1.
root = insert_values(rr_arr, sizeof(rr_arr) / sizeof(rr_arr[0]));
root = delete_node(root, 1);
print_inorder(root);
printf("\n");
destroy_tree(root);
// RL rotations occur when inserting 1, 5, and 3, and when deleting 1.
root = insert_values(rl_arr, sizeof(rl_arr) / sizeof(rl_arr[0]));
root = delete_node(root, 1);
print_inorder(root);
printf("\n");
destroy_tree(root);
return 0;
}구현 설명
이진 탐색 트리 소스 코드를 바탕으로 AVL 트리에 필요한 요소를 추가해 구현했다.
각 노드는 자신의 높이를 height에 저장하며, 이 구현에서는 단말 노드의 높이를 0으로 정한다.
실제 노드가 아닌 NULL은 빈 서브트리를 뜻하므로 높이를 -1로 취급한다.
따라서 get_height(NULL)은 빈 서브트리의 높이인 -1을 반환한다.
노드의 높이는 균형 인수를 계산하는 데 필요하다.
get_balance는 왼쪽과 오른쪽 서브트리의 높이 차이인 균형 인수를 반환한다.
get_balance(NULL)은 빈 서브트리를 균형 잡힌 상태로 처리하기 위해 0을 반환한다.
기존 이진 탐색 트리보다 많은 함수가 추가되었지만, 가장 중요한 함수는 rebalance다.
균형 인수가 1보다 크면 왼쪽으로, -1보다 작으면 오른쪽으로 치우친 상태이므로 재균형이 필요하다.
균형 인수가 1보다 크면 왼쪽으로 치우친 상태임은 알 수 있지만, LL 유형인지 LR 유형인지는 구분할 수 없다.
따라서 현재 노드의 균형 인수에 이어 왼쪽 자식의 균형 인수도 확인해 두 유형을 구분한다.
왼쪽 자식의 균형 인수가 음수라면 오른쪽 서브트리가 더 높다는 뜻이므로 LR 유형이고, 그렇지 않으면 LL 유형이다.
균형 인수가 -1보다 작으면 오른쪽으로 치우친 상태임은 알 수 있지만, RR 유형인지 RL 유형인지는 구분할 수 없다.
따라서 현재 노드의 균형 인수에 이어 오른쪽 자식의 균형 인수도 확인해 두 유형을 구분한다.
오른쪽 자식의 균형 인수가 양수라면 왼쪽 서브트리가 더 높다는 뜻이므로 RL 유형이고, 그렇지 않으면 RR 유형이다.