View source for Binary search tree

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

==History==
The binary search tree algorithm was discovered independently by several researchers, including P.F. Windley, [[Andrew Donald Booth]], [[Andrew Colin]], [[Thomas N. Hibbard]].<ref name="computer_journal89">{{cite journal|journal=[[The Computer Journal]]|date=1 January 1989|doi=10.1093/comjnl/32.1.68|volume=32|issue=1|pages=68–69|first1=J.|last1=Culberson|first2=J. I.|last2=Munro|url=https://academic.oup.com/comjnl/article/32/1/68/341965?login=true|doi-access=free|title=Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations}}</ref><ref>{{cite journal|journal=[[Algorithmica]]|publisher=[[Springer Publishing]], [[University of Waterloo]]|title= Analysis of the standard deletion algorithms in exact fit domain binary search trees|date=28 July 1986|doi=10.1007/BF01840390|url=https://link.springer.com/article/10.1007%2FBF01840390|first1=J.|last1=Culberson|first2=J. I.|last2=Munro|volume=5 |issue=1–4 |page=297|s2cid=971813 }}</ref> The algorithm is attributed to [[Conway Berners-Lee]] and [[David Wheeler (computer scientist)|David Wheeler]], who used it for storing [[labeled data]] in [[magnetic tape]]s in 1960.<ref name="windley60">{{cite journal|journal=[[The Computer Journal]]|date=1 January 1960|doi=10.1093/comjnl/3.2.84|url=https://academic.oup.com/comjnl/article/3/2/84/504799|author=P. F. Windley|volume=3|issue=2|page=84|title= Trees, Forests and Rearranging|doi-access=free}}</ref> One of the earliest and popular binary search tree algorithm is that of Hibbard.<ref name="computer_journal89" />

The time complexities of a binary search tree increases boundlessly with the tree height if the nodes are inserted in an arbitrary order, therefore [[self-balancing binary search tree]]s were introduced to bound the height of the tree to <math>O(\log n)</math>.<ref name="Knuth98">{{cite book|title=The Art of Computer Programming|first=Donald|last=Knuth|author-link=Donald Knuth|publisher=[[Addison-Wesley]]|year=1998|chapter=Section 6.2.3: Balanced Trees|pages=458–481|volume=3|edition=2|url=https://ia801604.us.archive.org/17/items/B-001-001-250/B-001-001-250.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://ia801604.us.archive.org/17/items/B-001-001-250/B-001-001-250.pdf |archive-date=2022-10-09 |url-status=live|isbn=978-0201896855
}}</ref> Various '''height-balanced''' binary search trees were introduced to confine the tree height, such as [[AVL tree]]s, [[Treap]]s, and [[red–black tree]]s.<ref>Paul E. Black, "red-black tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 November 2019. (accessed May 19 2022) from: https://www.nist.gov/dads/HTML/redblack.html</ref> 

The AVL tree was invented by [[Georgy Adelson-Velsky]] and [[Evgenii Landis]] in 1962 for the efficient organization of information.<ref>{{cite web|url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html|publisher=[[Cornell University]], Department of Computer Science|access-date=19 May 2022|title=CS 312 Lecture: AVL Trees|first=Andrew|last=Myers|url-status=live|archive-url=https://web.archive.org/web/20210427195749/http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html|archive-date=27 April 2021}}</ref><ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=An algorithm for the organization of information|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref> It was the first self-balancing binary search tree to be invented.<ref>{{cite web|url=http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|access-date=19 May 2022|url-status=live|archive-url=https://web.archive.org/web/20190214212633/http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|title=CSC263: Balanced BSTs, AVL tree|first=Toniann|last=Pitassi|year=2015|publisher=[[University of Toronto]], Department of Computer Science|archive-date=14 February 2019|page=6}}</ref>

==Overview==
A binary search tree is a rooted binary tree in which nodes are arranged in [[total order#Strict and non-strict total orders|strict total order]] in which the nodes with keys greater than any particular node ''A'' is stored on the right [[Tree (data structure)#Terminology|sub-trees]] to that node ''A'' and the nodes with keys equal to or less than ''A'' are stored on the left sub-trees to ''A,'' satisfying the [[binary search]] property.<ref name="reema18">{{cite book|title= Data Structures Using C|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription|chapter=Hashing and Collision}}</ref>{{rp|p=298}}<ref name="algo_cormen">{{cite book|last1=Cormen|first1=Thomas H. |author-link1=Thomas H. Cormen|last2=Leiserson|first2=Charles E. |author-link2=Charles E. Leiserson|last3=Rivest|first3=Ronald L. |author-link3=Ronald L. Rivest|author-link4=Clifford Stein|first4=Clifford |last4=Stein|url=https://mitpress.mit.edu/books/introduction-algorithms-second-edition|title=Introduction to Algorithms|edition=2nd|year=2001|publisher=[[MIT Press]]|isbn=0-262-03293-7}}</ref>{{rp|287}}

Binary search trees are also efficacious in [[sorting algorithm|sorting]]s and [[search algorithm]]s. However, the search complexity of a BST depends upon the order in which the nodes are inserted and deleted; since in worst case, successive operations in the binary search tree may lead to degeneracy and form a [[singly linked list]] (or "unbalanced tree") like structure, thus has the same worst-case complexity as a [[linked list]].<ref>{{cite journal|journal=[[The Computer Journal]]|volume=25|issue=1|date=1 February 1982|doi=10.1093/comjnl/25.1.158|author1=R. A. Frost|author2=M. M. Peterson|page=158|url=https://academic.oup.com/comjnl/article/25/1/158/527326|publisher=[[Oxford University Press]]|title=A Short Note on Binary Search Trees}}</ref>{{r|reema18|p=299-302}} 

Binary search trees are also a fundamental data structure used in construction of [[abstract data structures]] such as sets, [[set (computer science)#Multiset|multisets]], and [[associative array]]s.

==Operations==
===Searching===
Searching in a binary search tree for a specific key can be programmed [[recursion (computer science)|recursively]] or [[iteration#Computing|iteratively]].

Searching begins by examining the [[root node]]. If the tree is [[Null pointer|{{math|{{text|nil}}}}]], the key being searched for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and the node is returned. If the key is less than that of the root, the search proceeds by examining the left subtree. Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree. This process is repeated until the key is found or the remaining subtree is <math>\text{nil}</math>. If the searched key is not found after a <math>\text{nil}</math> subtree is reached, then the key is not present in the tree.{{r|algo_cormen|pp=290-291}}

====Recursive search====
The following [[pseudocode]] implements the BST search procedure through [[recursion (computer science)|recursion]].<ref name="algo_cormen" />{{rp|290}}
{|
|- style="vertical-align:top"
|
 Recursive-Tree-Search(x, key)
     '''if''' x = NIL '''or''' key = x.key '''then'''
         '''return''' x
     '''if''' key < x.key '''then'''
         '''return''' Recursive-Tree-Search(x.left, key)
     '''else'''
         '''return''' Recursive-Tree-Search(x.right, key)
     '''end if'''
|}
The recursive procedure continues until a <math>\text{nil}</math> or the <math>\text{key}</math> being searched for are encountered.

====Iterative search====
The recursive version of the search can be "unrolled" into a [[while loop]]. On most machines, the iterative version is found to be more [[Computer performance|efficient]].<ref name="algo_cormen" />{{rp|291}}
{|
|- style="vertical-align:top"
|
 Iterative-Tree-Search(x, key)
     '''while''' x &ne; NIL '''and''' key &ne; x.key '''do'''
         '''if''' key < x.key '''then'''
             x := x.left
         '''else'''
             x := x.right
         '''end if'''
     '''repeat'''
     '''return''' x
|}
Since the search may proceed till some [[leaf node]], the running time complexity of BST search is <math>O(h)</math> where <math>h</math> is the [[Tree (data structure)#Terminology|height of the tree]]. However, the worst case for BST search is <math>O(n)</math> where <math>n</math> is the total number of nodes in the BST, because an unbalanced BST may degenerate to a linked list. However, if the BST is [[height-balanced tree|height-balanced]] the height is <math>O(\log n)</math>.<ref name="algo_cormen" />{{rp|290}}

====Successor and predecessor====
For certain operations, given a node <math>\text{x}</math>, finding the successor or predecessor of <math>\text{x}</math> is crucial. Assuming all the keys of a BST are distinct, the successor of a node <math>\text{x}</math> in a BST is the node with the smallest key greater than <math>\text{x}</math>'s key. On the other hand, the predecessor of a node <math>\text{x}</math> in a BST is the node with the largest key smaller than <math>\text{x}</math>'s key. The following pseudocode finds the successor and predecessor of a node <math>\text{x}</math> in a BST.<ref>{{cite web|url=https://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-url=https://web.archive.org/web/20210413045057/http://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-date=13 April 2021|page=12|publisher=[[University of Texas at Arlington]]|access-date=17 May 2021|url-status=live|title=Design and Analysis of Algorithms|author=Junzhou Huang}}</ref><ref>{{cite web |author=Ray |first=Ray |title=Binary Search Tree |url=https://cs.lmu.edu/~ray/notes/binarysearchtrees/ |access-date=17 May 2022 |publisher=[[Loyola Marymount University]], Department of Computer Science}}</ref><ref name="algo_cormen" />{{rp|292–293}}
{|
|- style="vertical-align:top"
|
  BST-Successor(x)
      '''if''' x.right &ne; NIL '''then'''
          '''return''' BST-Minimum(x.right)
      '''end if'''
      y := x.parent
      '''while''' y &ne; NIL '''and''' x = y.right '''do'''
          x := y
          y := y.parent
      '''repeat'''
      '''return''' y
|
  BST-Predecessor(x)
      '''if''' x.left &ne; NIL '''then'''
          '''return''' BST-Maximum(x.left)
      '''end if'''
      y := x.parent
      '''while''' y &ne; NIL '''and''' x = y.left '''do'''
          x := y
          y := y.parent
      '''repeat'''
      '''return''' y
|}
Operations such as finding a node in a BST whose key is the maximum or minimum are critical in certain operations, such as determining the successor and predecessor of nodes. Following is the pseudocode for the operations.<ref name="algo_cormen" />{{rp|291–292}}
{|
|- style="vertical-align:top"
|
  BST-Maximum(x)
      '''while''' x.right &ne; NIL '''do'''
          x := x.right
      '''repeat'''
      '''return''' x
|
  BST-Minimum(x)
      '''while''' x.left &ne; NIL '''do'''
          x := x.left
      '''repeat'''
      '''return''' x
|}

===Insertion===
Operations such as insertion and deletion cause the BST representation to change dynamically. The data structure must be modified in such a way that the properties of BST continue to hold. New nodes are inserted as [[leaf nodes]] in the BST.<ref name="algo_cormen" />{{rp|294–295}} Following is an iterative implementation of the insertion operation.<ref name="algo_cormen" />{{rp|294}}
{|
|- style="vertical-align:top"
|
 1    BST-Insert(T, z)
 2      y := NIL
 3      x := T.root
 4      '''while''' x &ne; NIL '''do'''
 5        y := x
 6        '''if''' z.key < x.key '''then'''
 7          x := x.left
 8        '''else'''
 9          x := x.right
 10       '''end if'''
 11     '''repeat'''
 12     z.parent := y
 13     '''if''' y = NIL '''then'''
 14       T.root := z
 15     '''else if''' z.key < y.key '''then'''
 16       y.left := z
 17     '''else'''
 18       y.right := z
 19     '''end if'''
|}
The procedure maintains a "trailing pointer" <math>\text{y}</math> as a parent of <math>\text{x}</math>. After initialization on line 2, the '''while''' loop along lines 4-11 causes the pointers to be updated. If <math>\text{y}</math> is <math>\text{nil}</math>, the BST is empty, thus <math>\text{z}</math> is inserted as the root node of the binary search tree <math>\text{T}</math>, if it is not <math>\text{nil}</math>, insertion proceeds by comparing the keys to that of <math>\text{y}</math> on the lines 15-19 and the node is inserted accordingly.<ref name="algo_cormen" />{{rp|295}}

===Deletion===
[[File:BST node deletion.png|400px|right|The node <math>\text{D}</math> to be deleted has 2 children]]
The deletion of a node, say <math>\text{Z}</math>, from the binary search tree <math>\text{BST}</math> has three cases:{{r|algo_cormen|p=295-297}}
# If <math>\text{Z}</math> is a leaf node, it is replaced by <math>\text{NIL}</math> as shown in (a).
# If <math>\text{Z}</math> has only one child, the child node of <math>\text{Z}</math> gets elevated by modifying the parent node of <math>\text{Z}</math> to point to the child node, consequently taking <math>\text{Z}</math>'s position in the tree, as shown in (b) and (c).
# If <math>\text{Z}</math> has both left and right children, the successor of <math>\text{Z}</math>, say <math>\text{Y}</math>, displaces <math>\text{Z}</math> by following the two cases:
## If <math>\text{Y}</math> is <math>\text{Z}</math>'s right child, as shown in (d), <math>\text{Y}</math> displaces <math>\text{Z}</math> and <math>\text{Y}</math>'s right child remain unchanged.
## If <math>\text{Y}</math> lies within <math>\text{Z}</math>'s right subtree but is not <math>\text{Z}</math>'s right child, as shown in (e), <math>\text{Y}</math> first gets replaced by its own right child, and then it displaces <math>\text{Z}</math>'s position in the tree.

The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}
{|
|- style="vertical-align:top"
|
 1    BST-Delete(BST, z)
 2      '''if''' z.left = NIL '''then'''
 3        Shift-Nodes(BST, z, z.right)
 4      '''else if''' z.right = NIL '''then'''
 5        Shift-Nodes(BST, z, z.left)
 6      '''else'''
 7        y := BST-Successor(z)
 8        '''if''' y.parent &ne; z '''then'''
 9          Shift-Nodes(BST, y, y.right)
 10         y.right := z.right
 11         y.right.parent := y
 12       '''end if'''
 13       Shift-Nodes(BST, z, y)
 14       y.left := z.left
 15       y.left.parent := y
 16     '''end if'''
|-
|
 1    Shift-Nodes(BST, u, v)
 2      '''if''' u.parent = NIL '''then'''
 3        BST.root := v
 4      '''else if''' u = u.parent.left '''then'''
 5        u.parent.left := v
 5      '''else'''
 6        u.parent.right := v
 7      '''end if'''
 8      '''if''' v &ne; NIL '''then'''
 9        v.parent := u.parent
 10     '''end if'''
|}
The <math>\text{BST-Delete}</math> procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. The [[helper function]] <math>\text{Shift-Nodes}</math> is used within the deletion algorithm for the purpose of replacing the node <math>\text{u}</math> with <math>\text{v}</math> in the binary search tree <math>\text{BST}</math>.{{r|algo_cormen|p=298}} This procedure handles the deletion (and substitution) of <math>\text{u}</math> from <math>\text{BST}</math>.

==Traversal==
{{Main article|Tree traversal}}
{{see also|Threaded binary tree}}
A BST can be [[Tree traversal|traversed]] through three basic algorithms: [[inorder traversal|inorder]], [[pre-order traversal|preorder]], and [[post-order traversal|postorder]] tree walks.<ref name="algo_cormen" />{{rp|287}}
*'''Inorder tree walk''': Nodes from the left subtree get visited first, followed by the root node and right subtree. Such a traversal visits all the nodes in the order of non-decreasing key sequence.
*'''Preorder tree walk''': The root node gets visited first, followed by left and right subtrees.
*'''Postorder tree walk''': Nodes from the left subtree get visited first, followed by the right subtree, and finally, the root.

Following is a recursive implementation of the tree walks.<ref name="algo_cormen" />{{rp|287–289}}
{|
|- style="vertical-align:top"
|
  Inorder-Tree-Walk(x)
    '''if''' x &ne; NIL '''then'''
      Inorder-Tree-Walk(x.left)
      ''visit node''
      Inorder-Tree-Walk(x.right)
    '''end if'''
|
  Preorder-Tree-Walk(x)
    '''if''' x &ne; NIL '''then'''
      ''visit node''
      Preorder-Tree-Walk(x.left)
      Preorder-Tree-Walk(x.right)
    '''end if'''
|
  Postorder-Tree-Walk(x)
    '''if''' x &ne; NIL '''then'''
      Postorder-Tree-Walk(x.left)
      Postorder-Tree-Walk(x.right)
      ''visit node''
    '''end if'''
|}

==Balanced binary search trees==
{{Main|Self-balancing binary search tree}}
Without rebalancing, insertions or deletions in a binary search tree may lead to degeneration, resulting in a height <math>n</math> of the tree (where <math>n</math> is number of items in a tree), so that the lookup performance is deteriorated to that of a linear search.<ref>{{cite web|url=https://www.ics.uci.edu/~thornton/ics46/Notes/BinarySearchTrees/|publisher=[[University of California, Irvine]]|year=2021|first=Alex|last=Thornton|title= ICS 46: Binary Search Trees|archive-url=https://web.archive.org/web/20210704141729/https://www.ics.uci.edu/~thornton/ics46/Notes/BinarySearchTrees/|archive-date=4 July 2021|url-status=live|access-date=21 October 2021}}</ref> Keeping the search tree balanced and height bounded by <math>O(\log n)</math> is a key to the usefulness of the binary search tree. This can be achieved by "self-balancing" mechanisms during the updation operations to the tree designed to maintain the tree height to the binary logarithmic complexity.<ref name="Knuth98" /><ref name="peter11">{{cite book|publisher=[[Cambridge University Press]]|url=https://www.cambridge.org/core/books/advanced-data-structures/D56E2269D7CEE969A3B8105AD5B9254C|title=Advanced Data Structure|date=January 2011|isbn=9780511800191|doi=10.1017/CBO9780511800191|first=Peter|last=Brass}}</ref>{{rp|p=50}}

=== Height-balanced trees ===
A tree is height-balanced if the heights of the left sub-tree and right sub-tree are guaranteed to be related by a constant factor. This property was introduced by the [[AVL tree]] and continued by the [[red–black tree]].{{r|peter11|pp=50-51}} The heights of all the nodes on the path from the root to the modified leaf node have to be observed and possibly corrected on every insert and delete operation to the tree.{{r|peter11|pp=52}}

=== Weight-balanced trees ===
{{main|Weight-balanced tree}}
In a weight-balanced tree, the criterion of a balanced tree is the number of leaves of the subtrees. The weights of the left and right subtrees differ at most by <math>1</math>.<ref>{{Cite journal|doi=10.1016/0304-3975(80)90018-3|title=On the Average Number of Rebalancing Operations in Weight-Balanced Trees|journal=Theoretical Computer Science|volume=11|issue=3|pages=303–320|year=1978|last1=Blum|first1=Norbert|last2=Mehlhorn|first2=Kurt|url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-date=2022-10-09 |url-status=live}}</ref>{{r|peter11|pp=61}} However, the difference is bound by a ratio <math>\alpha</math> of the weights, since a strong balance condition of <math>1</math> cannot be maintained with <math>O(\log n)</math> rebalancing work during insert and delete operations. The <math>\alpha</math>-weight-balanced trees gives an entire family of balance conditions, where each left and right subtrees have each at least a fraction of <math>\alpha</math> of the total weight of the subtree.{{r|peter11|pp=62}}

=== Types ===
There are several self-balanced binary search trees, including [[T-tree]],<ref>{{cite conference|url=https://archive.org/details/verylargedatabas0000inte|first1=Tobin J.|last1=Lehman|first2=Michael J.|last2=Carey|title=A Study of Index Structures for Main Memory Database Management Systems|location=Kyoto|date=25–28 August 1986|conference=Twelfth International Conference on Very Large Databases (VLDB 1986)|isbn=0-934613-18-4|url-access=registration}}</ref> [[treap]],<ref>{{Citation | contribution=Randomized Search Trees | first1=Cecilia R. | last1=Aragon | first2=Raimund | last2=Seidel | title=30th Annual Symposium on Foundations of Computer Science | contribution-url=http://faculty.washington.edu/aragon/pubs/rst89.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://faculty.washington.edu/aragon/pubs/rst89.pdf |archive-date=2022-10-09 |url-status=live | pages=540–545 | year=1989 | doi=10.1109/SFCS.1989.63531 | isbn=0-8186-1982-1 | publisher=IEEE Computer Society Press | location=Washington, D.C.| title-link=Symposium on Foundations of Computer Science }}</ref> [[red-black tree]],<ref name="Cormen2001">{{Anchor|Cormen}}{{Cite book |title=Introduction to Algorithms |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |edition=second |publisher=MIT Press |year=2001 |isbn=978-0-262-03293-3 |chapter=Red&ndash;Black Trees |pages=[https://archive.org/details/introductiontoal00corm_691/page/n735 273]–301 |title-link=Introduction to Algorithms }}</ref> [[B-tree]],<ref>{{Citation | last = Comer | first = Douglas | author-link = Douglas Comer | title = The Ubiquitous B-Tree | journal = Computing Surveys | volume = 11 | issue = 2 | pages = 123–137 | date = June 1979 | issn = 0360-0300 | doi = 10.1145/356770.356776 | s2cid = 101673 | doi-access = free }}</ref> [[2–3 tree]],<ref>{{cite book| title=The Art of Computer Programming |volume=3| chapter=6.2.4 |quote=The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. |first1=Donald M |last1=Knuth |edition=2 |isbn=9780201896855 |publisher=Addison Wesley|year=1998}}</ref> and [[Splay tree]].<ref>{{cite journal | first1 = Daniel D. | last1 = Sleator | author1-link = Daniel Sleator | first2 = Robert E. | last2 = Tarjan | author2-link = Robert Tarjan | title = Self-Adjusting Binary Search Trees | journal = [[Journal of the ACM]] | volume = 32 | issue = 3 | pages = 652–686 | year = 1985 | url = https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf | doi = 10.1145/3828.3835 | s2cid = 1165848 }}</ref>

==Examples of applications==
===Sort===
{{Main article|Tree sort}}
Binary search trees are used in sorting algorithms such as [[tree sort]], where all the elements are inserted at once and the tree is traversed at an in-order fashion.<ref>{{cite web|url=https://www.cs.princeton.edu/courses/archive/spring19/cos226/lectures/study/32BinarySearchTrees.html|publisher=[[Princeton University School of Engineering and Applied Science]]|first=Arvind|last=Narayanan|access-date=21 October 2021|title=COS226: Binary search trees|archive-url=https://web.archive.org/web/20210322040843/https://www.cs.princeton.edu/courses/archive/spring19/cos226/lectures/study/32BinarySearchTrees.html|archive-date=22 March 2021|url-status=live|year=2019|via=cs.princeton.edu}}</ref> BSTs are also used in [[quicksort]].<ref>{{cite web|url=http://mathcenter.oxford.emory.edu/site/cs171/bstQuicksortConnection/|title=A Connection Between Binary Search Trees and Quicksort|archive-url=https://web.archive.org/web/20210226103159/http://mathcenter.oxford.emory.edu/site/cs171/bstQuicksortConnection/|publisher=[[Oxford College of Emory University]], The Department of Mathematics and Computer Science|first=Li|last=Xiong|url-status=live|access-date=4 June 2022|archive-date=26 February 2021}}</ref>

===Priority queue operations===
{{main|Priority queue}}
Binary search trees are used in implementing [[priority queue]]s, using the node's key as priorities. Adding new elements to the queue follows the regular BST insertion operation but the removal operation depends on the type of priority queue:<ref>{{cite web|publisher=[[Cornell University]], [[Cornell University College of Engineering|Department of Computer Science]]|first=Andrew|last=Myers|title=CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps|url=https://www.cs.cornell.edu/courses/cs4120/2016sp/lectures/lec_heaps/|archive-date=21 October 2021|url-status=live|archive-url=https://web.archive.org/web/20211021202727/https://www.cs.cornell.edu/courses/cs4120/2016sp/lectures/lec_heaps/|access-date=21 October 2021}}
</ref>
* If it is an ascending order priority queue, removal of an element with the lowest priority is done through leftward traversal of the BST.
* If it is a descending order priority queue, removal of an element with the highest priority is done through rightward traversal of the BST.

==See also==
{{Div col}}
* [[Search tree]]
* [[Join-based tree algorithms]]
* [[Optimal binary search tree]]
* [[Geometry of binary search trees]]
* [[Ternary search tree]]
{{colend}}

==References==
{{Reflist}}

==Further reading==
* {{DADS|Binary Search Tree|binarySearchTree}}
* {{cite book|last1=Cormen|first1=Thomas H. |author-link1=Thomas H. Cormen|last2=Leiserson|first2=Charles E. |author-link2=Charles E. Leiserson|last3=Rivest|first3=Ronald L. |author-link3=Ronald L. Rivest|author-link4=Clifford Stein|first4=Clifford |last4=Stein|url=https://mitpress.mit.edu/books/introduction-algorithms-second-edition|title=Introduction to Algorithms|edition=2nd|year=2001|publisher=[[MIT Press]]|isbn=0-262-03293-7|pages=253–272, 356–363|chapter=12: Binary search trees, 15.5: Optimal binary search trees}}
* {{cite web|url=http://nova.umuc.edu/~jarc/idsv/lesson1.html|title=Binary Tree Traversals|last=Jarc|first=Duane J.|date=3 December 2005|work=Interactive Data Structure Visualizations|publisher=[[University of Maryland]]|access-date=30 April 2006|archive-date=27 February 2014|archive-url=https://web.archive.org/web/20140227082917/http://nova.umuc.edu/~jarc/idsv/lesson1.html|url-status=dead}}
* {{cite book|last=Knuth|first=Donald|author-link=Donald Knuth|title=[[The Art of Computer Programming]]|edition=3rd|volume=3: "Sorting and Searching"|year=1997|publisher=Addison-Wesley|isbn=0-201-89685-0|pages=426–458|chapter=6.2.2: Binary Tree Searching}}
* {{cite web|url=http://employees.oneonta.edu/zhangs/PowerPointPlatform/resources/samples/binarysearchtree.ppt|title=Binary Search Tree|last=Long|first=Sean|work=Data Structures and Algorithms Visualization-A PowerPoint Slides Based Approach|publisher=[[SUNY Oneonta]]|format=[[Microsoft PowerPoint|PPT]]}}
* {{cite web|url=http://cslibrary.stanford.edu/110/BinaryTrees.html |archive-url=https://ghostarchive.org/archive/20220130/http://cslibrary.stanford.edu/110/BinaryTrees.html |archive-date=2022-01-30 |url-status=live|title=Binary Trees|last=Parlante|first=Nick|year=2001|work=CS Education Library|publisher=[[Stanford University]]}}{{cbignore}}

==External links==
{{Commons category|Binary search trees}}
* {{anchor|Ben Pfaff Introduction}} Ben Pfaff: [http://ftp.gnu.org/gnu/avl/avl-2.0.3.pdf.gz ''An Introduction to Binary Search Trees and Balanced Trees''.] (PDF; 1675&nbsp;kB) 2004.
* [http://btv.melezinek.cz Binary Tree Visualizer] (JavaScript animation of various BT-based data structures)

{{CS-Trees}}
{{Data structures}}

{{DEFAULTSORT:Binary search tree}}
[[Category:Articles with example C++ code]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Binary trees]]
[[Category:Search trees]]