Algorithm Guidecomplexity: O(log n)

AVL 트리 (AVL Tree)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

AVL Tree · 자가 균형

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

Logic Node1 / 5

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

02 쉽게 이해하기

For Everyone

🔑비유

양팔 저울 — 한쪽이 무거워지면 즉시 회전시켜 균형을 다시 맞춥니다.

💡쉽게 말하면

삽입·삭제 후 좌우 높이 차가 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 이면 회전

Guide Progress0%