binary search tree
Sign in to saveAlso known as BST, ordered binary tree, sorted binary tree
data structure in tree form with 0, 1, or 2 children per node, sorted for fast lookup
Key facts
- Type
- tree
- Invented by
- P.F. Windley, A.D. Booth , A.J.T. Colin , and T.N. Hibbard
- Operation
- Average
- Search
- Θ(log n )
- Insert
- Θ(log n )
- Delete
- Θ(log n )
- Space
- Θ( n )
via Wikipedia infobox
~14 min read
Encyclopedic overview
Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root.
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
Excerpted from Wikipedia’s “binary search tree” article, available under the CC BY-SA 4.0 licence.