도입
BST는 왼쪽은 더 작고 오른쪽은 더 크다는 규칙 덕분에 검색이 빠르지만, 입력 순서가 나쁘면 한쪽으로 길게 치우쳐 연결 리스트처럼 변할 수 있습니다.
AVL 트리는 이 문제를 해결하기 위해 각 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이를 제한합니다. 즉 BST property 위에 “균형 조건”을 하나 더 올려놓은 구조라고 보면 이해가 쉽습니다.
그래서 AVL 트리를 이해한다는 것은 단순히 검색 트리를 하나 더 배우는 것이 아니라, BST의 탐색 성질을 유지하면서 최악의 높이를 어떻게 제어할 것인지 이해하는 일에 가깝습니다.
필요성
일반 BST는 평균적으로는 잘 동작해도, 삽입 순서가 오름차순이나 내림차순처럼 치우치면 높이가 급격히 커질 수 있습니다. 이 경우 검색, 삽입, 삭제의 핵심 연산이 모두 길어진 경로를 따라가야 하므로 성능이 나빠집니다.
AVL 트리는 이런 편향을 구조적으로 막아 줍니다. 각 노드에서 두 서브트리의 높이 차이를 제한하므로, 트리 높이가 로그 범위 안에 머물고, 결과적으로 검색과 업데이트 성능도 더 예측 가능해집니다.
즉 AVL의 가치는 단순히 “균형이 맞다”는 데 있지 않고, BST가 가진 좋은 검색 성질을 최악의 경우에도 유지하려는 데 있습니다.
- 정렬 기반 검색을 자주 해야 할 때
- 최악의 경우에도 로그 높이를 유지하고 싶을 때
- 삽입과 삭제가 섞여 들어오지만 성능 편차를 줄이고 싶을 때
- 중위 순회를 통해 정렬 순 접근도 함께 얻고 싶을 때
정의
AVL 트리는 기본적으로 BST입니다. 따라서 왼쪽 서브트리의 키는 현재 노드보다 작고, 오른쪽 서브트리의 키는 더 커야 합니다.
여기에 AVL balancing rule이 추가됩니다. 각 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 -1, 0, +1 범위를 벗어나면 그 트리는 AVL 트리가 아닙니다.
즉 AVL은 “검색 규칙”과 “균형 규칙”을 동시에 만족해야 하는 자료구조입니다. 둘 중 하나라도 깨지면 단순 BST 또는 단순 이진 트리일 뿐, AVL이라고 부를 수 없습니다.
"AVL 트리의 본질은 BST 위에
높이 차이를 제한하는 균형 규칙을 더해 최악의 높이를 억제하는 데 있습니다."
핵심 원리
AVL 트리의 검색은 BST와 같습니다. 루트에서 시작해 더 작으면 왼쪽, 더 크면 오른쪽으로 내려갑니다.
차이는 수정 연산 이후에 드러납니다. 삽입이나 삭제 때문에 어떤 노드의 두 서브트리 높이 차이가 2 이상이 되면 AVL invariant가 깨집니다. 이때 회전을 적용해 구조를 다시 바꿉니다.
회전은 트리를 다시 정렬하는 과정이 아니라, 노드들을 위아래로 재배치해 높이를 조정하는 지역적(local) 연산입니다. 중요한 점은 회전 후에도 in-order 순서는 그대로 보존된다는 것입니다.
즉 AVL은 “정렬을 유지하면서 높이를 줄이는” 구조이고, 이 두 조건을 동시에 만족시키는 핵심 도구가 rotation입니다.
AVL Operation Model
1) BST 규칙으로 탐색한다
2) 삽입 또는 삭제를 수행한다
3) 조상 방향으로 올라가며 높이 차이를 확인한다
4) 불균형이 생긴 지점에서 rotation 으로 재균형한다
5) BST property 와 AVL balancing rule 을 함께 복구한다핵심 불변식
| 불변식 | 의미 | 실무 해석 |
|---|---|---|
| BST Property | 왼쪽 서브트리 키 < 현재 키 < 오른쪽 서브트리 키 | 검색과 중위 순 정렬 순회가 가능해짐 |
| AVL Balancing Rule | 각 노드의 두 서브트리 높이 차이 ≤ 1 | 트리 높이가 지나치게 커지는 것을 방지 |
| Balance Factor | 왼쪽/오른쪽 높이 차이를 요약하는 값 | 보통 -1, 0, +1 범위를 유지해야 안정적 |
| Rotation Safety | 회전 후에도 중위 순서가 보존됨 | 검색 구조를 깨뜨리지 않고 높이만 조정 가능 |
즉 AVL 디버깅은 “값 비교 규칙이 맞는가”와 “높이 차이 규칙이 맞는가”를 동시에 보는 일입니다. 둘 중 하나만 지켜도 충분하지 않습니다.
기본 구조
avl-tree/
├── root
└── node
├── key
├── left
├── right
└── height or balance-factor metadata일반 BST와 가장 큰 차이는 노드가 균형 정보를 함께 관리한다는 점입니다. 구현에 따라 높이를 저장하기도 하고, balance factor만 저장하기도 합니다.
이 메타데이터 덕분에 삽입·삭제 후 어느 지점이 무너졌는지 빠르게 확인할 수 있고, 필요한 회전도 지역적으로 적용할 수 있습니다.
기본 구현
class Node {
int key;
int height;
Node left;
Node right;
Node(int key) {
this.key = key;
this.height = 1;
}
}
int height(Node n) {
return n == null ? 0 : n.height;
}
int balance(Node n) {
return n == null ? 0 : height(n.left) - height(n.right);
}
void updateHeight(Node n) {
n.height = 1 + Math.max(height(n.left), height(n.right));
}
Node rotateRight(Node y) {
Node x = y.left;
Node t2 = x.right;
x.right = y;
y.left = t2;
updateHeight(y);
updateHeight(x);
return x;
}
Node rotateLeft(Node x) {
Node y = x.right;
Node t2 = y.left;
y.left = x;
x.right = t2;
updateHeight(x);
updateHeight(y);
return y;
}
Node insert(Node node, int key) {
if (node == null) return new Node(key);
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node;
}
updateHeight(node);
int bf = balance(node);
if (bf > 1 && key < node.left.key) return rotateRight(node); // LL
if (bf < -1 && key > node.right.key) return rotateLeft(node); // RR
if (bf > 1 && key > node.left.key) { // LR
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (bf < -1 && key < node.right.key) { // RL
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}패턴 1. 회전은 정렬을 깨지 않고 높이를 줄인다
NIST는 left rotation을 어떤 노드를 아래 왼쪽으로 밀어 내리고 그 오른쪽 자식이 위로 올라오는 연산으로, right rotation은 그 대칭 구조로 설명합니다.
중요한 점은 회전이 BST 순서를 깨뜨리지 않는다는 것입니다. 그래서 검색 규칙은 유지하면서도, 높이 차이가 큰 구간만 국소적으로 조정할 수 있습니다.
실무에서는 이 불균형을 보통 LL, RR, LR, RL 네 패턴으로 나누어 설명합니다. 하지만 본질은 이름보다도 단일 회전이 필요한지, 두 번의 회전이 필요한지에 있습니다.
Rotation Patterns
- single rotation
- left rotation
- right rotation
- double rotation
- left-right
- right-left패턴 2. 삽입은 BST 삽입 + 재균형
삽입 자체는 BST와 같습니다. 새 키와 비교를 반복해 적절한 leaf 위치를 찾고, 그 자리에 노드를 붙입니다.
차이는 그 이후입니다. 삽입으로 인해 어떤 조상 노드의 높이 차이가 2 이상 벌어질 수 있으므로, 삽입 지점에서 루트 방향으로 올라가며 높이와 balance를 갱신하고 필요하면 회전합니다.
즉 AVL 삽입은 “검색 규칙”과 “균형 회복 규칙”이 결합된 연산으로 보는 편이 맞습니다.
패턴 3. 삭제는 더 조심스럽다
삭제의 첫 단계는 여전히 BST 삭제입니다. leaf 제거, 자식 하나 splice, successor 치환 같은 기본 구조는 BST와 같습니다.
하지만 삭제는 높이를 줄일 수 있기 때문에, 불균형이 부모와 더 위 조상으로 연쇄적으로 퍼질 수 있습니다. 그래서 AVL 삭제는 삽입보다 구현 난이도가 더 높게 느껴지는 경우가 많습니다.
즉 삭제는 “노드를 뺀다”보다 “노드를 뺀 뒤에도 AVL invariant가 위로 계속 유지되는지 확인한다”로 이해하는 편이 더 정확합니다.
한계와 주의점
AVL의 장점은 높이를 강하게 제어한다는 점입니다. 하지만 그만큼 각 노드에 높이 또는 balance 정보를 유지해야 하고, 수정 연산마다 회전 여부를 판단해야 합니다.
즉 AVL은 “빠른 검색을 공짜로 얻는 구조”가 아니라, 더 복잡한 유지 비용을 지불하고 최악의 높이를 관리하는 구조입니다.
그래서 실무에서는 직접 AVL을 구현하기보다, 언어 또는 라이브러리가 제공하는 검증된 balanced tree 계열 구조를 사용하는 경우가 많습니다.
- BST property 와 AVL balancing rule 을 동시에 지켜야 함
- 회전 후 높이 갱신 순서를 잘못 잡으면 구조가 쉽게 틀어짐
- 삭제는 삽입보다 위쪽 조상까지 영향이 퍼질 가능성이 큼
- 직접 구현 시 parent/root 링크 갱신 실수가 매우 흔함
자주 하는 실수
- AVL이면 아무 회전이나 해도 된다고 생각함
- BST property 만 맞으면 AVL도 자동으로 맞는다고 착각함
- 회전 후 height 또는 balance factor 재계산을 빼먹음
- 삭제를 단순 BST 삭제로 끝내고 위쪽 재균형을 놓침
- 중위 순회 결과 검증 없이 balance 값만 보고 맞다고 판단함
- 루트가 회전으로 바뀌는 케이스를 놓침
실무 루틴
- 먼저 plain BST 로 충분한지, 아니면 worst-case 로그 높이 가 필요한지 판단한다.
- 검색뿐 아니라 predecessor, successor, ordered traversal 같은 정렬 질의 가 중요한지 본다.
- 직접 구현한다면 inorder 검증, height 검증, balance 검증 테스트를 먼저 만든다.
- 회전 함수는 단독으로 검증하고, insert/delete 와 분리해서 테스트한다.
- 삭제 케이스는 leaf, one child, two children, root replacement 를 분리해 점검한다.
- 실서비스에서는 직접 구현보다 검증된 라이브러리 구조를 우선 검토한다.
디버깅
점검 체크리스트
- inorder 결과가 정렬 순인가
- 모든 노드의 높이 차이가 1 이하인가
- 회전 후 서브트리 루트 교체가 제대로 반영됐는가
- height / balance 값이 최신 상태인가
- 삭제 뒤 조상 방향 재균형이 빠지지 않았는가요약
- ✅ AVL 트리는 height-balanced binary search tree 다.
- ✅ 각 노드의 두 서브트리 높이 차이는 최대 1이어야 한다.
- ✅ 검색은 BST와 같고, 수정 뒤에만 rotation 으로 균형을 복구한다.
- ✅ 회전은 BST의 in-order 순서를 보존한 채 높이를 조정하는 국소 연산이다.
- ✅ lookup, insert, delete 는 로그 높이 범위의 성능을 기대할 수 있다.
- ✅ 삽입은 BST 삽입 + 재균형, 삭제는 BST 삭제 + 조상 방향 재균형으로 이해하는 편이 좋다.
- ✅ AVL는 plain BST보다 안정적이지만 구현 복잡도는 더 높다.
- ✅ 직접 구현할 때는 회전 코드보다 불변식 검증 코드를 먼저 준비하는 편이 안전하다.