Trie (data structure)
A trie (also called a prefix tree or digital tree) is a tree-like data structure used to store strings where each node represents a single character of a key, and paths from root to leaf spell out complete keys. The root represents an empty string, and each edge corresponds to a character. Tries are highly efficient for prefix-based search operations, making them ideal for autocomplete systems, spell checkers, and IP routing tables.
Trie vs Hash Table vs BST for String Operations
| Operation | Trie | Hash Table | Balanced BST |
|---|---|---|---|
| Search | O(L) | O(L) avg | O(L log n) |
| Insert | O(L) | O(L) avg | O(L log n) |
| Delete | O(L) | O(L) avg | O(L log n) |
| Prefix Search | O(L + k) | O(n·L) | O(L log n + k) |
| Space | O(ALPHABET × n × L) | O(n) | O(n) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Binary Search Tree
A binary search tree (BST) is a binary tree in which every node satisfies the property that all keys in its left subtree are less than the node's key and all keys in its right subtree are greater. This ordering property makes search, insertion, and deletion operations efficient, averaging O(log n) for balanced trees. BSTs are foundational in database indexing, symbol tables, and dynamic set operations.
Graph (computer science)
A graph is a non-linear data structure consisting of a finite set of vertices (nodes) and a set of edges that connect pairs of vertices. Graphs can be directed (edges have a direction) or undirected, and weighted (edges carry a cost) or unweighted. They are used to model real-world problems such as social networks, transportation systems, web page link structures, and dependency resolution.
Bloom Filter
A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It can yield false positives (reporting an element is present when it is not) but never false negatives (it will never miss a true member). It works by hashing elements into a bit array using multiple hash functions. Bloom filters are used in databases, web caches, network routers, and spell checkers where memory efficiency is critical and occasional false positives are tolerable.
The word "trie" was coined by Edward Fredkin in 1960, derived from the middle letters of "retrieval." Despite being spelled "trie," it is commonly pronounced "try" to distinguish it from "tree," reflecting its purpose as a retrieval data structure.