Does the tree learn from data?

Ordinary insertion builds an index. It does not train a predictive model.

Can a word be both a key and a prefix?

Yes. Its ending marker records the key while its middle continuation supports longer keys.

Is it always faster than hashing?

No. Prefix functionality, memory layout, key lengths, and workload determine the useful comparison.

AI Glossary / Graphs and symbolic AI / Intermediate

Ternary search tree

Definition

A ternary search tree is a data structure for storing and finding strings one character at a time. Each node holds a character and up to three links: one for smaller characters, one for matching characters followed by the next position, and one for larger characters. It combines character-by-character prefix storage with ordered comparisons and is also called a ternary search trie.

What it means

The word “ternary” refers to the three possible links, not to strings containing only three symbols. A tree can index an ordinary vocabulary or a collection of product codes. Values associated with completed keys can store definitions, identifiers, or other records.

A prefix path and a stored key are different things. If “cart” is stored, a path for “car” exists, but “car” is a key only if its ending is marked. This distinction matters when a search box must distinguish a valid product code from the beginning of several longer codes.

How it works

Compare the current query character with the node's character. A smaller or larger character follows the corresponding side link without consuming a query character. A match advances to the next query character through the middle link. Once the final character matches, check whether that node marks a stored key.

Insertion follows the same comparisons and creates missing nodes. Prefix retrieval first finds the prefix, then explores its continuations. A prefix that is itself a key must also be included in the results.

The three-link design avoids allocating one child slot for every possible alphabet symbol at every node. Actual memory and speed depend on implementation, key distribution, and tree shape. Returning thousands of suggestions still requires producing those results; the index does not eliminate output costs.

Three practical examples

1. A parts catalog completes “ax” with stored codes such as “ax12” and “ax19.” A separate availability filter removes discontinued parts after retrieval.

2. A document editor looks up reserved words and offers completions. Matching the prefix “for” can return both the complete keyword “for” and a longer identifier such as “format,” if both are indexed.

3. An assistant searches an approved glossary before presenting definitions. The tree provides exact or prefix candidates; another component ranks them or handles misspellings and meaning.

Think of it this way

Think of a spelling guide that asks whether the letter you want comes before, matches, or comes after the displayed letter. Only a match moves you to the next letter of the word. The analogy captures navigation, but a real implementation uses linked records rather than a person repeatedly scanning an alphabet.

Worked example

Insert “cat,” “car,” and “dog,” in that order, into a simple unbalanced tree, using ordinary alphabetical character order. Mark the last node of each completed key.

Inserting “cat” creates a middle-link chain c, a, t. Inserting “car” matches c and a. At t, the desired r is smaller, so an r node is added on t's left link and marked as the end of “car.” Inserting “dog” first compares d with c. Because d is larger, d becomes c's right child; its middle chain continues through o and g.

Now search for “car.” Compare c with c, a with a, r with t, and r with r: four character comparisons. The side step from t to r does not advance the query position. The marked r node confirms success.

Searching for “ca” reaches a but finds no ending marker, so the key is absent. A prefix request for “ca” nevertheless returns “car” and “cat.” Searching for “cap” reaches the r node while comparing p, then follows its missing left link and fails. These outcomes follow from the stated insertion order; other valid tree shapes can use different comparison counts.

Illustrative case study

Fictional case: Cedar Parts builds an autocomplete tool for catalog codes. Its developer initially treats every matched prefix as a complete product, so typing a shortened code displays a purchase link for a nonexistent item.

The team separates the key-ending marker from navigation nodes and adds tests containing both a short code and longer codes beginning with it. It also keeps original display spelling alongside a documented normalized search key. Acceptance checks compare returned codes against a small manually reviewed catalog before testing performance on the full dataset. No measured commercial improvement is implied.

Common misconceptions and mistakes

Do not advance the query position when following a smaller or larger link. That skips a character and can create false matches or misses.

Do not assume every node completes a key, or that a three-way tree is automatically balanced. Insertion order can affect comparison paths in a simple implementation.

Character ordering is not automatically human dictionary ordering. Case, accents, and Unicode representation need a deliberate policy. Also distinguish this structure from ternary search for optimizing a unimodal function; the shared word does not make the algorithms equivalent.

Business use

Consider a ternary search tree when exact string lookup and prefix retrieval are central requirements. Compare it with a hash table, sorted array, and other trie representations using the real catalog and update pattern.

For a business assistant, define what a returned candidate means. A lexical prefix match says nothing about permission, current stock, or semantic relevance. Apply those checks separately, limit suggestion counts sensibly, and retain a way to retrieve the complete record for an accepted key.

Check your understanding

If only “plane” is stored, does successfully navigating the characters “plan” establish that “plan” is a stored key?

Answer: No. The path establishes a prefix. A separate ending marker is required to establish that “plan” itself is stored.

Related terms

Trie
prefix search
string matching
binary search tree
symbol table
autocomplete
hash table
character encoding

Learn next

Study ordinary tries next. Draw both representations for “cat,” “car,” and “dog,” and mark key endings. Then insert “ca” and explain which navigation nodes can be reused and which key metadata must change.

Sources

Primary reference: Sedgewick and Wayne, TST.java, https://algs4.cs.princeton.edu/55compression/TST.java.html. The implementation was opened and read for comparison navigation, key values, insertion, and prefix collection. The catalogue examples and comparison trace are original hand-checked illustrations, not executed performance measurements.

Previous: Ternary search Next: Test and Evaluation, Verification and Validation