binary search tree

(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).

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

Implementation

Ben Pfaff's insert, delete, search, copy, etc. (literate C); Kaz Kylheku's Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. insert (C), insert (C), search (C), and insert, search, delete, and various traversals (Modula-2) (use must be acknowledged).

More information

A demonstration.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Tue Jul 5 10:28:41 2005.
HTML page formatted Wed Oct 26 09:47:14 2005.

Cite this as:
Paul E. Black, "binary search tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/binarySearchTree.html