In computer science, a search tree is a tree data structure in whose nodes data values can be stored from some ordered set, which is such that in an in-order traversal of the tree the nodes are visited in ascending order of the stored values. Each subtree of a search tree is by itself again a search tree.
Search trees can implement the data type of (finite) multisets. The advantage of using search trees is that the test for membership can be performed efficiently provided that the tree is reasonably balanced, that is, the leaves of the tree are at comparable depths. Various search-tree data structures exist, several of which also allow efficient insertion and deletion of elements, which operations then have to maintain tree balance. If the multiset being represented is immutable, this is not an issue.
Search trees can also implement associative arrays by storing key–value pairs, where the ordering is based on the key part of these pairs.
In some kinds of search trees the data values are all stored in the leaves of the tree. In that case some additional information needs to be stored in the internal tree nodes to make efficient operations possible.
Examples
Some examples of search-tree data structures are:
- Red-black trees and splay trees, both of which are instances of self-balancing binary search trees;
- Ternary search trees, in which each internal node has exactly three children;
- B trees, commonly used in databases;
- B+ trees, like B trees but with all data values stored in the leaves;
- van Emde Boas trees, very efficient if the data values are fixed-size integers.
See also
- Trie, a tree data structure that allows searching for strings, which however does not store the actual data values in the nodes.
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
