Chapter 17 — It Doesn’t Hurt to Trie

Trie

A tree-like data structure used to store and search strings character by character

Trie pronunciation

Trie is usually pronounced like “try”

Prefix tree

Another name for a trie because tries are useful for prefix-based searching

Digital tree

Another name sometimes used for a trie

Trie use case

Autocomplete, prefix searching, dictionaries, IP addresses, and phone numbers

Autocomplete

Suggesting complete words based on a prefix the user has typed

Why tries help autocomplete

They can quickly find the prefix path and collect words below it

Trie node

A node that stores a dictionary or hash table of child links

children dictionary

The hash table inside a trie node that maps characters to child nodes

Root node

The starting node of a trie before any characters are followed

Trie path

A sequence of character links that spells a word or prefix

Child node

The next node reached by following a character key from the current node

Asterisk marker

The "*" key used to show that a complete word ends at that node

Why the asterisk is needed

It separates a complete word from a prefix of a longer word

Complete word vs prefix

A complete word has an asterisk marker, while a prefix may only be part of a longer path

Example of complete word vs prefix

“bat” needs an asterisk even if “batter” continues past the same letters

Shared prefix

When multiple words reuse the same starting path in a trie

Shared prefix benefit

Tries avoid fully repeating the same starting letters for related words

Trie search

Start at the root and follow each character through child nodes

Trie search success

If every character path exists, return the final node

Trie search failure

If a character path does not exist, return None or stop searching

Trie search Big O

O(K), where K is the number of characters in the search string

Why trie search is O(K)

The algorithm checks one character at a time using hash table lookup at each node

Trie search vs binary search

Binary search depends on the number of stored words, while trie search depends on word length

Trie insertion

Add a word by following existing character paths and creating missing nodes

Trie insertion process

Start at the root, process each character, create missing child nodes, then add "*" at the end

Trie insertion Big O

O(K), where K is the number of characters in the word

Collect all words

A recursive process that gathers every complete word below a given trie node

collectAllWords use case

Used after finding a prefix node to gather autocomplete suggestions

Autocomplete process

Search for the prefix, then collect all words below the final prefix node

Trie with values

A trie where the "*" marker stores extra information like a popularity score

Popularity score

A value used to rank autocomplete suggestions by how common or important they are

Smarter autocomplete

Autocomplete that sorts matching words by popularity instead of showing every match equally

Trie tradeoff

Tries can provide fast prefix lookup but may use extra memory for many nodes and child dictionaries

Main lesson of Chapter 17

Tries make prefix-based string searching and autocomplete efficient by storing words as shared character pat