AVL 트리
마지막 업데이트
AVL 트리는 자가 균형 이진 탐색 트리입니다. 일반 BST처럼 작동하지만, 삽입할 때마다 각 조상의 균형 인수(왼쪽 및 오른쪽 서브트리 간 높이 차이)를 확인하고, 어떤 노드가 불균형해지면(차이가 1보다 큼) 회전을 수행하여 균형을 복원합니다. 위의 재생 버튼을 눌러 값이 삽입되고 트리가 다시 제 모양으로 회전하는 것을 확인하세요.
트리가 조금이라도 지나치게 치우치는 것을 결코 허용하지 않기 때문에, AVL 트리는 O(log n) 높이를 보장하며, 따라서 탐색, 삽입, 삭제는 항상 O(log n)입니다. 일반 BST를 망가뜨릴 정렬된 입력에 대해서도 그렇습니다. 그 대가는 삽입마다 발생하는 추가 회전과 높이 관리입니다.
시간 및 공간 복잡도
| 연산 | 복잡도 | 참고 |
|---|---|---|
| 탐색 | O(log n) | 높이는 항상 ~1.44 log n |
| 삽입 | O(log n) | 추가로 O(1) 회전 |
| 삭제 | O(log n) | 추가로 O(log n) 회전 |
| 공간 | O(n) | 노드당 높이 필드 하나 |
네 가지 회전 경우
| 경우 | 불균형 | 수정 |
|---|---|---|
| 왼쪽-왼쪽 | 왼쪽 자식의 왼쪽이 무거움 | 한 번의 오른쪽 회전 |
| 오른쪽-오른쪽 | 오른쪽 자식의 오른쪽이 무거움 | 한 번의 왼쪽 회전 |
| 왼쪽-오른쪽 | 왼쪽 자식의 오른쪽이 무거움 | 왼쪽 회전 후 오른쪽 회전 |
| 오른쪽-왼쪽 | 오른쪽 자식의 왼쪽이 무거움 | 오른쪽 회전 후 왼쪽 회전 |
풀이 예제
[10, 20, 30, 40, 50, 25]를 한 번에 하나씩 삽입:
| 단계 | 구조 | 동작 |
|---|---|---|
10 삽입 | 10 | 첫 번째 노드가 루트가 됨; 균형 |
20 삽입 | 10(_, 20) | 10의 오른쪽으로 감; 여전히 균형 |
30 삽입 | 20(10, 30) | 10에서 오른쪽-오른쪽, 따라서 한 번의 왼쪽 회전이 20을 루트로 올림 |
40 삽입 | 20(10, 30(_, 40)) | 30의 오른쪽으로 감; 모든 균형 인수가 ±1 이내로 유지됨 |
50 삽입 | 20(10, 40(30, 50)) | 30에서 오른쪽-오른쪽, 따라서 30에서의 왼쪽 회전이 40을 올림 |
25 삽입 | 30(20(10, 25), 40(_, 50)) | 20에서 오른쪽-왼쪽: 40의 서브트리를 오른쪽으로 회전한 후 20을 왼쪽으로 회전 |
AVL 트리를 사용해야 할 때
| 사용해야 할 때 | 피해야 할 때 |
|---|---|
| 탐색이 삽입보다 훨씬 많고 가능한 한 가장 낮은 높이를 원할 때 | 삽입과 삭제가 우세할 때 - 추가 회전과 재균형은 레드-블랙 트리보다 비용이 큼 |
적대적이거나 정렬된 입력에 대해서도 보장된 O(log n) 최악의 경우가 필요할 때 | 단순 해시 테이블이면 충분할 때 - 정렬된 순회나 범위 질의가 필요 없을 때 |
| 정렬된 연산이 필요할 때: 중위 순회, 선행자/후행자, 범위 질의 | 데이터 집합이 매우 작을 때 - 일반 BST나 정렬된 배열이 더 간단하고 충분히 빠름 |
| 데이터가 이미 정렬된 채로 도착할 수 있어 불균형 BST를 연결 리스트로 만들 수 있을 때 | 매우 빠듯한 메모리에서 노드당 높이 필드의 추가 메모리를 감당할 수 없을 때 |
AVL Tree 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 AVL Tree 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 AVL Tree 코드
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)JavaScript로 구현한 AVL Tree 코드
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Java로 구현한 AVL Tree 코드
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}C++로 구현한 AVL Tree 코드
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}C로 구현한 AVL Tree 코드
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}AVL 트리 FAQ
AVL 트리에서 균형 인수란 무엇인가요?
노드의 균형 인수는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값입니다. AVL 트리는 모든 노드의 균형 인수를 -1, 0 또는 +1로 유지합니다. 삽입이 그 범위를 벗어나게 하면 회전이 균형을 복원합니다.
AVL 트리와 레드-블랙 트리의 차이는 무엇인가요?
둘 다
O(log n) 연산을 갖는 자가 균형 BST입니다. AVL 트리는 더 엄격하게 균형이 잡혀 있어 조회가 약간 더 빠르지만, 삽입/삭제 시 회전을 더 많이 할 수 있습니다. 레드-블랙 트리는 더 느슨하게 균형이 잡혀 회전 수를 줄이는 것을 선호합니다 - 그래서 많은 표준 라이브러리가 맵과 집합에 이를 사용합니다.왜 일반 이진 탐색 트리 대신 AVL 트리를 사용하나요?
일반 BST는 값이 정렬된 순서로 들어오면 치우친 사슬을 형성하여 연산이
O(n)으로 저하될 수 있습니다. AVL 트리는 회전하여 균형을 유지하므로, 삽입 순서와 관계없이 O(log n) 높이와 연산을 보장합니다.데이터베이스 인덱스에는 AVL 트리가 레드-블랙 트리보다 나은가요?
워크로드에 따라 다릅니다. AVL 트리는 더 엄격하게 균형이 잡혀 있어 읽기가 우세하고 가능한 한 짧은 탐색 경로를 원할 때 유리합니다. 하지만 대부분의 데이터베이스와 언어 라이브러리는 레드-블랙 트리(또는 B-트리)를 선택합니다. 쓰기 위주 워크로드에서 더 적은 회전으로 재균형하며, 삽입과 삭제가 빈번할 때 그것이 더 중요하기 때문입니다.
한 번의 AVL 삽입에는 회전이 몇 번 필요한가요?
값 하나를 삽입한 후 트리를 재균형하는 데는 단일 회전 또는 이중(2단계) 회전 중 하나로 최대 한 번의 회전이면 충분합니다. 삽입은 서브트리의 높이를 최대 1만 증가시키므로, 가장 낮은 불균형 조상에서의 단일 수정이면 충분하기 때문입니다. 삭제는 다릅니다: 재균형이 루트를 향해 전파되면서 최대
O(log n)번의 회전이 필요할 수 있습니다.회전할 때마다 노드 높이를 갱신해야 하나요?
네 - 흔한 버그는 포인터는 올바르게 회전했지만 관련된 두 노드의 높이 재계산을 잊는 것입니다. 각 회전 후에는 먼저 강등된 노드의 높이를, 그다음 승격된 노드의 높이를 갱신해야 합니다. 승격된 노드의 높이는 새 자식에 의존하기 때문입니다. 이를 건너뛰면 오래된 균형 인수가 남아 이후의 재균형 판단을 망가뜨립니다.
관련 자료
더 많은 시각화
