트리 알고리즘Advanced

AVL 트리

1962년 Adelson-Velsky와 Landis가 발명한 최초의 자가 균형 이진 검색 트리입니다. 서브트리의 높이 차이를 최대 1로 유지하여 O(log n) 연산을 보장합니다. 삽입/삭제 후 재균형을 위해 네 가지 유형의 회전(LL, RR, LR, RL)을 수행합니다. 데이터베이스, 파일 시스템, 보장된 로그 연산이 중요한 곳에 사용됩니다.

#tree#self-balancing#rotation#binary-search-tree

Complexity Analysis

Time (Average)

O(log n)

Expected case performance

Space

O(n)

Memory requirements

Time (Best)

O(log n)

Best case performance

Time (Worst)

O(log n)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 13•Section Notes

Values to Insert (comma-separated, max 10)

Watch rotations maintain balance!

Example Sets:

Rotation Types

• LL: Right rotation (left-heavy)
• RR: Left rotation (right-heavy)
• LR: Left-Right rotation
• RL: Right-Left rotation
• Balance factor: height(left) - height(right)
• O(log n) for insert, delete, search

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in 트리 알고리즘

트라이 (접두사 트리)

Intermediate

각 노드가 문자를 나타내는 효율적인 문자열 저장 및 검색을 위한 트리 데이터 구조입니다. 문자열 길이 m에 대해 O(m) 삽입/검색 연산을 가능하게 합니다. 자동 완성 시스템, 맞춤법 검사기, IP 라우팅(최장 접두사 매칭), 사전 구현에 필수적입니다. 공통 접두사가 있는 큰 문자열 집합에 메모리 효율적입니다.

O(m)

O(ALPHABET_SIZE × N × M)

treestring-algorithms

Start Learning

최소 공통 조상 (LCA)

Intermediate

재귀적 접근 방식을 사용하여 이진 트리에서 두 노드의 최소 공통 조상을 찾습니다. LCA는 두 노드를 모두 자손으로 갖는 가장 깊은 노드입니다. 계층적 데이터(관계 찾기), 노드 간 거리 계산, 버전 관리 시스템(병합 베이스)의 응용이 있습니다. 더 고급 트리 쿼리의 기초입니다.