시스매

스스로 균형 잡는 데이터 구조 AVL 트리 완벽 핸드북

17 min read

2025-08-24 13:42

  • AVL 트리는 최초의 자가 균형 이진 탐색 트리로, 어떤 경우에도 O(log n)의 시간 복잡도로 데이터 검색을 보장합니다.

  • 모든 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 1 이하로 유지되며, 이 균형이 깨지면 ‘회전’을 통해 스스로 균형을 맞춥니다.

  • 검색 성능이 매우 중요하지만 삽입과 삭제가 상대적으로 적은 데이터베이스나 파일 시스템 같은 곳에서 유용하게 사용됩니다.

스스로 균형 잡는 데이터 구조 AVL 트리 완벽 핸드북

컴퓨터 과학의 세계에서 데이터는 왕입니다. 그리고 그 왕을 효율적으로 관리하는 것은 모든 개발자의 숙명이자 과제입니다. 수많은 데이터를 그저 쌓아두기만 한다면, 정작 필요할 때 원하는 정보를 찾는 데 하루 온종일이 걸릴지도 모릅니다. 이를 해결하기 위해 탄생한 것이 바로 ‘자료구조’이며, 그중에서도 ‘트리(Tree)’ 구조는 계층적인 데이터를 표현하고 탐색하는 데 탁월한 성능을 보입니다.

하지만 단순한 이진 탐색 트리(Binary Search Tree)는 치명적인 약점을 가지고 있습니다. 데이터가 들어오는 순서에 따라 트리의 모양이 한쪽으로 길게 늘어선 비효율적인 형태가 될 수 있다는 점입니다. 최악의 경우, 연결 리스트(Linked List)와 다를 바 없는 성능을 보여주게 되죠.

이러한 문제를 해결하기 위해 1962년, 두 명의 소련 수학자, **게오르기 아델손-벨스키(Georgy Adelson-Velsky)**와 **예브게니 란디스(Yevgeny Landis)**는 획기적인 아이디어를 세상에 내놓습니다. 바로 ‘스스로 균형을 잡는’ 이진 탐색 트리, 그들의 이름을 딴 AVL 트리입니다.

1. AVL 트리는 왜 만들어졌을까? 이진 탐색 트리의 배신

AVL 트리의 탄생 배경을 이해하려면 먼저 이진 탐색 트리(BST)의 한계를 알아야 합니다. 이진 탐색 트리는 다음과 같은 간단한 규칙을 가집니다.

  • 모든 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 존재한다.

  • 모든 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 존재한다.

이 규칙 덕분에 우리는 데이터를 찾을 때마다 탐색 범위를 절반씩 줄여나갈 수 있습니다. 마치 사전에서 단어를 찾듯, 매우 효율적인 탐색이 가능하죠. 이상적인 경우, 즉 트리가 완벽한 균형을 이루고 있을 때, N개의 데이터가 있다면 약 log₂N 번의 비교만으로 원하는 데이터를 찾을 수 있습니다. 이를 시간 복잡도로 **O(log n)**이라고 표현합니다.

하지만 만약 데이터가 1, 2, 3, 4, 5 순서로 들어온다면 어떻게 될까요? 트리는 다음과 같이 한쪽으로만 길게 늘어선 모양이 됩니다.

1
 \
  2
   \
    3
     \
      4
       \
        5

이런 트리에서 숫자 5를 찾으려면 결국 모든 노드를 한 번씩 방문해야 합니다. 이는 연결 리스트에서 데이터를 찾는 것과 똑같으며, 시간 복잡도는 **O(n)**이 됩니다. 데이터가 100만 개라면 100만 번의 비교가 필요할 수도 있다는 뜻입니다. O(log n)의 엄청난 효율성을 기대했지만, 최악의 경우 O(n)이라는 ‘배신’을 당하게 되는 셈입니다.

AVL 트리는 바로 이 ‘배신’을 막기 위해 탄생했습니다. 데이터가 어떤 순서로 들어오든, 트리가 항상 “어느 정도” 균형 잡힌 상태를 유지하도록 강제하여 언제나 O(log n)의 검색 성능을 보장하는 것이 AVL 트리의 핵심 목표입니다.

2. AVL 트리의 구조: 균형의 열쇠 ‘균형 인수’

AVL 트리는 이진 탐색 트리의 모든 규칙을 그대로 따릅니다. 단, 한 가지 중요한 조건이 추가됩니다.

모든 노드에 대해, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 초과할 수 없다.

이 조건을 ‘AVL 균형 조건’이라고 부릅니다. 그리고 이 높이 차이를 **균형 인수(Balance Factor)**라고 정의합니다.

  • 균형 인수 (Balance Factor) = (오른쪽 서브트리 높이) - (왼쪽 서브트리 높이)

따라서 AVL 트리의 모든 노드는 반드시 -1, 0, 1 중 하나의 균형 인수 값을 가져야 합니다.

  • -1: 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 1 더 높다. (Left-Heavy)

  • 0: 양쪽 서브트리의 높이가 같다. (Balanced)

  • 1: 오른쪽 서브트리가 왼쪽 서브트리보다 높이가 1 더 높다. (Right-Heavy)

만약 어떤 노드의 균형 인수가 -2나 +2가 되는 순간, 트리의 균형이 깨졌다고 판단하고 즉시 ‘수술’에 들어갑니다. 이 수술이 바로 AVL 트리의 핵심 메커니즘인 **회전(Rotation)**입니다.

3. AVL 트리의 작동법: 삽입, 삭제, 그리고 ‘회전’

AVL 트리의 핵심은 데이터가 추가되거나(삽입) 삭제될 때 균형을 유지하는 방법에 있습니다.

검색은 일반 이진 탐색 트리와 100% 동일합니다. 루트 노드부터 시작하여 찾고자 하는 값과 비교하며 왼쪽 또는 오른쪽으로 이동하면 됩니다. AVL 트리는 항상 균형이 잡혀있으므로 O(log n)의 시간 복잡도를 철저히 보장합니다.

삽입 (Insertion)

  1. 일반 BST처럼 삽입: 먼저 새로운 데이터를 이진 탐색 트리의 규칙에 따라 적절한 위치에 삽입합니다.

  2. 균형 인수 갱신 및 확인: 삽입된 노드부터 루트 노드까지 거슬러 올라가면서 경로에 있는 모든 노드의 균형 인수를 다시 계산합니다.

  3. 리밸런싱 (Rebalancing): 올라가는 도중 균형 인수가 -2 또는 +2가 된 노드를 발견하면, 해당 노드를 기준으로 ‘회전’을 수행하여 균형을 맞춥니다. 삽입의 경우, 회전은 최대 한 번만 발생합니다.

삭제 (Deletion)

삭제 과정도 삽입과 유사하지만 조금 더 복잡합니다.

  1. 일반 BST처럼 삭제: 삭제할 노드를 이진 탐색 트리의 규칙에 따라 삭제합니다.

  2. 균형 인수 갱신 및 확인: 삭제가 일어난 위치부터 루트 노드까지 거슬러 올라가며 균형 인수를 갱신합니다.

  3. 리밸런싱 (Rebalancing): 균형이 깨진 노드를 발견하면 회전을 통해 균형을 맞춥니다. 삭제의 경우, 한 번의 회전으로 트 전체의 균형이 맞춰지지 않을 수 있어, 루트까지 올라가는 동안 여러 번의 회전이 필요할 수 있습니다.

4. 심화: 4가지 회전(Rotation) 시나리오 정복하기

AVL 트리의 균형을 맞추는 회전은 마치 척추 교정 치료와 같습니다. 틀어진 뼈대를 바로잡아 전체적인 균형을 되찾는 과정이죠. 회전은 균형이 깨진 지점과 그 원인에 따라 4가지 시나리오로 나뉩니다.

균형이 깨진 노드를 x라고 가정해 봅시다. x의 균형 인수가 +2(Right-Heavy) 또는 -2(Left-Heavy)가 되었을 때 회전이 필요합니다.

시나리오 1: RR (Right-Right) Case

  • 상황: x 노드의 오른쪽 자식(y)의 오른쪽에 새로운 노드가 삽입되어 균형이 깨진 경우.

  • 해결책: 왼쪽 회전 (Left Rotation)

x를 중심으로 왼쪽으로 한 번 회전시킵니다. x는 내려가고 y가 그 자리로 올라옵니다. x는 y의 왼쪽 자식이 됩니다.

[Before]

  x (+2)
   \
    y (+1)
     \
      z (New)

[After Left Rotation on x]

    y (0)
   / \
  x(0) z(0)

시나리오 2: LL (Left-Left) Case

  • 상황: x 노드의 왼쪽 자식(y)의 왼쪽에 새로운 노드가 삽입되어 균형이 깨진 경우.

  • 해결책: 오른쪽 회전 (Right Rotation)

x를 중심으로 오른쪽으로 한 번 회전시킵니다. x는 내려가고 y가 그 자리로 올라옵니다. x는 y의 오른쪽 자식이 됩니다.

[Before]

      x (-2)
     /
    y (-1)
   /
  z (New)

[After Right Rotation on x]

      y (0)
     / \
    z(0) x(0)

시나리오 3: RL (Right-Left) Case

  • 상황: x 노드의 오른쪽 자식(y)의 왼쪽에 새로운 노드가 삽입되어 균형이 깨진 경우.

  • 해결책: 오른쪽 회전 후 왼쪽 회전 (Right-Left Rotation)

이 경우는 한 번의 회전으로는 해결되지 않습니다.

  1. 먼저 y를 중심으로 오른쪽 회전을 수행합니다.

  2. 그 후, x를 중심으로 왼쪽 회전을 수행합니다. (RR Case와 동일해짐)

[Before]

  x (+2)
   \
    y (-1)
   /
  z (New)

[After Right Rotation on y]

  x (+2)
   \
    z (+1)
     \
      y

[After Left Rotation on x]

      z (0)
     / \
    x(0) y(0)

시나리오 4: LR (Left-Right) Case

  • 상황: x 노드의 왼쪽 자식(y)의 오른쪽에 새로운 노드가 삽입되어 균형이 깨진 경우.

  • 해결책: 왼쪽 회전 후 오른쪽 회전 (Left-Right Rotation)

RL Case와 대칭적인 경우입니다.

  1. 먼저 y를 중심으로 왼쪽 회전을 수행합니다.

  2. 그 후, x를 중심으로 오른쪽 회전을 수행합니다. (LL Case와 동일해짐)

[Before]

      x (-2)
     /
    y (+1)
     \
      z (New)

[After Left Rotation on y]

      x (-2)
     /
    z (-1)
   /
  y

[After Right Rotation on x]

      z (0)
     / \
    y(0) x(0)

이 네 가지 회전 메커니즘 덕분에 AVL 트리는 어떤 데이터의 삽입과 삭제에도 굴하지 않고 꿋꿋하게 균형을 유지할 수 있습니다.

5. AVL 트리 vs 다른 자료구조

그렇다면 AVL 트리는 항상 최고의 선택일까요? 다른 자료구조와 비교하여 장단점을 살펴보겠습니다.

자료구조검색 시간삽입/삭제 시간특징
AVL 트리O(log n)O(log n)- 엄격한 균형 유지 (높이 차이 1 이하)
- 검색 성능이 매우 뛰어남
- 삽입/삭제 시 회전이 비교적 빈번할 수 있음
Red-Black 트리O(log n)O(log n)- AVL보다 덜 엄격한 균형 유지
- 삽입/삭제 시 회전이 덜 발생하여 삽입/삭제가 잦은 경우 유리
- 검색 성능은 AVL보다 미세하게 느릴 수 있음
이진 탐색 트리최선: O(log n)
최악: O(n)		최선: O(log n)
최악: O(n)		- 구현이 간단함
- 데이터 입력 순서에 따라 성능이 극단적으로 저하될 수 있음
해시 테이블평균: O(1)
최악: O(n)		평균: O(1)
최악: O(n)		- 키-값 쌍으로 데이터를 저장
- 평균적인 속도는 가장 빠름
- 데이터 정렬 및 범위 검색이 불가능함

결론적으로, AVL 트리는 다음과 같은 상황에서 최고의 선택이 될 수 있습니다.

  • 데이터의 검색(읽기) 작업이 삽입/삭제(쓰기) 작업보다 훨씬 빈번할 때

  • 데이터의 정렬된 순서나 범위 검색이 필요할 때

  • 어떤 경우에도 O(log n)의 검색 성능을 반드시 보장해야 할 때

이러한 특성 때문에 AVL 트리는 데이터베이스 인덱싱, 파일 시스템 등에서 그 진가를 발휘합니다.

6. 결론: 균형 잡힌 삶을 추구하는 데이터 구조

AVL 트리는 ‘균형’의 중요성을 보여주는 훌륭한 예시입니다. 한쪽으로 치우치지 않고 끊임없이 스스로를 바로잡는 노력을 통해, 어떤 상황에서도 안정적이고 예측 가능한 성능을 제공합니다. 비록 삽입과 삭제 시 회전이라는 추가 비용이 발생하지만, 그 덕분에 우리는 언제나 번개처럼 빠른 검색 속도를 누릴 수 있습니다.

컴퓨터 과학의 수많은 자료구조 속에서 AVL 트리가 반세기가 넘는 시간 동안 꾸준히 사랑받는 이유는 바로 이 ‘신뢰성’ 때문일 것입니다. 데이터를 다루는 개발자라면, 이 똑똑하고 부지런한 자료구조의 원리를 이해하고 적재적소에 활용할 수 있는 지혜를 갖추는 것이 중요합니다.

레퍼런스(References)

AVL트리

그래프 뷰

백링크