트리 알고리즘Intermediate

트라이 (접두사 트리)

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

#tree#string-algorithms#prefix-matching#autocomplete

Complexity Analysis

Time (Average)

O(m)

Expected case performance

Space

O(ALPHABET_SIZE × N × M)

Memory requirements

Time (Best)

O(m)

Best case performance

Time (Worst)

O(m)

Worst case performance

Words to Insert (comma-separated)

Word to Search

Example Sets:

How it works

• Each character is a node in the tree
• Words share common prefixes
• End-of-word markers for complete words
• O(m) insert and search time
• Perfect for autocomplete 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 트리 알고리즘

최소 공통 조상 (LCA)

Intermediate

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

AVL 트리

Advanced

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