트리 알고리즘Intermediate

최소 공통 조상 (LCA)

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

#tree#binary-tree#recursion#ancestry

Complexity Analysis

Time (Average)

O(n)

Expected case performance

Space

O(h)

Memory requirements

Time (Best)

O(n)

Best case performance

Time (Worst)

O(n)

Worst case performance

Binary Tree (level-order, comma-separated)

Use 'null' for empty nodes

Node p

Node q

Example Trees:

How it works

• Recursively traverse the tree
• Find nodes p and q in subtrees
• LCA is where both are found
• O(n) time, O(h) space
• Used in version control systems

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

AVL 트리

Advanced

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