Algorithm Guidecomplexity: O(log n)

AVL 트리 (AVL Tree)

모든 노드의 좌우 서브트리 높이 차를 1 이하로 유지하는 자가 균형 이진 탐색 트리입니다. 삽입·삭제 후 회전(rotation)으로 균형을 복구해 항상 O(log n)을 보장합니다.

01AVL 트리 (AVL Tree)

알고리즘 작동 원리 탐색

AVL 트리. 삽입 후 좌우 높이 차가 1을 넘으면 회전으로 균형을 맞추는 자가 균형 BST입니다.

insert(20) · 20 > 10이므로 오른쪽 자식으로 붙입니다. 아직 균형 상태입니다.

insert(30) · 오른쪽으로만 쏠려 10→20→30 사슬이 됩니다. 10의 균형 인수가 -2 — 불균형입니다!

왼쪽 회전 · 가운데 20을 위로 끌어올리고 10을 그 왼쪽 자식으로 내립니다.

균형 복구 완료 · 높이가 2에서 1로 낮아졌습니다. 이렇게 매번 균형을 유지해 항상 O(log n)입니다.

Live Python

1def insert(node, key):

2 if not node:

3 return Node(key)

4 if key < node.key:

5 node.left = insert(node.left, key)

6 else:

7 node.right = insert(node.right, key)

8 update_height(node)

9 bf = balance(node) # 왼쪽 높이 − 오른쪽 높이

10 if bf < -1: # 오른쪽으로 치우침

11 return rotate_left(node) # 균형 복구

12 if bf > 1:

13 return rotate_right(node)

14 return node

1 / 5

02 쉽게 이해하기

For Everyone

🔑핵심 동작

모든 노드에서 좌우 높이 차가 1을 넘지 않게 유지합니다. 어긋나면 회전으로 되돌려 높이를 O(log n) 으로 묶습니다.

💡쉽게 말하면

삽입·삭제 후 좌우 높이 차가 1을 넘으면 '회전'으로 균형을 복구하는 BST예요.

덕분에 한쪽으로 치우쳐 느려지는 일 없이 항상 O(log n)을 보장합니다.

📍어디에 쓰나

–잦은 검색이 필요한 정렬 데이터
–데이터베이스 인덱스

03 파이썬 구현 코드

AVL 트리 (AVL Tree)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def height(n):
    return n.height if n else 0

def balance(n):
    return height(n.left) - height(n.right) if n else 0

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y); update(x)
    return x

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update(node)
    return rebalance(node)  # |balance| > 1 이면 회전

04 자주 묻는 질문

FAQ

AVL 트리 (AVL Tree)란 무엇인가요?+

AVL 트리 (AVL Tree)의 시간복잡도는 어떻게 되나요?+

AVL 트리 (AVL Tree)의 시간복잡도는 O(log n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

AVL 트리 (AVL Tree)은(는) 어디에 사용하나요?+

잦은 검색이 필요한 정렬 데이터, 데이터베이스 인덱스.

AVL 트리 (AVL Tree)를 쉽게 비유하면?+

모든 노드에서 좌우 높이 차가 1을 넘지 않게 유지합니다. 어긋나면 회전으로 되돌려 높이를 O(log n) 으로 묶습니다.

→ 트리 전체 보기Related

🌳트리 순회 (Tree Traversal)

O(n)

🌳세그먼트 트리 (Segment Tree)

질의·갱신 O(log n)

🌳트라이 (Trie)

O(m) (문자열 길이)