1
$\begingroup$

I'm trying to figure out why ternary search trees are memory efficient. I have tried to read up on this, but all articles I find only state it's memory efficient compared to tries, but not why.

I believe it has something to do with the middle node, and with its ability to handle duplicate keys in a better way than tries, but I'm still not sure.

Why are TST's more memory efficient then tries?

$\endgroup$
3
$\begingroup$

Tries

Tries store strings character by character. See the figure below of a tree that represents the same set of 12 words.

enter image description here

Each input word is shown beneath the node that represents it. In a tree representing words of lowercase letters, each node has 26-way branching. Searches are very fast: A search for "is" starts at the root, takes the "i" branch, then the "s" branch, and ends at the desired node. Unfortunately, search tries have exorbitant space requirements: Nodes with 26-way branching typically occupy 104 bytes, and 256-way nodes consume a kilobyte. Eight nodes representing the 34,000-character Unicode Standard would together require more than a megabyte!

Ternary Search Trees

Ternary search trees combine attributes of binary search trees and digital search tries. Like tries, they proceed character by character. Like binary search trees, they are space efficient, though each node has three children, rather than two. A search compares the current character in the search string with the character at the node. If the search character is less, the search goes to the left child; if the search character is greater, the search goes to the right child. When the search character is equal, though, the search goes to the middle child, and proceeds to the next character in the search string.

enter image description here

The figure above shows a balanced ternary search tree for the same set of 12 words. The low and high pointers are shown as solid lines, while equal pointers are shown as dashed lines. Each input word is shown beneath its terminal node. A search for the word "is" starts at the root, proceeds down the equal child to the node with value "s," and stops there after two comparisons. A search for "ax" makes three comparisons to the first letter ("a") and two comparisons to the second letter ("x") before reporting that the word is not in the tree.

Searching for a string of length k in a ternary search tree with n strings will require at most O(log n+k) comparisons.

The primary challenge in implementing digital search tries is to avoid using excessive memory for trie nodes that are nearly empty. Ternary search trees may be viewed as a trie implementation that gracefully adapts to handle this case, at the cost of slightly more work for full nodes. Ternary search trees combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.

Hope it helps! Reference: Link

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.