top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

What is a ternary search tree? Explain it with basic operations of a tree.

+6 votes
819 views
What is a ternary search tree? Explain it with basic operations of a tree.
posted Jun 28, 2016 by Shivam Kumar Pandey

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
A ternary search tree is a type of tree where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two.
thanks but you are missing its program of basic operations

2 Answers

+1 vote
 
Best answer

Ternary search Tree is a extended concept of BST , as the names ternary suggests it has three nodes, left node for storing value less than the root, middle node for storing equal value to the root and right node for storing value greater than that of root.

          3
        / | \
       2  3  4

the above tree is a typical ternary search Tree.
Applications of ternary search trees:
1. Ternary search trees are efficient for queries like “Given a word, find the next word in dictionary(near-neighbor lookups)” or “Find all telephone numbers starting with 9342 or “typing few starting characters in a web browser displays all website names with this prefix”(Auto complete feature)”.

  1. Used in spell checks: Ternary search trees can be used as a dictionary to store all the words. Once the word is typed in an editor, the word can be parallely searched in the ternary search tree to check for correct spelling.

to understand basic operation of a Ternary Search Tree follow this link:http://www.geeksforgeeks.org/ternary-search-tree/

answer Jun 30, 2016 by Shahsikant Dwivedi
Thanks Shashikant and you made it simple to understand and I think its applications in real life is tough part but it is very efficient. isn't?
yes indeed, shivam
–2 votes

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.

A binary search tree for 12 words.

Digital search tries store strings character by character. given Figure 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 ). 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!
enter image description here

answer Jun 30, 2016 by Vrije Mani Upadhyay
...