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
Wikidata facts
- Image
- Binary search tree.svg
Show 4 more facts
- Commons category
- Binary search trees
- time of discovery or invention
- 1960-00-00
- inception
- 1960-01-01
- Stack Exchange tag
- stackoverflow.com/tags/binary-search-tree
Sources (3)
via Wikidata · CC0
~14 min read
Article
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.
Connections
tree
Entity
tree traversal
Entity
B-tree
Entity
binary search algorithm
Entity
linked list
Entity
red–black tree
Entity
AVL tree
Entity
abstract data type
Entity
time complexity
Entity
set
Entity
self-balancing binary search tree
Entity
computer science
Entity
International Standard Book Number
Entity
Stanford University
Entity
digital object identifier
Entity
International Standard Serial Number
Entity
Cornell University
Entity
Donald Knuth
Entity
University of Toronto
Entity
data structure
Entity