Editing Binary search tree (section)

{{good article}}
{{Short description|Rooted binary tree data structure}}
{{Infobox data structure
|name=Binary search tree
|type=tree
|invented_by=P.F. Windley, [[Andrew Donald Booth|A.D. Booth]], [[Andrew Colin|A.J.T. Colin]], and [[Thomas N. Hibbard|T.N. Hibbard]]
|invented_year=1960
|space_avg={{math|O(''n'')}}
|space_worst={{math|O(''n'')}}
|search_avg={{math|O(log ''n'')}}
|search_worst={{math|O(''n'')}}
|insert_avg={{math|O(log ''n'')}}
|insert_worst={{math|O(''n'')}}
|delete_avg={{math|O(log ''n'')}}
|delete_worst={{math|O(''n'')}}
}}

[[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.]]

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 [[Time complexity#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]].

The performance of a binary search tree is dependent on the order of insertion of the nodes into the tree since arbitrary insertions may lead to degeneracy; several variations of the binary search tree can be built with guaranteed worst-case performance. The basic operations include: search, traversal, insert and delete. BSTs with guaranteed worst-case complexities perform better than an unsorted array, which would require [[linear time|linear search time]].

The [[Computational complexity theory|complexity analysis]] of BST shows that, [[Best, worst and average case|on average]], the insert, delete and search takes <math>O(\log n)</math> for <math>n</math> nodes. In the worst case, they degrade to that of a singly linked list: <math>O(n)</math>. To address the boundless increase of the tree height with arbitrary insertions and deletions, [[Self-balancing_binary_search_tree|self-balancing]] variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm. [[AVL trees]] were the first self-balancing binary search trees, invented in 1962 by [[Georgy Adelson-Velsky]] and [[Evgenii Landis]].

Binary search trees can be used to implement [[abstract data type]]s such as [[Set (abstract data type)|dynamic sets]], [[lookup table]]s and [[priority queues]], and used in [[sorting algorithm]]s such as [[tree sort]].