Skip to main content
Definition Website Computer and Technology

Trie

Subject: Computer and Technology noun /traɪ/ 1 definition

  1. Definition (noun)

    Entry #44 · Updated

    A Trie—also called a prefix tree or digital tree—is an ordered, tree-based data structure that stores a dynamic set of strings or sequential keys by encoding one symbol per edge along paths from the root. Because keys that share leading symbols traverse the same ancestor nodes, insertion, exact lookup, and prefix matching operate in time proportional to the key's length rather than the total number of stored entries. Unlike hash tables that hash complete keys solely for exact matches or comparison-based search trees that compare whole keys at every branch, a trie trades higher node memory for predictable prefix queries and lexicographically ordered traversal.

    Common Types

    • Standard Character Trie: Allocates one edge per individual character or symbol—commonly using a fixed array or child map—providing simple prefix traversal while consuming more memory for sparse alphabets.

    • Radix Tree (Compressed Trie): Merges non-branching chains of single-child nodes into single edges labeled with multi-character substrings, reducing memory footprint and tree depth for long or sparse keys.

    • Bitwise Trie: Branches on individual bits or fixed bit-chunks of binary keys rather than text characters, making it well suited for longest-prefix matching in IP routing tables.

    • Suffix Trie: Indexes every suffix of a target text within one trie structure, enabling substring membership checks in time proportional to the pattern length.

    Example

    A code editor indexes 80,000 standard-library identifiers in a trie to power real-time autocomplete suggestions. When a developer types parse_, the editor traverses six edges from the root to reach that prefix node and collects only matching descendants such as parse_json and parse_url without scanning all 80,000 entries.