(data structure)
Definition: A binary tree where every node's left subtree has keys less than the node's key, and every right subtree has keys greater than the node's key.
Generalization (I am a kind of ...)
binary tree, search tree.
Specialization (... is a kind of me.)
AVL tree, splay tree, threaded tree, randomized binary search tree, discrete interval encoding tree.
Aggregate parent (I am a part of or used in ...)
treesort (1).
See also relaxed balance, ternary search tree, move-to-root heuristic, jump list.
Note: A binary search tree is almost always implemented with pointers, but may have a variety of constraints on how it is composed.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 18 August 2008.
HTML page formatted Mon Aug 25 09:01:40 2008.
Cite this as:
Paul E. Black, "binary search tree", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 18 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/binarySearchTree.html