Chapter 17 — It Doesn’t Hurt to Trie

0.0(0)
Studied by 0 people
call kaiCall Kai
Locked
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/14

encourage image

There's no tags or description

Looks like no tags are added yet.

Last updated 3:07 PM on 8/28/26
Name
Mastery
Learn
Test
Matching
Spaced
Call with Kai
Chat

No analytics yet

Send a link to your students to track their progress

15 Terms

1
New cards
Trie
A tree-like structure for storing strings character by character
2
New cards
Prefix tree
Another name for a trie
3
New cards
Trie use case
Autocomplete and prefix search
4
New cards
Trie node
Stores child links, often in a hash table/dictionary
5
New cards
Root node
Starting node before any characters are followed
6
New cards
Trie path
A sequence of character links spelling a word or prefix
7
New cards
Shared prefix
Multiple words reuse the same starting character path
8
New cards
Asterisk marker
Marks the end of a complete word
9
New cards
Complete word vs prefix
A complete word has an end marker; a prefix may continue
10
New cards
Trie search
Follow each character from the root
11
New cards
Trie search Big O
O(K), where K is the search string length
12
New cards
Trie insertion
Create missing character nodes and add end marker
13
New cards
Trie insertion Big O
O(K)
14
New cards
Autocomplete process
Search prefix, then collect words below that node
15
New cards
Trie tradeoff
Fast prefix lookup but may use extra memor