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 ...)
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.
A animation (Java).
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 12 December 2011.
HTML page formatted Mon Dec 12 10:22:39 2011.
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. 12 December 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/binarySearchTree.html