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 Black.
Entry modified 26 January 2015.
HTML page formatted Fri Feb 23 10:06:07 2018.
Cite this as:
Paul E. Black, "binary search tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 26 January 2015. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/binarySearchTree.html