Editing Binary search tree (section)

==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 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
}}</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>