AVL Tree(AVL 트리)는 이진 탐색 트리(BST)의 한 종류로, 삽입/삭제 이후에도 트리의 높이가 한쪽으로 치우치지 않도록 자동으로 균형을 유지하는 자기 균형(Self-Balancing) 트리입니다. 일반적인 BST는 입력 순서가 특정 패턴(오름차순/내림차순 등)을 가지면 트리가 한쪽으로 길게 늘어져 탐색/삽입/삭제가 O(N)까지 떨어질 수 있습니다. 반면 AVL Tree는 불균형을 감지하면 회전(Rotation)으로 구조를 조정하여, 탐색/삽입/삭제를 항상 O(log N) 범위로 유지하는 것이 목적입니다.
한쪽으로 치우친 트리 (높이 ≈ n)
|
균형에 가까운 트리 (높이 ≈ log n)
|
이번 글에서는 AVL Tree의 개념과 동작 원리를 정리하고, C#으로 AVL Tree를 직접 구현한 뒤(Insert/Remove/Contains/순회/Validate 포함), Unity 테스트 코드로 균형 유지 동작을 확인해 보겠습니다.
※ 트리(Tree)는 사이클이 없는 연결 그래프로 볼 수 있으며, 이진 트리는 각 노드가 최대 2개의 자식(Left/Right)을 갖습니다. BST는 여기에 “왼쪽은 작고 오른쪽은 크다”라는 정렬 규칙을 더한 구조입니다. AVL Tree는 BST에 균형 규칙을 추가하여, 삽입/삭제 이후에도 트리 높이가 한쪽으로 치우치지 않도록 제한하는 것이 목적입니다.
1. AVL Tree의 구조와 동작 방식
AVL Tree는 “정렬된 트리”라는 BST의 장점은 유지하면서, “입력 순서가 나쁘면 트리가 망가진다”는 단점을 회전으로 해결하는 자료구조입니다. 이 섹션에서는 코드가 아니라 개념 관점에서 AVL Tree가 삽입/삭제를 어떻게 처리하며 스스로를 조정하는지를 설명합니다.
- Node: 트리를 구성하는 단위이며 Key(값)와 Left/Right(자식), Height(서브트리 높이)를 가집니다.
- Root: 트리의 최상단 노드입니다.
- Parent / Child: 부모-자식 관계를 갖는 인접 노드입니다.
- Leaf: 자식이 없는 노드입니다(Left/Right가 모두 null).
- Sibling(형제 노드): 같은 부모를 가진 노드입니다.
- Depth: Root에서 특정 노드까지의 거리입니다.
- Height: 특정 노드에서 가장 깊은 Leaf까지의 최대 거리입니다.
※ 트리에 대한 기본적인 내용은 Unity 개발자를 위한 C# Tree(트리) 구현을 참고하세요.
AVL Tree가 강제하는 균형 규칙은 간단합니다. 모든 노드에 대해 (왼쪽 서브트리 높이 - 오른쪽 서브트리 높이)가 -1, 0, 1 중 하나여야 합니다. 이 값을 균형 인수(Balance Factor)라고 부르며, 절댓값이 2 이상이 되는 순간 “불균형”으로 판단합니다.
1.1 삽입 시 동작(개념)
삽입 자체는 BST와 동일합니다. 새 값은 Root부터 비교를 반복하며, 작은 값이면 왼쪽, 큰 값이면 오른쪽으로 내려가 Leaf 위치에 붙습니다. AVL Tree의 핵심은 그 다음입니다. 삽입이 끝나면 삽입 지점에서부터 위로 올라가며 각 노드의 높이와 균형을 다시 계산합니다. 만약 어떤 노드에서 불균형이 발견되면, 그 노드를 기준으로 회전을 수행하여 구조를 재배치합니다.
예를 들어, 값이 30 → 20 → 10 순서로 삽입되었다고 가정하겠습니다. BST로만 처리하면 트리는 다음처럼 왼쪽으로 길게 늘어집니다(이 구조는 예시이며, 개념 이해가 목적입니다).
30
/
20
/
10
이 상태에서 노드 30의 왼쪽 높이가 오른쪽보다 2 이상 커지므로 불균형입니다. AVL Tree는 “왼쪽-왼쪽(LL)” 형태의 불균형임을 판단하고, 오른쪽 회전으로 20을 위로 올립니다. 결과는 다음과 같습니다.
30 20
/ → / \
20 10 30
/
10
중요한 점은, 회전 이후에도 BST 정렬 규칙(왼쪽 < 부모 < 오른쪽)은 그대로 유지된다는 것입니다. 단지 부모-자식 연결 관계만 바뀌어, 트리 높이가 줄고 균형이 복구됩니다.
1.2 삭제 시 동작(개념)
삭제도 먼저 BST 규칙으로 처리합니다. 삭제 대상 노드를 찾은 뒤 자식 수에 따라 (1) Leaf면 제거, (2) 자식이 하나면 자식을 올림, (3) 자식이 둘이면 inorder successor(오른쪽 서브트리의 최소값)로 값을 치환한 뒤 successor를 제거합니다.
AVL Tree의 핵심은 삭제 이후입니다. 삭제로 인해 어떤 서브트리의 높이가 줄어들면, 삭제 지점에서부터 위로 올라가며 각 노드의 Height를 다시 계산하고, 좌/우 높이 차이(Balance Factor)가 -1, 0, 1 범위를 벗어나는 순간 회전으로 복구합니다.
예시 1) Leaf 삭제로 인해 불균형이 생기는 경우
아래 트리는 AVL 조건을 만족하는 상태라고 가정하겠습니다(이 구조는 예시이며, 개념 이해가 목적입니다).
30
/ \
20 40
/ \
10 (25)
/
5
여기서 Leaf 노드 25를 삭제한다고 해 보겠습니다. BST 규칙대로 25는 자식이 없으므로 바로 제거됩니다.
30
/ \
20 40
/
10
/
5
이제 중요한 것은 “삭제된 노드의 부모부터” 영향을 받는다는 점입니다. 삭제 직후에는 20의 오른쪽 서브트리가 사라지면서 20의 균형이 달라집니다.
- 삭제 전: 20의 Left 높이는 2, Right 높이는 1 (Balance Factor = +1)
- 삭제 후: 20의 Left 높이는 2, Right 높이는 0 (Balance Factor = +2)
이 시점에서 20의 Balance Factor가 +2가 되어(왼쪽 높이가 오른쪽보다 2 이상 큼), AVL은 불균형으로 판단하고 회전을 수행합니다. 현재 불균형은 “왼쪽-왼쪽(LL)” 형태이므로 Right Rotation으로 복구됩니다.
30 30
/ \ / \
20 40 → 10 40
/ / \
10 5 20
/
5
삭제가 끝난 뒤에도 트리가 균형을 유지하는 이유는, 이처럼 삭제 지점에서 위로 올라가며 불균형을 발견하는 즉시 회전으로 복구하기 때문입니다.
예시 2) 자식 2개 노드 삭제(치환 후 삭제) + 균형 복구
이번에는 자식이 둘인 노드를 삭제하는 예시를 보겠습니다. 아래 트리에서 20을 삭제한다고 가정하겠습니다.
30
/ \
(20) 40
/ \
10 25
/
22
20은 자식이 2개이므로, BST 삭제 규칙에 따라 inorder successor를 찾습니다. 즉, 20의 오른쪽 서브트리(25)에서 가장 작은 값(22)을 successor로 선택합니다.
- 1) 20의 Key를 22로 치환
- 2) 원래 위치에 있던 successor(22) 노드를 실제로 제거
치환 이후의 구조(아직 successor 제거 전)는 다음처럼 “값만 바뀐 상태”입니다.
30
/ \
[22] 40
/ \
10 25
/
22 (이 노드를 제거해야 함)
이제 오른쪽 서브트리에서 successor 노드(Leaf 또는 1자식)를 제거합니다. 이때 실제로 높이가 줄어드는 지점은 successor가 제거된 위치이며, 그 지점부터 위로 올라가며 Height와 Balance Factor가 다시 계산됩니다.
즉, “자식 2개 삭제”는 겉으로는 20을 지우는 것처럼 보이지만, 내부적으로는 오른쪽 서브트리에서 한 번 더 Remove가 발생하는 구조입니다. AVL Tree는 이 두 번째 제거 때문에 생기는 높이 변화까지 포함해, 필요하면 회전을 수행해 균형을 복구합니다.
정리하면, AVL Tree의 삭제는 다음의 특징을 가집니다.
- 삭제 자체는 BST 규칙(0/1/2 자식 케이스)을 그대로 따른다
- 삭제 이후 “높이 감소”가 발생할 수 있으므로, 삭제 지점에서 위로 균형을 다시 검사한다
- 불균형(-2 또는 +2)이 발견되면 회전으로 즉시 복구한다
※ 동작을 시각적으로 확인해보기
아래 링크는 AVL Tree의 삽입 및 삭제 과정에서 발생하는 회전(Rotation)과 균형 복구 과정을 단계별로 시각화해 주는 도구입니다. Balance Factor 변화와 함께 LL / LR / RL / RR 회전이 언제, 왜 발생하는지를 직관적으로 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
2. AVL Tree가 활용되는 대표적인 사례
AVL Tree는 이론적으로는 매우 강력한 자료구조이지만, Unity 게임 개발이나 일반적인 클라이언트 로직에서 직접 구현해 사용하는 경우는 많지 않습니다. 대부분의 상황에서는 List 정렬, Dictionary, PriorityQueue 같은 더 단순한 자료구조로 충분한 경우가 많기 때문입니다.
그럼에도 불구하고 AVL Tree가 의미를 가지는 경우는 분명히 존재합니다. 핵심은 “정렬된 상태를 유지해야 하고, 삽입과 삭제가 반복되며, 최악의 성능(O(N))을 피해야 하는 경우”입니다.
- 정렬된 데이터가 항상 필요하고, 갱신이 잦은 경우
데이터가 한 번 정렬되고 끝나는 구조라면 List 정렬이 더 단순합니다. 하지만 값이 계속 추가·삭제되면서도, 언제든지 정렬된 순서로 순회(InOrder)해야 하는 경우라면 AVL Tree 같은 균형 트리가 이론적으로 적합한 선택이 됩니다. - 범위 기반 조회가 자주 필요한 경우
“이 값 이상, 이 값 이하만 처리한다” 같은 범위 조건은 해시 기반 구조(HashSet, Dictionary)에서는 자연스럽지 않습니다. AVL Tree는 BST 규칙을 유지하므로, 특정 값 기준으로 좌우 서브트리를 나눠 탐색하며 범위를 좁히는 로직을 구성하기 쉽습니다. - 입력 패턴이 예측 불가능하고, 최악 성능을 피해야 하는 경우
일반 BST는 입력 순서에 따라 한쪽으로 치우쳐 O(N)까지 성능이 떨어질 수 있습니다. AVL Tree는 삽입·삭제 이후에도 회전으로 균형을 강제하므로, 항상 O(log N) 범위를 유지해야 하는 상황에서 안정적인 선택지가 됩니다. - 다른 자료구조 선택이 애매한 중간 지점
PriorityQueue는 “최솟값/최댓값 하나를 빠르게 꺼내는 것”에는 적합하지만, 전체 정렬 순서를 유지하거나 범위 조회에는 부적합합니다. Dictionary나 HashSet은 빠르지만 정렬 개념이 없습니다. 이런 구조들 사이에서 ‘정렬 + 안정적인 성능’이 동시에 필요한 경우, AVL Tree는 하나의 대안이 될 수 있습니다.
정리하면, AVL Tree는 “자주 쓰는 만능 자료구조”라기보다는, 요구사항이 명확히 맞아떨어질 때 선택하는 특화된 도구에 가깝습니다. 이 글에서 AVL Tree를 직접 구현해 보는 목적 역시, 실제 프로젝트에 바로 쓰기보다는 균형 트리가 왜 필요하고, 어떻게 동작하는지를 정확히 이해하는 데에 있습니다.
3. AVL Tree가 제공하는 기능(구현 기준)
이번에 구현할 AvlTree<T>는 다음 기능을 제공합니다.
- Count
현재 저장된 노드 개수를 반환합니다(중복 없음). - Insert
키를 삽입합니다. 동일 키가 있으면 삽입하지 않습니다. - Remove
키를 삭제합니다. 삭제되면 true, 없으면 false를 반환합니다. - Contains
키 존재 여부를 확인합니다. - Min / Max
최솟값/최댓값을 반환합니다. - PreOrder / InOrder / PostOrder
비재귀(스택 기반) 순회를 제공합니다. - Validate
Height 정합성과 균형 조건을 검증합니다(디버그용).
4. AVL Tree의 내부 동작 방식
이 섹션에서는 “개념”이 아니라, 구현 관점에서 내부가 어떤 값들을 유지하고 어떤 순서로 호출되는지를 설명합니다. AVL Tree에서 성능과 정확성을 좌우하는 포인트는 크게 3가지입니다.
- 각 노드가 자신의 Height를 유지한다
- 불균형을 Balance Factor로 판별한다
- 불균형이 생기면 회전으로 즉시 복구한다
4.1 Height 저장 방식
이 구현은 Height를 null=0, leaf=1로 두는 방식입니다. 따라서 어떤 노드의 Height는 “자식 높이 중 큰 값 + 1”로 계산됩니다. 이 규칙만 지키면, 간선 기준(leaf=0)인지 노드 기준(leaf=1)인지는 균형 판단에 큰 차이가 없습니다. 중요한 것은 좌/우 높이의 차이입니다.
private class Node
{
public T Key;
public Node Left;
public Node Right;
public int Height;
public Node(T key)
{
Key = key;
Height = 1; // leaf height = 1 (노드 단위 높이, null=0)
}
}
private static int Height(Node n)
{
return n?.Height ?? 0; // null이면 0
}
private static void UpdateHeight(Node n)
{
int hl = Height(n.Left);
int hr = Height(n.Right);
n.Height = (hl > hr ? hl : hr) + 1;
}
높이 갱신 규칙은 다음과 같습니다.
Height(n) = max(Height(n.Left), Height(n.Right)) + 1
null이면 0, leaf이면 1
4.2 Balance Factor 계산
Balance Factor는 아래처럼 계산합니다. AVL Tree는 모든 노드에서 이 값이 -1, 0, 1 범위여야 합니다.
private static int BalanceFactor(Node n)
{
return Height(n.Left) - Height(n.Right);
}
정리하면 다음 식으로 볼 수 있습니다.
BalanceFactor(n) = Height(n.Left) - Height(n.Right)
4.3 Insert 코드 흐름을 단계별로 보기
Insert는 크게 2단계로 나뉩니다.
- 1단계: BST 삽입 - 비교기로 내려가며 null 자리에 새 노드를 만든다
- 2단계: 복구 - 삽입이 발생했다면 돌아오면서 UpdateHeight → Rebalance
1) BST 삽입(재귀 하강) 코드
public void Insert(T key)
{
_root = Insert(_root, key, out bool inserted);
if (inserted)
{
++Count;
}
}
private Node Insert(Node root, T key, out bool inserted)
{
if (root == null)
{
inserted = true;
return new Node(key);
}
int c = _cmp.Compare(key, root.Key);
if (c == 0)
{
inserted = false; // 중복 불가
return root;
}
else if (c < 0)
{
root.Left = Insert(root.Left, key, out inserted);
}
else
{
root.Right = Insert(root.Right, key, out inserted);
}
// 2) 복구(Height 갱신 + Rebalance)
if (inserted)
{
UpdateHeight(root);
root = Rebalance(root);
}
return root;
}
핵심은 재귀가 되돌아올 때(부모로 복귀할 때)마다 UpdateHeight와 Rebalance가 호출된다는 점입니다. 이 구조 덕분에 “삽입 지점부터 위로 올라가며 균형을 검사/복구”가 자연스럽게 구현됩니다.
예시 연결: 30 → 20 → 10을 삽입하면, 재귀는 10을 leaf로 만든 뒤 되돌아오며 20, 30 순서로 Height를 갱신합니다. 30에서 BalanceFactor가 +2가 되어 Rebalance가 회전을 수행합니다. 회전이 발생하면 해당 서브트리의 루트가 변경될 수 있습니다. Insert는 이러한 상황을 처리하기 위해, 항상 “해당 서브트리의 최종 루트”를 반환하도록 설계되어 있습니다. 이 반환값을 부모 노드가 다시 연결함으로써, 회전에 따른 구조 변경이 상위 노드까지 자연스럽게 전파됩니다.
4.4 Remove 코드 흐름을 단계별로 보기
Remove는 먼저 BST 규칙으로 노드를 찾고, 자식 수에 따라 제거 방식이 달라집니다. 구현에서는 아래 흐름을 가집니다.
- 대상이 없으면 removed=false
- 대상을 찾으면 removed=true
- 자식 0/1개면 child를 반환(연결을 끊음)
- 자식 2개면 inorder successor로 Key를 치환하고 successor를 제거
- 그 뒤 UpdateHeight → Rebalance로 균형 복구
Remove 코드
public bool Remove(T key)
{
_root = Remove(_root, key, out bool removed);
if (removed)
{
--Count;
}
return removed;
}
private Node Remove(Node root, T key, out bool removed)
{
if (root == null)
{
removed = false;
return null;
}
int c = _cmp.Compare(key, root.Key);
if (c < 0)
{
root.Left = Remove(root.Left, key, out removed);
}
else if (c > 0)
{
root.Right = Remove(root.Right, key, out removed);
}
else
{
// found
removed = true;
if (root.Left == null || root.Right == null)
{
Node child = root.Left ?? root.Right;
return child; // height는 caller에서 갱신
}
else
{
// two children: inorder successor로 치환 후 제거
Node succ = root.Right;
while (succ.Left != null)
{
succ = succ.Left;
}
root.Key = succ.Key;
root.Right = Remove(root.Right, succ.Key, out _);
}
}
// 삭제로 인해 높이가 변할 수 있으므로 항상 갱신/복구 필요
UpdateHeight(root);
return Rebalance(root);
}
삭제가 까다로운 이유는 “높이 감소”가 위쪽에 연쇄적으로 영향을 주기 때문입니다. 코드에서도 삭제 처리 후 무조건 UpdateHeight와 Rebalance가 실행되도록 구성되어 있습니다.
4.5 회전(Rotation) 방식
Rebalance는 BalanceFactor를 기준으로 네 가지 케이스(LL/LR/RR/RL)를 구분하고, RotateLeft, RotateRight를 조합해 균형을 복구합니다.
Rebalance 코드(케이스 분기)
private Node Rebalance(Node n)
{
int bf = BalanceFactor(n);
// LL case
if (bf > 1 && BalanceFactor(n.Left) >= 0)
{
return RotateRight(n);
}
// LR case
if (bf > 1 && BalanceFactor(n.Left) < 0)
{
n.Left = RotateLeft(n.Left);
return RotateRight(n);
}
// RR case
if (bf < -1 && BalanceFactor(n.Right) <= 0)
{
return RotateLeft(n);
}
// RL case
if (bf < -1 && BalanceFactor(n.Right) > 0)
{
n.Right = RotateRight(n.Right);
return RotateLeft(n);
}
return n;
}
1) LL 케이스: Right Rotation
30(y) 20
/ → / \
20(x) 10 30
/
10
Right Rotation 코드
private Node RotateRight(Node y) // y = 30
{
Node x = y.Left; // x = 20
Node t2 = x.Right; // t2 = null
x.Right = y; // y를 x의 오른쪽 자식으로
y.Left = t2; // t2 = y의 왼쪽 자식으로
UpdateHeight(y);
UpdateHeight(x);
return x;
}
2) RR 케이스: Left Rotation
10(x) 20
\ → / \
20(y) 10 30
\
30
Left Rotation 코드
private Node RotateLeft(Node x) // x = 10
{
Node y = x.Right; // y = 20
Node t2 = y.Left; // t2 = null
y.Left = x; // x를 y의 왼쪽 자식으로
x.Right = t2; // t2를 x의 오른쪽 자식으로
UpdateHeight(x);
UpdateHeight(y);
return y;
}
3) LR 케이스: Left Rotation(Left Child) → Right Rotation
30 30 25
/ → / → / \
20 25 20 30
\ /
25 20
LR은 코드에서 다음 순서로 수행됩니다.
// LR case
if (bf > 1 && BalanceFactor(n.Left) < 0)
{
n.Left = RotateLeft(n.Left);
return RotateRight(n);
}
4) RL 케이스: Right Rotation(Right Child) → Left Rotation
10 10 15
\ → \ → / \
20 15 10 20
/ \
15 20
RL은 코드에서 다음 순서로 수행됩니다.
// RL case
if (bf < -1 && BalanceFactor(n.Right) > 0)
{
n.Right = RotateRight(n.Right);
return RotateLeft(n);
}5. C# 기반 AVL Tree 직접 구현 코드
아래는 AvlTree<T> 전체 코드입니다. 핵심은 Insert/Remove 이후 UpdateHeight와 Rebalance를 수행하여 AVL 균형 조건을 유지하는 부분입니다.
using System;
using BCL = System.Collections.Generic; // BCL - Base Class Library
namespace Daebak.Common.Collections
{
/// <summary>
/// AVL Tree (Self-Balancing BST)
/// - Insert / Remove: O(log N)
/// - Search: O(log N)
///
/// 핵심 아이디어:
/// - 모든 노드에 대해 (왼쪽 서브트리 높이 - 오른쪽 서브트리 높이) = -1, 0, 1 을 유지합니다.
/// - 삽입/삭제 이후 높이를 갱신하고, 불균형이 생기면 회전(Rotate)으로 균형을 복구합니다.
/// </summary>
public class AvlTree<T>
{
/// <summary>
/// 트리의 노드
/// - Key: 저장 값
/// - Left/Right: 자식 포인터
/// - Height: 이 노드를 루트로 하는 서브트리의 높이(leaf = 1)
/// </summary>
private class Node
{
public T Key;
public Node Left;
public Node Right;
public int Height;
public Node(T key)
{
Key = key;
Height = 1; // leaf height = 1 (노드 단위 높이, null=0)
}
}
private Node _root; // 트리의 루트 노드
private readonly BCL.IComparer<T> _cmp; // 키 비교자(정렬 기준)
public int Count { get; private set; } // 중복 없이 저장된 노드 개수
public AvlTree(BCL.IComparer<T> comparer = null)
{
// comparer가 없으면 기본 비교자를 사용합니다.
// T는 IComparable<T>를 구현했거나 Comparer<T>.Default가 처리 가능해야 합니다.
_cmp = comparer ?? BCL.Comparer<T>.Default;
}
/// <summary>
/// 트리를 비웁니다. (모든 노드 해제는 GC 대상)
/// </summary>
public void Clear()
{
_root = null;
Count = 0;
}
/// <summary>
/// key가 트리에 존재하는지 확인합니다. (BST 탐색)
/// </summary>
public bool Contains(T key)
{
Node n = _root;
while (n != null)
{
int c = _cmp.Compare(key, n.Key);
if (c == 0)
{
return true;
}
else if (c < 0)
{
// key < n.Key 이면 왼쪽으로
n = n.Left;
}
else
{
// key > n.Key 이면 오른쪽으로
n = n.Right;
}
}
return false;
}
/// <summary>
/// key를 삽입합니다. (중복은 허용하지 않음)
/// - 삽입 후, 높이 갱신 및 Rebalance로 AVL 성질을 유지합니다.
/// </summary>
public void Insert(T key)
{
_root = Insert(_root, key, out bool inserted);
if (inserted)
{
++Count;
}
}
/// <summary>
/// key를 삭제합니다.
/// - 삭제 후, 높이 갱신 및 Rebalance로 AVL 성질을 유지합니다.
/// </summary>
public bool Remove(T key)
{
_root = Remove(_root, key, out bool removed);
if (removed)
{
--Count;
}
return removed;
}
/// <summary>
/// 전위 순회(PreOrder): Root -> Left -> Right
/// </summary>
public BCL.IEnumerable<T> PreOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> st = new();
st.Push(_root);
while (st.Count > 0)
{
Node n = st.Pop();
yield return n.Key;
if (n.Right != null)
{
st.Push(n.Right);
}
if (n.Left != null)
{
st.Push(n.Left);
}
}
}
/// <summary>
/// 중위 순회(InOrder): Left -> Root -> Right
/// </summary>
public BCL.IEnumerable<T> InOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> st = new();
Node cur = _root;
while (st.Count > 0 || cur != null)
{
if (cur != null)
{
st.Push(cur);
cur = cur.Left;
}
else
{
cur = st.Pop();
yield return cur.Key;
cur = cur.Right;
}
}
}
/// <summary>
/// 후위 순회(PostOrder): Left -> Right -> Root
/// </summary>
public BCL.IEnumerable<T> PostOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> s1 = new();
BCL.Stack<Node> s2 = new();
s1.Push(_root);
while (s1.Count > 0)
{
Node n = s1.Pop();
s2.Push(n);
if (n.Left != null)
{
s1.Push(n.Left);
}
if (n.Right != null)
{
s1.Push(n.Right);
}
}
while (s2.Count > 0)
{
yield return s2.Pop().Key;
}
}
public T Min()
{
if (_root == null)
{
throw new InvalidOperationException("Tree is empty.");
}
Node n = _root;
while (n.Left != null)
{
n = n.Left;
}
return n.Key;
}
public T Max()
{
if (_root == null)
{
throw new InvalidOperationException("Tree is empty.");
}
Node n = _root;
while (n.Right != null)
{
n = n.Right;
}
return n.Key;
}
/// <summary>
/// Debug: AVL 속성 검증
/// </summary>
public bool Validate(out string reason)
{
try
{
ValidateNode(_root);
reason = "OK";
return true;
}
catch (Exception e)
{
reason = e.Message;
return false;
}
}
// -------- Internal Helpers --------
private Node Insert(Node root, T key, out bool inserted)
{
if (root == null)
{
inserted = true;
return new Node(key);
}
int c = _cmp.Compare(key, root.Key);
if (c == 0)
{
inserted = false;
return root;
}
else if (c < 0)
{
root.Left = Insert(root.Left, key, out inserted);
}
else
{
root.Right = Insert(root.Right, key, out inserted);
}
if (inserted)
{
UpdateHeight(root);
root = Rebalance(root);
}
return root;
}
private Node Remove(Node root, T key, out bool removed)
{
if (root == null)
{
removed = false;
return null;
}
int c = _cmp.Compare(key, root.Key);
if (c < 0)
{
root.Left = Remove(root.Left, key, out removed);
}
else if (c > 0)
{
root.Right = Remove(root.Right, key, out removed);
}
else
{
removed = true;
if (root.Left == null || root.Right == null)
{
Node child = root.Left ?? root.Right;
return child;
}
else
{
Node succ = root.Right;
while (succ.Left != null)
{
succ = succ.Left;
}
root.Key = succ.Key;
root.Right = Remove(root.Right, succ.Key, out _);
}
}
UpdateHeight(root);
return Rebalance(root);
}
private static int Height(Node n)
{
return n?.Height ?? 0;
}
private static int BalanceFactor(Node n)
{
return Height(n.Left) - Height(n.Right);
}
private static void UpdateHeight(Node n)
{
int hl = Height(n.Left);
int hr = Height(n.Right);
n.Height = (hl > hr ? hl : hr) + 1;
}
private Node Rebalance(Node n)
{
int bf = BalanceFactor(n);
if (bf > 1 && BalanceFactor(n.Left) >= 0)
{
return RotateRight(n);
}
if (bf > 1 && BalanceFactor(n.Left) < 0)
{
n.Left = RotateLeft(n.Left);
return RotateRight(n);
}
if (bf < -1 && BalanceFactor(n.Right) <= 0)
{
return RotateLeft(n);
}
if (bf < -1 && BalanceFactor(n.Right) > 0)
{
n.Right = RotateRight(n.Right);
return RotateLeft(n);
}
return n;
}
private Node RotateRight(Node y)
{
Node x = y.Left;
Node t2 = x.Right;
x.Right = y;
y.Left = t2;
UpdateHeight(y);
UpdateHeight(x);
return x;
}
private Node RotateLeft(Node x)
{
Node y = x.Right;
Node t2 = y.Left;
y.Left = x;
x.Right = t2;
UpdateHeight(x);
UpdateHeight(y);
return y;
}
private int ValidateNode(Node n)
{
if (n == null)
{
return 0;
}
int hl = ValidateNode(n.Left);
int hr = ValidateNode(n.Right);
int expected = Math.Max(hl, hr) + 1;
if (n.Height != expected)
{
throw new Exception($"Height mismatch at {n.Key}: node={n.Height}, calc={expected}");
}
int bf = hl - hr;
if (bf < -1 || bf > 1)
{
throw new Exception($"Unbalanced at {n.Key}: bf={bf}");
}
return expected;
}
}
}6. Unity 환경에서 테스트 해보기
Unity에서 삽입/삭제 이후에도 트리가 균형 상태를 유지하는지 확인하기 위해 Validate를 사용합니다. 또한 InOrder 출력이 항상 오름차순인지 확인하면 BST 정렬 규칙이 유지되는지도 함께 검증할 수 있습니다.
using UnityEngine;
using Daebak.Common.Collections;
public class Test_AvlTree : MonoBehaviour
{
void Start()
{
AvlTree<int> tree = new();
Debug.Log("=== AVL Tree 테스트 시작 ===");
// 회전이 발생하기 쉬운 삽입 순서
int[] insert = { 30, 20, 10, 25, 40, 50, 22, 5, 35 };
foreach (int v in insert)
{
tree.Insert(v);
}
Debug.Log($"Count = {tree.Count}");
Debug.Log("InOrder(오름차순):");
foreach (int v in tree.InOrder())
{
Debug.Log(v);
}
Debug.Log($"Contains(22) = {tree.Contains(22)}");
Debug.Log($"Contains(99) = {tree.Contains(99)}");
Debug.Log($"Min = {tree.Min()}");
Debug.Log($"Max = {tree.Max()}");
Debug.Log($"Remove(20) = {tree.Remove(20)}");
Debug.Log($"Remove(20) (이미 삭제됨) = {tree.Remove(20)}");
Debug.Log("After Remove InOrder:");
foreach (int v in tree.InOrder())
{
Debug.Log(v);
}
if (tree.Validate(out string reason))
{
Debug.Log("AVL Valid: " + reason);
}
else
{
Debug.LogError("AVL Invalid: " + reason);
}
Debug.Log("=== AVL Tree 테스트 종료 ===");
}
}
실행 결과
=== AVL Tree 테스트 시작 ===
Count = 9
InOrder(오름차순):
5
10
20
22
25
30
35
40
50
Contains(22) = True
Contains(99) = False
Min = 5
Max = 50
Remove(20) = True
Remove(20) (이미 삭제됨) = False
After Remove InOrder:
5
10
22
25
30
35
40
50
AVL Valid: OK
=== AVL Tree 테스트 종료 ===
마무리
AVL Tree는 “정렬된 트리”라는 BST의 장점을 유지하면서, 삽입/삭제 이후에도 회전으로 균형을 강제해 항상 안정적인 O(log N) 성능을 제공하는 자료구조입니다. 입력 순서가 예측 불가능한 실무 환경에서도 최악의 케이스를 피할 수 있다는 점이 큰 장점입니다.
Unity/게임 개발에서는 정렬된 상태 유지와 범위 기반 조회가 필요한 로직(랭킹, 시간 기반 스케줄, 보조 인덱스 등)에서 활용할 수 있습니다. 반대로 “정렬”이 아니라 “최솟값/최댓값 우선 처리”가 목적이라면, 완전 이진 트리 기반의 힙(Heap)으로 구현하는 PriorityQueue가 더 단순하고 적합할 수 있습니다. 요구사항이 ‘정렬 유지’인지 ‘우선순위 추출’인지에 따라 자료구조를 선택하는 것이 중요합니다.
※ 다음 글에서는 Red-Black Tree 구조를 살펴보며, AVL Tree와 비교해 완전한 균형 대신 색 규칙을 통해 트리 높이를 제한하는 방식이 어떻게 성능과 구현 복잡도 사이의 균형을 맞추는지를 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 시간 복잡도(Big O) 개념 정리 (0) | 2026.01.13 |
|---|---|
| Unity 개발자를 위한 C# Red-Black Tree(레드 블랙 트리) 구현 (0) | 2025.12.27 |
| Unity 개발자를 위한 C# BST(Binary Search Tree, 이진 탐색 트리) 구현 (0) | 2025.12.11 |
| Unity 개발자를 위한 C# Tree(트리) 구현 (0) | 2025.12.10 |
| Unity 개발자를 위한 Graph(그래프)의 이해 (0) | 2025.12.10 |
