Ternary search tree

Ternary search tree

In computer science, a ternary search tree (trie,TST) is a ternary (three-way) tree data structure which combines 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.

A standard digital trie stores strings; each node represents a particular string prefix, and branches "N" ways, where "N" is the size of the set of characters which could come next in the string. If "N" is large, the nodes may be very large even if the trie is sparsely populated. A ternary search tree may be thought of as a digital trie in which each "N"-way branching node has been replaced with a binary search tree; there are only as many nodes in each of these binary trees as there would be non-empty branches of the corresponding trie node, and the binary nodes have one extra link each, corresponding to what the trie node would link to for that branch.

Tries had traditionally used nodes of fixed size. Each node contained a fixed number of pointers. This led to wastage of space when few keys were used. As an alternative, the nodes were allowed to have variable sizes, by considering each node a doubly-linked list that stored only the necessary pointers. But this made the search less efficient, and wasted even more space as the structure grew. Conceptually, the structure obtained by replacing the doubly-linked list with a binary search tree is same as the TST. Now the search is more efficient because BST searching is much faster than traversing the linked list.

The construction of a binary search tree is closely related to quicksort. Similarly the construction of a TST is closely related to quicksort with three-way partitioning (quick-radix sort, to be exact).

ee also

*Ternary search
*Search algorithm
*Binary search
*Interpolation search
*Linear search

References

*"Algorithms in C/C++/Java", third ed. (Parts 1-4), Robert Sedgewick, Addison Wesley.

External links

* [http://www.cs.princeton.edu/~rs/strings/ Ternary Search Trees]
* [http://www.ddj.com/documents/s=921/ddj9804a/ Ternary Search Trees (Dr. Dobbs)]
* [http://search.cpan.org/~mrogaski/Tree-Ternary-0.03/Ternary.pm Tree::Ternary (Perl module)]
* [http://dasnar.sdf-eu.org/res/ctst-README.html Ternary Search Tree code]
* [http://abc.se/~re/code/tst/ STL-compliant Ternary Search Tree in C++]
* [http://ternary.sourceforge.net Ternary Search Tree in C++]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • Tree traversal — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… …   Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Metric tree — This article is about the data structure. For the type of metric space, see Real tree. A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle… …   Wikipedia

  • Cover tree — The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed up of a nearest neighbor search. It is a refinement of the Navigating Net data structure, and related to a variety of other data… …   Wikipedia

  • Dancing tree — For the film Dancing tree, see Dancing tree (film) In computer science, a dancing tree is a tree data structure, which is similar to B+ tree. Invented by Hans Reiser, for use by the Reiser4 file system. As opposed to self balancing binary search… …   Wikipedia

  • Hash tree — A binary hash tree In cryptography and computer science Hash trees or Merkle trees are a type of data structure[citation needed] which contains a tree of summary information about a larger piece of da …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”