Algorithm Guidecomplexity: O(log n)

AVL 트리 (AVL Tree)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 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 Frequently Asked Questions

FAQ

What is AVL 트리 (AVL Tree)?+

What is the time complexity of AVL 트리 (AVL Tree)?+

The time complexity of AVL 트리 (AVL Tree) is O(log n). Follow the step-by-step visualization to see exactly why.

Where is AVL 트리 (AVL Tree) used?+

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

What's a simple analogy for AVL 트리 (AVL Tree)?+

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

→ Trees — see allRelated

🌳트리 순회 (Tree Traversal)

O(n)

🌳세그먼트 트리 (Segment Tree)

질의·갱신 O(log n)

🌳트라이 (Trie)

O(m) (문자열 길이)

Guide Progress0%