이번 글에서는 AVL 트리에 노드를 삽입하는 방법을 알아봅니다. AVL 트리에서의 삽입 절차는 일반적인 이진 탐색 트리(BST)와 동일하지만, 트리를 따라 내려가는 과정마다 균형 잡기(balance)라는 추가 단계를 수행해야 한다는 점이 다릅니다.
균형을 맞추려면 앞서 살펴본 균형 인수(balance factor)를 계산해야 합니다. 그리고 계산된 균형 상태에 따라 적절한 회전(rotation) 메서드를 호출하면 되는데, 이전 글의 회전 설명을 참고하면 어떤 상황에서 어떤 회전을 적용해야 하는지 직관적으로 이해할 수 있습니다.
그럼 클래스 메서드와 재귀 호출을 위한 헬퍼 함수를 구현해 보겠습니다.
삽입 메서드 구현
insert(data) {
let node = new this.Node(data);
// 트리가 비어 있는지 확인
if (this.root === null) {
// 첫 번째 요소로 삽입
this.root = node;
} else {
insertHelper(this, this.root, node);
}
}
헬퍼 메서드
function insertHelper(self, root, node) {
if (root === null) {
root = node;
} else if (node.data < root.data) {
// 왼쪽으로 이동!
root.left = insertHelper(self, root.left, node);
// 균형 인수를 확인하고 적절한 회전 수행
if (root.left !== null && self.getBalanceFactor(root) > 1) {
if (node.data > root.left.data) {
root = rotationLL(root);
} else {
root = rotationLR(root);
}
}
} else if (node.data > root.data) {
// 오른쪽으로 이동!
root.right = insertHelper(self, root.right, node);
// 균형 인수를 확인하고 적절한 회전 수행
if (root.right !== null && self.getBalanceFactor(root) < -1) {
if (node.data > root.right.data) {
root = rotationRR(root);
} else {
root = rotationRL(root);
}
}
}
return root;
}
회전 로직 이해하기
헬퍼 함수의 핵심은 재귀 호출이 반환된 직후 균형 인수를 확인한다는 점입니다. 새 노드가 삽입된 경로를 따라 거슬러 올라가면서 각 노드의 균형이 깨졌는지 검사하고, 깨졌다면 즉시 회전으로 복원합니다.
- 왼쪽으로 치우친 경우 (균형 인수 > 1): 새 노드가 어느 서브트리에 삽입되었는지에 따라 LL 회전 또는 LR 회전을 적용합니다.
- 오른쪽으로 치우친 경우 (균형 인수 < -1): 마찬가지로 새 노드의 위치에 따라 RR 회전 또는 RL 회전을 적용합니다.
이렇게 하면 삽입 연산이 진행되는 동안 트리의 높이가 항상 O(log n) 범위 내에서 유지되므로, 탐색·삽입·삭제 모두 안정적인 성능을 보장할 수 있습니다.
다음과 같이 테스트해 볼 수 있습니다.
예제
let AVL = new AVLTree(); AVL.insert(10); AVL.insert(15); AVL.insert(5); AVL.insert(50); AVL.insert(3); AVL.insert(7); AVL.insert(12); AVL.inOrder();
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
3 5 7 10 12 15 50
중위 순회(in-order traversal) 결과가 오름차순으로 정렬되어 출력되는 것을 확인할 수 있습니다. 이는 삽입 과정에서 균형 회전이 올바르게 수행되어 트리가 이진 탐색 트리의 성질을 그대로 유지하고 있다는 의미입니다.