What do we benefit from using ternary search trees rather than binary search trees?

Question

Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many other options.

The reason behind them being famous is their space efficiency compared to tries (Although tries are faster) & their flexibility (Compared to Hashtables).

Ternary search trees have three pointers in their data node : lokid the left kid, hikid the right kid & midkid the middle kid.

The thing that I'm missing is why do we need the middle kid ? What is the particularity of this pointer ? In which things it would be better to have that pointer rather than not having it at all ?

I was drawing some trees & i think we can realize the same thing using only 2 pointers (A binary search tree) with insertions going to the left kid if current character in the string to insert is equal or less than the character on the current node and insertions going to the right the other way around.

The following picture shows a binary tree generated from inserting words: KARIM, KARAS, SARAS.

The insertion algorithm of the above tree could be something similar to the following pseudo code :

insert(root, word){

    if(!root) {
        root = new node()
        root->char = *(word++)
    }

    if(*word > root->char)
        insert(root->right, word)

    else {
        if(*word == root->char) 
            insert(root->left, word++)
        else
            insert(root->left, word)    

    }
}

What could possibly be wrong with the above conception ? Am i missing something about the ternary trees which makes them superior to binary trees ?

Answer 1

I'd challenge you to write the code which queries your data structure. For example, how could you determine that "SARAS" is in your tree, but "KSARAS" is not?

The problem with your data structure is that we cannot tell the difference between searching and selecting a letter. This is what the middle child of the ternary tree is used for: when you've found the letter you're looking for, you step to its middle child.

Here's what a ternary tree for your set of words might look like. I've marked word ends with *.

    K
    | \
    A  S
    |  |
    R  A
    |  |
    I  R
  / |  |
 A  M* A
 |     |
 S*    S*

Querying for "SARAS", for example, would look like this:

• [Looking for "SARAS", at node K] S > K, so go right.
• [Looking for "SARAS", at node S] S = S, so go down and advance to next character.
• [Looking for "ARAS", at node A] A = A, so go down and advance to next character.
• etc... (eventually returns true)

Querying for "KSARAS", however, would look like this:

• [Looking for "KSARAS", at node K] K = K, so go down and advance to next character.
• [Looking for "SARAS", at node A] S > A, so go right.
• [Looking for "SARAS", fell off tree] return false.