木構造アルゴリズムIntermediate

トライ（プレフィックスツリー）

共通のプレフィックスを共有することで文字列を効率的に格納するツリーベースのデータ構造です。ルートからリーフへの各パスは単語またはキーを表します。オートコンプリート、スペルチェック、IPルーティングテーブル、辞書実装で優れており、キーの長さmに対してO(m)の操作を実現します。

#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

木の中で2つの与えられたノードの祖先である最も深いノードを見つけます。計算生物学（種の進化）、ネットワークルーティング、バージョン管理システムでの応用を持つ木クエリの基本操作です。様々なアルゴリズムが異なる時間-空間のトレードオフを提供します。

AVL木

Advanced

1962年にAdelson-VelskyとLandisによって発明された最初の自己平衡二分探索木です。回転を通じて高さのバランスを維持し、O(log n)の操作を保証します。赤黒木よりも厳格なバランシングは、データベースやファイルシステムなどの検索が多いアプリケーションに理想的です。