Binary search tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a binary search tree (BST), also called an ordered or sorted binary tree, is a <a href="/facts/Rooted_tree/TCWk4Joy">rooted</a> <a href="/facts/Binary_tree/TDV7GMpu">binary tree</a> <a href="/facts/Data_structure/yNsNvL1I">data structure</a> 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 <a href="/facts/Time_complexity/77T62gmf">time complexity</a> of operations on the binary search tree is <a href="/facts/Time_complexity/77T62gmf">linear</a> with respect to the height of the tree.
Binary search trees allow <a href="/facts/Binary_search_algorithm/FFmQzunc">binary search</a> 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 <a href="/facts/Binary_logarithm/Uy7kAtRm">binary logarithm</a>. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to <a href="/facts/Conway_Berners-Lee/gN4EVVA7">Conway Berners-Lee</a> and <a href="/facts/David_Wheeler_(computer_scientist)/eMm8hmrz">David Wheeler</a>.
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 <a href="/facts/Linear_time/77T62gmf">linear search time</a>.
The <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity analysis</a> of BST shows that, <a href="/facts/Best,_worst_and_average_case/Ed9ekH30">on average</a>, the insert, delete and search takes 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 for 
 
 
 
 n
 
 
 {\displaystyle n}
 
 nodes. In the worst case, they degrade to that of a singly linked list: 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
. To address the boundless increase of the tree height with arbitrary insertions and deletions, <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing</a> variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm. <a href="/facts/AVL_trees/DfexIbS6">AVL trees</a> were the first self-balancing binary search trees, invented in 1962 by <a href="/facts/Georgy_Adelson-Velsky/1CpLURAR">Georgy Adelson-Velsky</a> and <a href="/facts/Evgenii_Landis/FPlw09va">Evgenii Landis</a>.
Binary search trees can be used to implement <a href="/facts/Abstract_data_type/BaVGSHNP">abstract data types</a> such as <a href="/facts/Set_(abstract_data_type)/ovoXUmF9">dynamic sets</a>, <a href="/facts/Lookup_table/ULPEAGTJ">lookup tables</a> and <a href="/facts/Priority_queues/1uXVo4Uf">priority queues</a>, and used in <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting algorithms</a> such as <a href="/facts/Tree_sort/t3PnVBnK">tree sort</a>.

Binary search tree open-in-new

Binary search tree