Ternary Search Trees

Ternary search trees are a similar data structure to binary search trees and tries. They encapsulate the memory efficiency of binary search trees and time efficiency of tries.

We know that by using tries we can search and sort strings efficiently, but it consumes a lot of memory. Here we can use ternary search trees instead, which store fewer references and null objects.

Characteristics of Ternary Search Trees (TST)

• TST stores characters or strings in nodes

• Each node has three children: left, equal, right

• The left pointer contains all the strings which are alphabetically less than the data

• The equal pointer contains all the strings which are alphabetically equal to the data

• The right pointer contains all the strings which are alphabetically greater than the data

Ternary search trees declaration

1
2
3
4
5
6
7
struct TSTNode {
  char data;
  int isEnd;
  TSTNode * left;
  TSTNode * equal;
  TSTNode * right;
};

In general, we have as many pointers/edges from every node as the number of characters in the alphabet.
We have to define an alphabet in advance + ALP_SIZE. For example: in the English alphabet, there are 26 characters, so ALP_SIZE = 26 -> 26 pointers from every node.

Inserting string in the TST:

To explain it further, we will try to insert some strings in the TST: boats, boat, bat, bats.

We will insert in this order:

First, let’s insert boats.

Now to insert boat to our TST we just have to mark isEnd of of “t” to 1.

Now, let’s insert bat.

Now, at last, insert bats.

Code for inserting into TST:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TSTNode * insertInTST(TSTNode * root, char * word) {

  if (root == NULL) {
    root = new TSTNode();
    root - > data = * word;
    root - > isEnd = 1;
    root - > left = root - > equal = root - > right = NULL;
  }

  if ( * word < root - > data)
    root - > left = insertInTST(root - > left, word);
  else if ( * word == root - > data) {
    if ( * (word + 1))
      root - > equal = insertInTST(root - > equal, word + 1);
    else
      root - > isEnd = 1;
  } else
    root - > right = insertInTST(root - > right, word);
  return root;
}

Time Complexity: O(N), where N is the length of the string to be inserted.

Searching string in the TST:

While searching we can follow the same procedure as the binary search tree. The only difference is that in cases when the character matches we check for the remaining characters instead of returning.

Code for searching into TST:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int searchInTST(TSTNode * root, char * word) {

  if (!root)
    return -1;
  if ( * word < root - > data)
    return searchInTST(root - > left, word);
  else if ( * word > root - > data)
    return searchInTST(root - > right, word);
  else {
    if (root - > isEnd && * (word + 1) == 0)
      return 1;
    return searchInTST(root - > eq, word + 1);
  }
}

Time Complexity: O(N), where N is the length of the string to be searched.

TST vs Hashing

TST

• Works for strings

• Examines just enough key characters

• May only miss a few characters

• Supports much more operation

• More flexible than binary search trees

• Faster than hashing

Hashing

• Needs to examine the entire key

• Search hits and misses cost the same

• Run time and performance relies heavily on the hash function

• Does not support as much operation as TST

Applications of TST

• It can be used to implement the auto-complete feature efficiently

• Can be used for spell checkers

• Near neighbor searching

• For databases, especially when indexing by several non-key fields.