Content deleted Content added
Editing caption of Fig 1, which previously said "The leaves are not drawn", when they are in fact displayed (i.e. the nodes with values 1, 4, 7 and 13 are all leaves). |
m Removed recurrent information; fixed citations. |
||
| (9 intermediate revisions by 7 users not shown) | |||
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 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|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 154 ⟶ 151:
===Deletion===
[[File:BST node deletion.png|thumb|400px|right|
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,
# 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 [[Tree_traversal#In-order,_LNR|in-order]] 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.
# 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}}
Line 166 ⟶ 164:
|- 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'''
|-
| |||