Grades 3–5 · Computing
How can a search box finish the word I started?
A search box may offer “car” and “cart” when someone types “ca.” One way to find such suggestions is to store words in a branching tree of letters. Computer scientists call this a trie, or prefix tree. A prefix is a beginning part of a word.
In the diagramFollow the typed beginning through branchesTyped: ca•cartdogMatching wordscarcartcatDouble circles mark complete stored words.
The tiny tree in the picture stores car, cart, cat and dog. Car and cat share the c branch and then the a branch. After that, their paths separate. A special end marker says where a stored word is complete. Car needs that marker even though its path also continues to cart.
To find suggestions for “ca,” the program follows c and then a. It collects complete words farther along those branches: car, cart and cat. Typing “car” leaves car and cart. Typing “z” finds no branch in this little dictionary. Real search boxes may add ranking or other methods. This tree simply finds stored words that begin with the same letters; it does not know what someone intends to write.
About this explanation
Starting knowledge: Can follow letter order and simple branching diagrams.
Sources
- Princeton University — Tries
- Princeton University — TrieST reference: keysWithPrefix