Binary search tree: Difference between revisions

Revision as of 07:54, 12 February 2025

Revision as of 18:47, 6 March 2025

Line 31:

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 complexitiescomplexity 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>