AVL 트리: 회전, 삽입, 삭제 C++ 예시
사라 첸
⚡ 스마트 요약
AVL 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리 사이의 높이 차이가 -1, 0 또는 +1 이내로 유지되는 자체 균형 이진 검색 트리로, O(log n) 검색 성능을 보장합니다.
AVL 트리란 무엇입니까?
AVL 나무 이진 탐색 트리(BST)는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 -1, 0 또는 +1인 트리입니다. 이들은 로그 시간 복잡도를 유지하는 자체 균형 BST이며, 발명가인 아델슨-벨스키와 랜디스(AVL)의 이름을 따서 명명되었습니다.
AVL 트리는 어떻게 작동하나요?
AVL 트리가 존재하는 이유를 이해하려면 일반 트리에서 어떤 문제가 발생하는지 살펴보세요. 이진 검색 트리다음 키들이 주어진 순서대로 삽입되었다고 가정해 보세요:
AVL 트리 시각화
키가 오름차순으로 입력될 때 트리는 선형적으로 성장하여 검색 시간이 O(n)으로 늘어납니다. 이는 이진 검색 트리(BST)의 목적에 어긋납니다. 균형 트리만이 검색 시간을 로그 시간 복잡도로 유지합니다. 이제 동일한 키를 다른 순서로 삽입하는 경우를 살펴보겠습니다.
동일한 키라도 삽입 순서가 다르면 트리의 형태가 얕아지므로 모든 검색은 O(log n) 시간 복잡도로 실행됩니다. AVL 트리는 삽입 시마다 트리의 높이를 감시하고 이진 검색 순서를 유지하면서 불균형을 수정함으로써 트리의 형태를 유지합니다.
AVL 트리의 균형 요소
균형 계수(BF) trac각 노드의 높이를 ks로 설정하여 트리가 실행 중에 자체 균형을 유지할 수 있도록 합니다.
밸런스 팩터의 특성
균형 인자 AVL 트리
- 균형 계수는 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이입니다.
Balance factor(node) = height(node->left) − height(node->right)- 허용되는 값은 -1, 0, +1뿐입니다.
- -1이라는 값은 오른쪽 서브트리에 레벨이 하나 더 많다는 것을 의미하며, 이는 노드가 오른쪽으로 치우쳐 있다는 뜻입니다.
- +1이라는 값은 왼쪽 서브트리에 레벨이 하나 더 있다는 것을 의미하며, 이는 노드가 왼쪽으로 치우쳐 있다는 뜻입니다.
- 값이 0이면 양쪽 높이가 동일하다는 의미이며, 노드가 완벽하게 균형을 이루고 있다는 뜻입니다.
AVL 회전
삽입이나 삭제로 인해 균형 요소 규칙이 깨질 때마다 순환이 실행됩니다. 네 가지 경우는 LL, RR, LR, RL입니다.
왼쪽 – 왼쪽 회전
이 회전은 왼쪽 하위 트리의 왼쪽 자식에 새 노드가 삽입될 때 수행됩니다.
AVL 트리 왼쪽 - 왼쪽 회전
오른쪽으로 한 번 회전합니다. 이 경우는 노드의 BF가 +2이고 왼쪽 자식 노드의 BF가 +1일 때 발생합니다.
오른쪽 – 오른쪽 회전
이 회전은 오른쪽 하위 트리의 오른쪽 자식에 새 노드가 삽입될 때 수행됩니다.
한 번의 좌측 회전이 수행됩니다. 이 경우는 노드의 BF가 -2이고 해당 노드의 오른쪽 자식의 BF가 -1일 때 발생합니다.
오른쪽 – 왼쪽 회전
이 회전은 오른쪽 하위 트리의 왼쪽 자식에 새 노드가 삽입될 때 수행됩니다.
BF(노드) = -2이고 BF(오른쪽 자식) = +1일 때 발생합니다. 오른쪽 자식을 오른쪽으로 회전한 다음 노드를 왼쪽으로 회전합니다.
왼쪽 – 오른쪽 회전
이 회전은 왼쪽 하위 트리의 오른쪽 자식에 새 노드가 삽입될 때 수행됩니다.
노드의 BF 값이 +2이고 왼쪽 자식 노드의 BF 값이 -1일 때 실행됩니다. 왼쪽 자식 노드를 왼쪽으로 회전한 다음, 노드를 오른쪽으로 회전합니다.
AVL 트리에 삽입
삽입은 일반적인 이진 검색 트리(BST) 삽입과 거의 동일합니다. 삽입이 완료될 때마다 트리는 위쪽으로 이동하여 균형을 재조정합니다. 삽입은 최악의 경우 O(log n) 시간 복잡도로 실행됩니다.
AVL 트리 삽입 구현
1 단계 : 표준 BST 알고리즘을 사용하여 노드를 삽입합니다. 위 예시에서는 160을 삽입합니다.
2 단계 : 삽입 경로상의 모든 조상의 균형 계수를 업데이트합니다.
3 단계 : 만약 어떤 조상 노드가 균형 요소 범위를 벗어나면, 그에 맞는 회전을 수행합니다. 예시에서 노드 350의 균형 요소가 벗어나므로, LL 회전을 통해 균형을 복원합니다.
- If
BF(node) = +2BF(left-child) = +1LL 회전을 수행합니다. - If
BF(node) = −2BF(right-child) = −1RR 회전을 수행합니다. - If
BF(node) = −2BF(right-child) = +1RL 회전을 수행합니다. - If
BF(node) = +2BF(left-child) = −1LR 회전을 수행합니다.
AVL 트리의 삭제
삭제는 일반 이진 검색 트리(BST)와 동일한 논리를 따르며, 삭제 후 재균형이 맞춰집니다.
1 단계 : 트리에서 요소를 찾으세요.
2 단계 : 표준 BST 삭제 방법을 사용하여 노드를 삭제합니다.
3 단계 : 두 가지 경우가 가능합니다.
케이스 1 : 오른쪽 하위 트리에서 삭제합니다.
- 1A. If
BF(node) = +2BF(left-child) = +1LL 회전을 수행합니다. - 1B. If
BF(node) = +2BF(left-child) = −1LR 회전을 수행합니다. - 1C. If
BF(node) = +2BF(left-child) = 0LL 회전을 수행합니다.
케이스 2 : 왼쪽 하위 트리에서 삭제합니다.
- 2A. If
BF(node) = −2BF(right-child) = −1RR 회전을 수행합니다. - 2B. If
BF(node) = −2BF(right-child) = +1RL 회전을 수행합니다. - 2C. If
BF(node) = −2BF(right-child) = 0RR 회전을 수행합니다.
C++ AVL 트리의 예
아래는 C++ AVL 트리를 구현하는 프로그램:
#include <iostream> #include <queue> #include <unordered_map> using namespace std; struct node { struct node *left; int data; int height; struct node *right; }; class AVL { public: struct node *root; AVL() { this->root = NULL; } int calheight(struct node *p) { if (p->left && p->right) { if (p->left->height < p->right->height) return p->right->height + 1; else return p->left->height + 1; } else if (p->left && p->right == NULL) { return p->left->height + 1; } else if (p->left == NULL && p->right) { return p->right->height + 1; } return 0; } int bf(struct node *n) { if (n->left && n->right) return n->left->height - n->right->height; else if (n->left && n->right == NULL) return n->left->height; else if (n->left == NULL && n->right) return -n->right->height; return 0; } struct node *llrotation(struct node *n) { struct node *p = n; struct node *tp = p->left; p->left = tp->right; tp->right = p; return tp; } struct node *rrrotation(struct node *n) { struct node *p = n; struct node *tp = p->right; p->right = tp->left; tp->left = p; return tp; } struct node *rlrotation(struct node *n) { struct node *p = n; struct node *tp = p->right; struct node *tp2 = p->right->left; p->right = tp2->left; tp->left = tp2->right; tp2->left = p; tp2->right = tp; return tp2; } struct node *lrrotation(struct node *n) { struct node *p = n; struct node *tp = p->left; struct node *tp2 = p->left->right; p->left = tp2->right; tp->right = tp2->left; tp2->right = p; tp2->left = tp; return tp2; } struct node *insert(struct node *r, int data) { if (r == NULL) { r = new struct node; r->data = data; r->left = r->right = NULL; r->height = 1; return r; } if (data < r->data) r->left = insert(r->left, data); else r->right = insert(r->right, data); r->height = calheight(r); if (bf(r) == 2 && bf(r->left) == 1) r = llrotation(r); else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r); else if (bf(r) == -2 && bf(r->right) == 1) r = rlrotation(r); else if (bf(r) == 2 && bf(r->left) == -1) r = lrrotation(r); return r; } void levelorder_newline() { if (this->root == NULL) { cout << "\nEmpty tree\n"; return; } levelorder_newline(this->root); } void levelorder_newline(struct node *v) { queue<struct node *> q; struct node *cur; q.push(v); q.push(NULL); while (!q.empty()) { cur = q.front(); q.pop(); if (cur == NULL && q.size() != 0) { cout << "\n"; q.push(NULL); continue; } if (cur != NULL) { cout << " " << cur->data; if (cur->left != NULL) q.push(cur->left); if (cur->right != NULL) q.push(cur->right); } } } struct node *deleteNode(struct node *p, int data) { if (p->left == NULL && p->right == NULL) { if (p == this->root) this->root = NULL; delete p; return NULL; } struct node *q; if (p->data < data) p->right = deleteNode(p->right, data); else if (p->data > data) p->left = deleteNode(p->left, data); else { if (p->left != NULL) { q = inpre(p->left); p->data = q->data; p->left = deleteNode(p->left, q->data); } else { q = insuc(p->right); p->data = q->data; p->right = deleteNode(p->right, q->data); } } if (bf(p) == 2 && bf(p->left) == 1) p = llrotation(p); else if (bf(p) == 2 && bf(p->left) == -1) p = lrrotation(p); else if (bf(p) == 2 && bf(p->left) == 0) p = llrotation(p); else if (bf(p) == -2 && bf(p->right) == -1) p = rrrotation(p); else if (bf(p) == -2 && bf(p->right) == 1) p = rlrotation(p); else if (bf(p) == -2 && bf(p->right) == 0) p = rrrotation(p); return p; } struct node *inpre(struct node *p) { while (p->right != NULL) p = p->right; return p; } struct node *insuc(struct node *p) { while (p->left != NULL) p = p->left; return p; } ~AVL() {} }; int main() { AVL b; int c, x; do { cout << "\n1.Display levelorder on newline"; cout << "\n2.Insert"; cout << "\n3.Delete\n"; cout << "\n0.Exit\n"; cout << "\nChoice: "; cin >> c; switch (c) { case 1: b.levelorder_newline(); break; case 2: cout << "\nEnter no. "; cin >> x; b.root = b.insert(b.root, x); break; case 3: cout << "\nWhat to delete? "; cin >> x; b.root = b.deleteNode(b.root, x); break; case 0: break; } } while (c != 0); }
위 코드의 실행 예시:
- 위 코드를 복사하여 파일에 저장하세요.
avl.cpp. - 코드를 컴파일합니다.
g++ avl.cpp -o run
- 코드를 실행합니다.
./run
AVL 트리의 장점
- AVL 트리의 높이는 항상 균형을 이루며 log N을 초과하여 성장하지 않습니다.
- 이 방법은 트리가 퇴화될 수 없기 때문에 일반 이진 검색 트리보다 검색 속도가 빠릅니다.
- 자체 균형 조정은 자동으로 이루어지며, 재구축 단계는 필요하지 않습니다.
- 결정론적 성능은 실시간 시스템과 인메모리 인덱스에 적합합니다.
