Content deleted Content added
JimGrassroot (talk | contribs) |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
Line 29:
==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 complexity 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
Line 39:
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.
| |||