Ternary Search Trees (2023)

By Jon Bentley and Bob Sedgewick, April 01, 1998

When you have to store a set of strings, what data structure do you use? Jon and Robert suggest one place you can start is with ternary search trees, which combine the time efficiency of digital tries with the space efficiency of binary search trees.

When you have to store a set of strings, what data structure should you use? You could use hash tables, which sprinkle the strings throughout an array. Access is fast, but information about relative order is lost. Another option is the use of binary search trees, which store strings in order, and are fairly fast. Or you could use digital search tries, which are lightning fast, but use lots of space.

In this article, we'll examine ternary search trees, which combine the time efficiency of digital tries with the space efficiency of binary search trees. The resulting structure is faster than hashing for many typical search problems, and supports a broader range of useful problems and operations. Ternary searches are faster than hashing and more powerful, too.

(Video) Advanced Data Structures: Ternary Search Trees (TSTs)

We described the theory of ternary search trees at a symposium in 1997 (see "Fast Algorithms for Sorting and Searching Strings," by J.L. Bentley and R. Sedgewick, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1997). In this article, we'll concentrate on what the data structure offers working programmers. Algorithms in C, Third Edition, by Robert Sedgewick (Addison-Wesley, 1998) provides yet another view of ternary search trees. For more information (including all the code in this article and the driver software), refer to http://www.cs.princeton.edu/~rs/strings/ or see "Resource Center," page 3.

A Grove of Trees

Figure 1 is a binary search tree that represents 12 common two-letter words. For every node, all nodes down the left child have smaller values, while all nodes down the right child have greater values. A search starts at the root. To find the word "on," for instance, we compare it to "in" and take the right branch. We take the right branch at "of" and the left branch at "or," and then arrive at "on." Every comparison could access each character of both words.

Ternary Search Trees (1)

Figure 1: A binary search tree for 12 words.

Digital search tries store strings character by character. Figure 2 is a tree that represents the same set of 12 words; each input word is shown beneath the node that represents it. (Two-letter words lead to prettier pictures; all structures that we'll see can store variable-length words.) In a tree representing words of lowercase letters, each node has 26-way branching (though most branches are empty, and not shown in Figure 2). 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. At every node, we access an array element (one of 26), test for null, and take a branch. 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!

(Video) 2 8 Ternary search tree introduction

Ternary Search Trees (2)

Figure 2: A digital search trie for 12 words.

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.

Figure 3 is 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.

Ternary Search Trees (3)

(Video) 37 2 Ternary Search Tries

Figure 3: A ternary search tree for 12 words.

The idea behind ternary search trees dates back at least as far as 1964. In "Randomized Binary Searching with Tree Structures" (Communications of the ACM, March 1964), H.A. Clampett sketched a primitive version of the structure. Computer scientists have proven many theorems about the trees; for instance, 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 C Structure

As far as we can tell, previous authors have viewed ternary search trees as a theoretical structure for proving theorems. We were delighted to find that the trees also lead to practical computer programs. Although we've chosen to illustrate the data structure in C, we could have just as easily chosen C++, Java, or other languages.

Each node in a ternary search tree is represented by the following structure:

typedef struct tnode *Tptr; typedef struct tnode { char splitchar; Tptr lokid, eqkid, hikid; } Tnode; 

The value stored at the node is splitchar, and the three pointers represent the three children. The root of the tree is declared to be Tptr root. We will represent every character in each string, including the null character that terminates it.

(Video) Ternary Search | Ternary Search with example | Easy explanation of Ternary Search

Membership Searching

We begin with a recursive version of the search function. It returns 1 if string s is in the subtree rooted at p, and 0 otherwise; it is originally called as rsearch(root, s):

int rsearch(Tptr p, char *s) { if (!p) return 0; if (*s < p->splitchar) return rsearch(p->lokid, s); else if (*s > p->splitchar) return rsearch(p->hikid, s); else { if (*s == 0) return 1; return rsearch(p->eqkid, ++s); } } 

The first if returns 0 if the search has run off the end of the tree. The next two if statements take the low and high branches as appropriate. The final else branch returns 1 if the current character is the end-of-string character 0, and otherwise moves to the next input character and to the equal branch.

Some programmers might feel more comfortable with the iterative version of the search function (which has only one argument):

int search(char *s) { Tptr p; p = root; while (p) { if (*s < p->splitchar) p = p->lokid; else if (*s == p->splitchar) { if (*s++ == 0) return 1; p = p->eqkid; } else p = p->hikid; } return 0; } 

This is substantially faster on some compilers, and we'll use it in later experiments. On most optimizing compilers, though, the run time of the recursive version is within a few percent of the iterative version.

Both versions of the search use a pattern that we will see repeatedly: If the search character is less, go to lokid; if it is greater, go to hikid; if it is equal, go to the next character and eqkid. The following code illustrates that shorter is not always cleaner, simpler, faster, or better:

(Video) Ternary Search Trees Explained and Implemented in Java with Examples | TST | Geekific

int rsearch2(Tptr p, char *s) { return (!p ? 0 : ( *s == p->splitchar ? (*s ? rsearch2(p->eqkid, ++s) : 1) : (rsearch2(*s < p->splitchar ? p->lokid : p->hikid, s)) )); } 

FAQs

How does a ternary search tree work? ›

The ternary search tree or TST is another data structure it's another search tree that's somewhere

What is ternary search in data structure? ›

Ternary search is a decrease(by constant) and conquer algorithm that can be used to find an element in an array. It is similar to binary search where we divide the array into two parts but in this algorithm, we divide the given array into three parts and determine which has the key (searched element).

Is ternary search faster than binary? ›

The time complexity of ternary search is O(log3 n). Is binary search better than ternary search? Yes, in terms of complexity, binary search is better than ternary search.

What is binary search tree with example? ›

The binary search tree is an advanced algorithm used for analyzing the node, its left and right branches, which are modeled in a tree structure and returning the value. The BST is devised on the architecture of a basic binary search algorithm; hence it enables faster lookups, insertions, and removals of nodes.

What is the height of ternary tree? ›

4. What is the Height of the root node of ternary tree? Explanation: Height of ternary tree is defined as the length of path from root to deepest node in tree. Therefore, height off root node in ternary tree is 0.

What are binary trees in data structure? ›

A binary tree is a rooted tree that is also an ordered tree (a.k.a. plane tree) in which every node has at most two children. A rooted tree naturally imparts a notion of levels (distance from the root), thus for every node a notion of children may be defined as the nodes connected to it a level below.

How many types of searching algorithms are there? ›

Search algorithms can be classified based on their mechanism of searching into three types of algorithms: linear, binary, and hashing.

What is ternary operator in C? ›

Ternary Operator in C is an operator which takes three operands or variables, unlike the other operators which take one or two operands. Ternary operator in C is also known as Conditional Operator. It is a way to shorten the simple if-else code of the block.

What is interpolation search technique? ›

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957.

Is ternary better than binary? ›

Mathematically, ternary coding is more efficient than binary coding. It is little used in computation because technology for binary processing is already established and the implementation of ternary coding is more complicated, but remains relevant in algorithms that use decision trees and in communications.

Why use binary search if there is ternary search? ›

In a binary search, you always eliminate half the list. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list.

Is ternary search divide and conquer? ›

A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two thirds. A ternary search is an example of a divide and conquer algorithm (see search algorithm).

What is difference between binary tree and binary search tree? ›

A Binary Tree is a non-linear data structure in which a node can have 0, 1 or 2 nodes. Individually, each node consists of a left pointer, right pointer and data element. A Binary Search Tree is an organized binary tree with a structured organization of nodes. Each subtree must also be of that particular structure.

What are the types of binary search tree? ›

Here are each of the binary tree types in detail:
  • Full Binary Tree. It is a special kind of a binary tree that has either zero children or two children. ...
  • Complete Binary Tree. ...
  • Perfect Binary Tree. ...
  • Balanced Binary Tree. ...
  • Degenerate Binary Tree.
29 Sept 2022

What are the two methods of binary tree implementation? ›

Trees can be represented in two ways as listed below: Dynamic Node Representation (Linked Representation). Array Representation (Sequential Representation).

How many nodes tree can have? ›

If binary tree has height h, maximum number of nodes will be when all levels are completely full. Total number of nodes will be 2^0 + 2^1 + …. 2^h = 2^(h+1)-1. For example, the binary tree shown in Figure 2(b) with height 2 has 2^(2+1)-1 = 7 nodes.

Can a tree have more than 2 children? ›

A node can have any number of children. A leaf is a node with no children. An internal node is a non-leaf node Siblings are nodes with the same parent. The ancestors of a node d are the nodes on the path from d to the root.

How many binary search trees are possible with 4 nodes justify? ›

Enumerating Binary Trees

There are 14 different (shaped) binary trees with four nodes.

What is binary search tree in algorithm? ›

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.

What are the different types of tree in data structure? ›

Binary Search tree can be applied for searching an element in a set of elements. Heap trees are used for heap sort. Modern routers use a type of tree called Tries for storing routing information. The B-Trees and the T-Trees are mostly used by popular databases to store their data.

What is the fastest search algorithm? ›

Binary search manual calculation

According to a simulation conducted by researchers, it is known that Binary search is commonly the fastest searching algorithm. A binary search is performed for the ordered list. This idea makes everything make sense that we can compare each element in a list systematically.

Which searching technique is best? ›

The binary search algorithm works on the principle of divide and conquer and it is considered the best searching algorithm because it's faster to run.

What are the 2 types of searching algorithms? ›

In searching, there are two types: sequential search and interval search. Almost every search algorithm falls into one of these two categories. Linear and binary searches are two simple and easy-to-implement algorithms, with binary algorithms performing faster than linear algorithms.

Why is it called ternary operator? ›

Since the Conditional Operator '?:' takes three operands to work, hence they are also called ternary operators.

What is ternary operator with example? ›

It helps to think of the ternary operator as a shorthand way or writing an if-else statement. Here's a simple decision-making example using if and else: int a = 10, b = 20, c; if (a < b) { c = a; } else { c = b; } printf("%d", c); This example takes more than 10 lines, but that isn't necessary.

How do ternary operators work? ›

The conditional (ternary) operator is the only JavaScript operator that takes three operands: a condition followed by a question mark ( ? ), then an expression to execute if the condition is truthy followed by a colon ( : ), and finally the expression to execute if the condition is falsy.

What is difference between binary search and interpolation search? ›

Binary Search goes to the middle element to check irrespective of search-key. On the other hand, Interpolation Search may go to different locations according to search-key. If the value of the search-key is close to the last element, Interpolation Search is likely to start search toward the end side.

What are the types of searching? ›

Types of searches: transactional, navigational, informational.

What is sublist search algorithm? ›

The sublist search algorithm works by comparing the first element of the first list with the first element of the second list. If the two values don't match, it goes to the next element of the second list.

Why dont we use ternary? ›

A ternary bit is known as a trit. The reason we can't use ternary logic comes down to the way transistors are stacked in a computer—something called “gates”—and how they're used to carry out math. Gates take two inputs, execute a task on them, and then return one output.

Do quantum computers use binary? ›

On the most basic hardware level, quantum computers differ from classical computers because they are not binary — rather than working with bits that are in one of two states, quantum processors work with “qubits” that are in both of two states simultaneously.

What replaced binary code? ›

A ternary computer, also called trinary computer, is one that uses ternary logic (i.e., base 3) instead of the more common binary system (i.e., base 2) in its calculations. This means it uses trits instead of bits, as most computers do.

Does ternary search perform better than binary search? ›

Thus, we can say that Binary search is faster than Ternary search. This happens because of the increase in the number of comparisons in Ternary search. In simple words, the reduction in the number of iterations in Ternary search is not able to compensate for the increase in comparisons.

Why binary search is the best? ›

The main advantage of using binary search is that it does not scan each element in the list. Instead of scanning each element, it performs the searching to the half of the list. So, the binary search takes less time to search an element as compared to a linear search.

Is quad search faster than binary search? ›

The results obtained shows that binary search is 1.98 times faster than linear search on a dual-core and 3.83 times faster on quad-core machine.

What is the time complexity of ternary search? ›

At first look, it seems that ternary search might be faster than binary search as its time complexity on an input containing n items should be O(log3n), which is less than the time complexity of binary search O(log2n). Before analyzing this claim, let's take a look at its C, Java, and Python implementation first.

What is the recurrence relation of ternary search? ›

Recurrence relation for ternary search is T(n) = T(n/3) + O(1) or even T(n) = T(2n/3) + O(1) . The constant hidden in this O(1) depends on concrete implementation and how analysis was conducted. It could be 4 or 3 , or some other value.

Which search uses divide and conquer algorithm? ›

In binary search, on a sorted array of numbers, we divide (decrease) the array of numbers(search space), conquer the sub problems by recursively looking at the middle point for our target and splitting until we find our target the base case condition.

Which technique can be used to perform DFS and BFS on a ternary tree? ›

Inorder Traversal (Practice):

Which of the following is the implementation of the ternary tree? ›

Explanation: Ternary tree is used to implement ternary search tree and ternary heap. While AVL Tree, hash Table, dictionary are different types of Data Structures.

How do I make AB tree of order 5? ›

Example B-Tree

The following is an example of a B-tree of order 5. This means that (other that the root node) all internal nodes have at least ceil(5 / 2) = ceil(2.5) = 3 children (and hence at least 2 keys). Of course, the maximum number of children that a node can have is 5 (so that 4 is the maximum number of keys).

What is TST in Java? ›

The TST class represents an symbol table of key-value pairs, with string keys and generic values. It supports the usual put, get, contains, delete, size, and is-empty methods.

Why DFS is better than BFS? ›

BFS is better when target is closer to Source. DFS is better when target is far from source. As BFS considers all neighbour so it is not suitable for decision tree used in puzzle games. DFS is more suitable for decision tree.

Which is faster DFS or BFS? ›

BFS, Breadth-First Search, is a vertex-based technique for finding the shortest path in the graph. It uses a Queue data structure that follows first in first out. In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. It is slower than DFS.

What are the 3 depth traversal for a tree data structure? ›

Types of Tree Traversal in Data Structure

In-order, pre-order, and post-order are the three most frequent ways to go over them in depth-first.

What is the recurrence relation of ternary search? ›

Recurrence relation for ternary search is T(n) = T(n/3) + O(1) or even T(n) = T(2n/3) + O(1) . The constant hidden in this O(1) depends on concrete implementation and how analysis was conducted. It could be 4 or 3 , or some other value.

Can a tree have more than 2 children? ›

A node can have any number of children. A leaf is a node with no children. An internal node is a non-leaf node Siblings are nodes with the same parent. The ancestors of a node d are the nodes on the path from d to the root.

What is the height of a binary search tree? ›

The height of a binary tree is the height of the root node in the whole binary tree. In other words, the height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node. A similar concept in a binary tree is the depth of the tree.

What is a 5 way B-tree? ›

DEF: A B-Tree of order 5 is an 5-way tree such that 1. All leaf nodes are at the same level. 2. All non-leaf nodes (except the root) have at most 5 and at least 2 children.

Why are B trees used in databases? ›

In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.

Can a node have 3 children? ›

In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents.

What is the maximum number of nodes in a ternary tree of height h? ›

For complete ternary tree tree(k=3) total no. of nodes = [(3^(h+1))-1]/(h-1). So for height 3 the total no. of nodes will be 40.

What is the height of binary search tree in worst case? ›

Since a binary search tree is not guarenteed to be balanced in any way, the worst case height of a tree with n nodes is n-1. Therefore, the worst case run time for insert is O(n).

Videos

1. 013 Ternary search trees introduction
(LINUX EXPLORER)
2. Advanced Data Structures: TST Insert and Remove
(Niema Moshiri)
3. 148, TSTree1
(Abbas A)
4. AUTO COMPLETE USING TERNARY SEARCH TREES
(Next Generation Computing and Algorithms)
5. 014 Ternary search trees implementation I
(LINUX EXPLORER)
6. Tries Ternary Search Tries 22 42
(jaratanradnus)
Top Articles
Latest Posts
Article information

Author: Nathanael Baumbach

Last Updated: 02/25/2023

Views: 6604

Rating: 4.4 / 5 (55 voted)

Reviews: 86% of readers found this page helpful

Author information

Name: Nathanael Baumbach

Birthday: 1998-12-02

Address: Apt. 829 751 Glover View, West Orlando, IN 22436

Phone: +901025288581

Job: Internal IT Coordinator

Hobby: Gunsmithing, Motor sports, Flying, Skiing, Hooping, Lego building, Ice skating

Introduction: My name is Nathanael Baumbach, I am a fantastic, nice, victorious, brave, healthy, cute, glorious person who loves writing and wants to share my knowledge and understanding with you.