Algorithmes d'arbreIntermediate

Trie (Prefix Tree)

Tree-based data structure that stores strings efficiently by sharing common prefixes. Each path from root to leaf represents a word or key. Excels at autocomplete, spell checking, IP routing tables, and dictionary implementations with O(m) operations where m is key length.

#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 Algorithmes d'arbre

Lowest Common Ancestor (LCA)

Intermediate

Finds the deepest node that is an ancestor of two given nodes in a tree. Fundamental operation in tree queries with applications in computational biology (species evolution), network routing, and version control systems. Various algorithms offer different time-space tradeoffs.

AVL Tree

Advanced

First self-balancing binary search tree invented in 1962 by Adelson-Velsky and Landis. Maintains height balance through rotations, guaranteeing O(log n) operations. Stricter balancing than red-black trees makes it ideal for lookup-heavy applications like databases and file systems.

Back to Algorithmes d'arbre