Binary search tree: Difference between revisions

Revision as of 21:36, 11 October 2023

Revision as of 21:40, 11 October 2023

Line 18:

[[File:Binary search tree.svg|right|upright=0.8|thumb|Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn.]]

In [[computer science]], a '''binary search tree''' ('''BST'''), also called an '''ordered''' or '''sorted binary tree''', is a [[Rooted tree|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 [[directlyTime proportionalcomplexity#Linear time|linear]] with respect to the height of the tree.

Binary search trees allow [[Binary search algorithm|binary search]] for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of [[binary logarithm]]. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to [[Conway Berners-Lee]] and [[David_Wheeler_(computer_scientist)|David Wheeler]].