Content deleted Content added
→Deletion: align img |
m Removed recurrent information; fixed citations. |
||
| (45 intermediate revisions by 24 users not shown) | |||
Line 6:
|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=
|space_worst=
|search_avg=
|search_worst=
|insert_avg=
|insert_worst=
|delete_avg=
|delete_worst=
}}
[[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 [[
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]].
Line 24:
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]].<ref>{{cite web |last=Pitassi |first=Toniann |year=2015 |title=CSC263: Balanced BSTs, AVL tree |url=http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf |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 |archive-date=14 February 2019 |access-date=19 May 2022 |publisher=[[University of Toronto]], Department of Computer Science |page=6}}</ref><ref>{{cite web |last=Myers |first=Andrew |title=CS 312 Lecture: AVL Trees |url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html |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 |access-date=19 May 2022 |publisher=[[Cornell University]], Department of Computer Science}}</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]] |language=ru |volume=146 |pages=263–266}} [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>
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 |url-access=subscription}}</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|url-access=subscription}}</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 time
▲}}</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>
==Overview==
A binary search tree is a rooted binary tree in which
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|url-access=subscription}}</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.
Line 47 ⟶ 44:
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 [[
====Recursive search====
Line 71 ⟶ 68:
|
Iterative-Tree-Search(x, key)
'''while''' x ≠ NIL '''and''' key ≠ x.key '''
'''if''' key < x.key '''then'''
x := x.left
Line 83 ⟶ 80:
====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
{|
|- style="vertical-align:top"
|
BST-Successor(x)
'''if''' x.right ≠ NIL '''then'''
'''return''' BST-Minimum(x.right)
'''end if'''
y := x.parent
'''while''' y ≠ NIL '''and''' x = y.right '''
x := y
y := y.parent
'''repeat'''
'''return''' y
|
BST-Predecessor(x)
'''if''' x.left ≠ NIL '''then'''
'''return''' BST-Maximum(x.left)
'''end if'''
y := x.parent
'''while''' y ≠ NIL '''and''' x = y.left '''
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}}
Line 114 ⟶ 111:
|
BST-Maximum(x)
'''while''' x.right ≠ NIL '''
x := x.right
'''repeat'''
'''return''' x
|
BST-Minimum(x)
'''while''' x.left ≠ NIL '''
x := x.left
'''repeat'''
'''return''' x
|}
Line 154 ⟶ 151:
===Deletion===
[[File:BST node deletion.png|thumb|400px|right|Binary search tree node deletion process.]]
# If <math>\text{
# If <math>\text{
#
## If <math>\text{
## 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.
# Alternatively, the in-order predecessor can also be used.
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,
2 '''if'''
3 Shift-Nodes(BST,
4 '''else if'''
5 Shift-Nodes(BST,
6 '''else'''
7
8 '''if'''
9 Shift-Nodes(BST,
10
11
12 '''end if'''
13 Shift-Nodes(BST,
14
15
16 '''end if'''
|-
|
1 Shift-Nodes(BST, u, v)
Line 195 ⟶ 194:
10 '''end if'''
|}
The <math>\text{
==Traversal==
Line 201 ⟶ 200:
{{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''':
*'''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}}
Line 236 ⟶ 235:
=== 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 [[
=== Weight-balanced trees ===
Line 243 ⟶ 242:
=== 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
==Examples of applications==
| |||