Definition: A tree where every subtree of a node has keys less than any other subtree of the node to its right. The keys in a node are conceptually between subtrees and are greater than any keys in subtrees to its left and less than any keys in subtrees to its right.
Specialization (... is a kind of me.)
binary search tree, B-tree, (a, b)-tree, ternary search tree.
See also search tree property, move-to-root heuristic, k-d tree.
Note: A search tree that is also a binary tree is a binary search tree.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 December 2005.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "search tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 December 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/searchtree.html