AVL 트리(Tree) 개념 및 구현
AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다.
트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다.
한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다.
AVL트리는 다음과 같은 특징을 가집니다.
- AVL 트리는 이진 탐색 트리의 속성을 가집니다.
- 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.
- 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다.
- AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다.
Balance Factor(BF)
Balance Factor(BF)는 외쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값입니다.
Balance Factor (k) = height (left(k)) - height(right(k))
- BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 높다는 것을 의미합니다.
- BF가 0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같다는 것을 의미합니다.
- BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 낮다는 것을 의미합니다.
다음은 ALV 트리의 예입니다. BF가 -1과 +1 사이에 있음을 알 수 있습니다.
시간 복잡도 (Time complexity)
| Operation | Average | Worst |
| Access | Θ(logN) | O(logN) |
| Search | Θ(logN) | O(logN) |
| Insert | Θ(logN) | O(logN) |
| Delete | Θ(logN) | O(logN) |
N은 트리의 노드 수입니다.
AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)입니다.
회전 (rotation)
AVL트리는 이진 탐색 트리이기 때문에 모든 작업은 이진 탐색 트리에서 사용하는 방식으로 수행됩니다.
검색 및 순회 연산은 BF를 변경하지 않지만 삽입 및 삭제에서는 BF가 변경될 수 있습니다.
삽입 삭제 시 불균형 상태(BF가 -1 ,0, 1이 아닌 경우) 가 되면 AVL트리는 불균형 노드를 기준으로 서브트리의 위치를 변경하는 rotation 작업을 수행하여 트리의 균형을 맞추게 됩니다.
삽입 삭제시 노드들의 배열에 따라 4가지(LL, RR, LR, RL) 불균형이 발생할 수 있으며 각 상황마다 rotation에 방향을 달리하여 트리의 균형을 맞춥니다.
그림에서 T1~4는 서브 트리를 나타냅니다.
LL(Left Left) case
y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여 균형을 맞춥니다.
right rotation 수행 과정
- y노드의 오른쪽 자식 노드를 z노드로 변경합니다.
- z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경합니다.
- y는 새로운 루트 노드가 됩니다.
Right Rotation 구현
struct node *rightRotate (struct node *z) {
struct node *y = z->left;
struct node *T2 = y->right;
// right 회전 수행
y->right = z;
z->left = T2;
// 노드 높이 갱신
z->height = 1 + max(z->left->height, z->right->height);
y->height = 1 + max(y->left->height, y->right->height);
// 새로운 루트 노드 y를 반환
return y;
}
RR(Right Right) case
y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여 균형을 맞춥니다.
left rotation 수행 과정
- y노드의 왼쪽 자식 노드를 z노드로 변경합니다.
- z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경합니다.
- y는 새로운 루트 노드가 됩니다.
Left Rotation 구현
struct node *leftRotate (struct node *z) {
struct node *y = z->right;
struct node *T2 = y->left;
// left 회전 수행
y->left = z;
z->right = T2;
// 노드 높이 갱신
z->height = 1 + max(z->left->height, z->right->height);
y->height = 1 + max(y->left->height, y->right->height);
// 새로운 루트 노드 y를 반환
return y;
}LR(Left Right) case
y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춥니다.
구현
y = z->left;
y = leftRotate(y);
z = rightRotate(z);RL(Right Left) case
y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춥니다.
구현
y = z->right;
y = rightRotate(y);
z = leftRotate(z);삽입 구현
AVL트리의 삽입 삭제 방식은 이진 탐색 트리와 같습니다. 하지만 높이 균형을 유지하기 위해 노드의 높이 정보와 case별 rotation 과정이 추가됩니다.
삭제도 과정이 비슷하기 때문에 삽입만 알아보도록 하겠습니다.
struct node {
int key;
struct node *left, *right;
int height;
};
int max(int a, int b) {
return (a > b)? a : b;
}
struct node* newNode(int key) {
struct node *temp = (struct *node)malloc(sizeof(struct node));
temp->key = key;
temp->left = NULL;
temp->right = NULL;
temp->height = 1;
return temp;
}
struct node *leftRotate (struct node *z) {
struct node *y = z->right;
struct node *T2 = y->left;
// left 회전 수행
y->left = z;
z->right = T2;
// 노드 높이 갱신
z->height = 1 + max(z->left->height, z->right->height);
y->height = 1 + max(y->left->height, y->right->height);
// 새로운 루트 노드 y를 반환
return y;
}
struct node *rightRotate (struct node *z) {
struct node *y = z->left;
struct node *T2 = y->right;
// right 회전 수행
y->right = z;
z->left = T2;
// 노드 높이 갱신
z->height = 1 + max(z->left->height, z->right->height);
y->height = 1 + max(y->left->height, y->right->height);
// 새로운 루트 노드 y를 반환
return y;
}
// BF(BalanceFactor)값을 가져오는 함수.
int getBalanceFactor(struct node *n) {
if (n == NULL)
return 0;
return n->left->height - n->right->height;
}
// 트리의 높이 균형을 유지하는 함수.
// 4가지 케이스를 가지고 rotate를 수행함.
struct node* rebalance(struct node* root) {
int bFactor = getBalanceFactor(root);
// LL Case
if (bFactor > 1 && key < node->left->key)
return rightRotate(root);
// RR Case
if (bFactor < -1 && key > node->right->key)
return leftRotate(root);
// LR Case
if (bFactor > 1 && key > node->left->key){
root->left = leftRotate(root->left);
return rightRotate(root);
}
// RL Case
if (bFactor < -1 && key < node->right->key){
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// 삽입 함수.
struct node* insert(struct node* root, int key) {
// 삽입 수행
if (root == NULL)
return newNode(key);
if (key > root->data)
root->right = insert(root->right, key);
else if (key < root->data)
root->left = insert(root->left, key);
else
return root;
// 노드 높이 갱신
root->height = 1 + max(node->left->height, node->right->height);
// 노드 균형 유지
root = rebalance(root);
return root;
}
