AVL 트리

1. AVL 트리

 이진 탐색 트리(Binary Search Tree, BST)는 데이터를 효율적으로 검색, 삽입, 삭제하기 위한 자료구조입니다. 평균적으로 O(log n)의 시간 복잡도를 가지지만, 이는 트리가 균형 잡혀 있을 때의 이야기입니다. 만약 데이터가 정렬된 순서로 삽입되면, 이진 탐색 트리는 한쪽으로만 성장하는 편향 트리(Skewed Tree)가 되어 연결 리스트(Linked List)와 같은 구조가 됩니다. 이 경우, 탐색, 삽입, 삭제 연산은 최악의 경우 O(n)의 시간 복잡도를 갖게 되어 이진 탐색 트리의 장점이 사라집니다.

 이러한 'BST의 퇴화(degenerate) 문제'를 해결하기 위해 등장한 것이 바로 자가 균형 이진 탐색 트리(Self-Balancing BST)입니다. AVL 트리는 최초로 제안된 자가 균형 이진 탐색 트리로, 1962년 두 소련의 수학자 Adelson-Velsky와 Landis의 이름을 따 명명되었습니다. AVL 트리는 삽입 또는 삭제 연산이 일어날 때마다 트리의 균형 상태를 점검하고, 만약 균형이 무너졌다면 '회전(Rotation)' 이라는 작업을 통해 스스로 균형을 맞춥니다. 이로써 트리의 높이를 항상 O(log n)으로 유지하여, 어떤 경우에도 O(log n)의 성능을 보장합니다.

2. AVL 트리의 이론

2.1. 핵심 조건: 균형 인수 (Balance Factor)

AVL 트리는 모든 노드가 다음의 조건을 만족해야 합니다.

모든 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차이가 1 이하여야 한다.

이 높이 차이를 균형 인수(Balance Factor)라고 부릅니다.

• Balance Factor = (왼쪽 서브트리 높이) - (오른쪽 서브트리 높이)
• AVL 트리의 모든 노드는 반드시 -1, 0, 1 중 하나의 균형 인수를 가져야 합니다.
• 만약 어떤 노드의 균형 인수가 -2 또는 2가 되면, 트리의 균형이 깨진 것으로 간주하고 재조정 작업에 들어갑니다.

2.2. 불균형의 발생과 회전 (Rotation)

새로운 노드가 삽입되거나 기존 노드가 삭제될 때, 해당 노드의 부모 노드들로 거슬러 올라가면서 균형 인수가 깨질 수 있습니다. 이때 AVL 트리는 '회전' 연산을 통해 균형을 복원합니다. 불균형 상태는 4가지 경우로 나눌 수 있으며, 각 경우에 맞는 회전 방법이 사용됩니다.

• LL (Left-Left) Case: 불균형이 발생한 노드(A)의 왼쪽 자식(B)의 왼쪽 서브트리에 노드가 삽입되어 불균형 발생.
  • 해결: Right Rotation을 1회 수행합니다.
• RR (Right-Right) Case: 불균형이 발생한 노드(A)의 오른쪽 자식(B)의 오른쪽 서브트리에 노드가 삽입되어 불균형 발생.
  • 해결: Left Rotation을 1회 수행합니다.
• LR (Left-Right) Case: 불균형이 발생한 노드(A)의 왼쪽 자식(B)의 오른쪽 서브트리에 노드가 삽입되어 불균형 발생.
  • 해결: B를 기준으로 Left Rotation 후, A를 기준으로 Right Rotation을 수행합니다. (Double Rotation)
• RL (Right-Left) Case: 불균형이 발생한 노드(A)의 오른쪽 자식(B)의 왼쪽 서브트리에 노드가 삽입되어 불균형 발생.
  • 해결: B를 기준으로 Right Rotation 후, A를 기준으로 Left Rotation을 수행합니다. (Double Rotation)

3. 장단점 및 다른 자료구조와의 비교

구분	장점 (Pros)	단점 (Cons)
AVL 트리	1. 매우 빠른 검색 속도: 항상 엄격하게 균형을 유지하므로 트리의 높이가 낮게 유지되어 검색 성능이 매우 빠르다. 2. 성능 보장: 모든 연산(검색, 삽입, 삭제)에 대해 최악의 경우에도 O(log n)을 보장한다.	1. 복잡한 삽입/삭제 연산: 삽입/삭제 시 균형을 맞추기 위한 회전 연산이 필요하며, 이 과정이 복잡하다. 2. 잦은 재조정 비용: 삽입/삭제가 빈번할 경우, 잦은 회전으로 인해 성능이 저하될 수 있다.

AVL 트리 vs Red-Black 트리

Red-Black 트리는 AVL 트리와 함께 가장 널리 사용되는 자가 균형 이진 탐색 트리입니다.

특징	AVL 트리	Red-Black 트리
균형 정책	더 엄격함. (높이 차이 <= 1)	더 느슨함. (특정 규칙 만족)
트리 높이	더 낮게 유지되는 경향이 있음.	AVL 트리보다 약간 더 높을 수 있음.
검색 성능	더 빠름. (트리가 더 균형 잡혀 있으므로)	AVL 트리보다 약간 느릴 수 있음.
삽입/삭제	더 느림. (균형을 맞추기 위해 더 많은 회전이 필요할 수 있음)	더 빠름. (최대 2~3회의 회전만으로 균형을 맞출 수 있음)
구현 복잡도	상대적으로 더 복잡함.	상대적으로 덜 복잡함.

언제 어떤 기술을 사용해야 하는가?

• AVL 트리: 데이터의 검색이 삽입/삭제보다 훨씬 빈번하게 일어나는 애플리케이션에 적합합니다. 예를 들어, 데이터베이스 인덱싱과 같이 한 번 구축되면 변경이 거의 없고 검색 위주로 사용되는 환경에서 유리합니다.
• Red-Black 트리: 삽입과 삭제가 빈번하게 일어나 검색과 수정의 균형이 중요한 범용적인 환경에 더 적합합니다. 이러한 이유로 C++의 std::map, std::set이나 Java의 TreeMap 등 많은 언어의 표준 라이브러리에서 Red-Black 트리를 채택하고 있습니다.

4. 실무적 관점에서의 사용

왜 사용해야 하는가?

실무에서 데이터 검색 성능은 시스템 전체의 응답성에 큰 영향을 미칩니다. 이진 탐색 트리의 O(n)이라는 최악의 시나리오는 서비스 장애로 이어질 수 있는 매우 치명적인 리스크입니다. AVL 트리는 트리의 균형을 항상 유지함으로써 '예측 가능한 O(log n) 성능'을 보장해줍니다. 이는 시스템의 안정성과 신뢰성을 높이는 데 필수적입니다.

언제, 어떤 부분에 사용해야 하는가?

• 데이터베이스 인덱스: 데이터베이스는 방대한 양의 데이터를 빠르게 검색해야 합니다. AVL 트리를 사용하면 어떤 데이터 분포에서도 빠른 인덱스 검색이 가능합니다.
• 파서(Parser) 또는 컴파일러: 소스 코드를 파싱하여 만드는 심볼 테이블 등을 구현할 때, 빠른 심볼 검색을 위해 사용될 수 있습니다.
• 네트워크: 대규모 라우팅 테이블을 관리하고 가장 효율적인 경로를 O(log n) 시간 안에 찾고자 할 때 활용될 수 있습니다.

어떻게 설계해서 사용하는가?

AVL 트리를 직접 구현하여 사용한다면, 노드 구조체(또는 클래스)는 다음과 같은 정보를 포함해야 합니다.

struct Node {
    int key;            // 노드의 키 값
    Node *left;         // 왼쪽 자식 포인터
    Node *right;        // 오른쪽 자식 포인터
    int height;         // 해당 노드를 루트로 하는 서브트리의 높이
};

• height 멤버를 이용해 각 노드의 균형 인수를 쉽게 계산할 수 있습니다.
• 삽입/삭제 후, 재귀적으로 부모 노드로 올라가면서 height를 갱신하고, 균형 인수를 확인합니다.
• 균형 인수가 -2 또는 2가 되는 최초의 노드를 찾으면, 해당 노드와 그 자식/손자 노드의 관계(LL, RR, LR, RL)를 파악하여 적절한 회전 함수를 호출하여 균형을 맞춥니다.

하지만 대부분의 경우, 실무에서는 이미 검증된 표준 라이브러리(예: std::map)를 사용하는 것이 버그 발생 가능성을 줄이고 생산성을 높이는 더 좋은 선택입니다. AVL 트리의 원리를 이해하는 것은 이러한 라이브러리들이 왜 그렇게 동작하는지, 그리고 특정 상황에 어떤 자료구조를 선택해야 하는지에 대한 깊은 이해를 제공합니다.

5. 요약

AVL 트리는 이진 탐색 트리가 한쪽으로 치우쳐져 성능이 저하되는 것을 막기 위해 스스로 균형을 잡는 최초의 자가 균형 이진 탐색 트리입니다. 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이를 1 이하로 유지하는 것이 핵심 조건입니다. 이 조건을 만족시키기 위해 데이터 삽입/삭제 시 회전(Rotation)이라는 메커니즘을 사용하여 트리의 구조를 동적으로 변경합니다.

이러한 엄격한 균형 정책 덕분에 AVL 트리는 검색 성능이 매우 빠르다는 장점이 있지만, 데이터를 삽입/삭제할 때 회전이 자주 발생할 수 있어 수정 비용이 비싸다는 단점이 있습니다. 따라서 실무에서는 검색이 수정보다 훨씬 중요한 환경에서 사용을 고려할 수 있으며, 일반적인 용도로는 수정 비용이 더 저렴한 Red-Black 트리가 널리 사용됩니다.