Nikhil Kumar SinghVrishchik

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.

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*.

```
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.

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.

```
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.

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

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

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.

Discuss this article in the forums
Introduction
Notation
Basic idea
Isolating the last bit
Read cumulative fre...

Read More There has always been a war for classification algorithms. Logistic regression,
decision trees, random forest,...

Read More We are going to learn all about the hash table in several articles. To begin
with we will discuss what hashing...

Read More