Tries

A trie (pronounced "try", from "retrieval") is a tree where each node represents a character, and a path from the root spells out a string. Common prefixes are shared, so "cat", "cats", "car", "card" all traverse the same c-a prefix before branching. Lookup and insert are O(m) where m is the word length — independent of how many words are stored, which is the big win over a hash map when you need prefix queries ("starts with 'ca'"). Classic uses: autocomplete (every keystroke narrows the subtree), spell-checkers, IP routing tables (longest-prefix match), and compressed variants (radix trees, PATRICIA tries) are used by Redis, Ethereum, and many file-system metadata stores. The trade: more memory than a hash map for non-prefix workloads, pays off if prefix ops are frequent.