Editing Binary search tree (section)

==Balanced binary search trees==
{{Main|Self-balancing binary search tree}}
Without rebalancing, insertions or deletions in a binary search tree may lead to degeneration, resulting in a height <math>n</math> of the tree (where <math>n</math> is number of items in a tree), so that the lookup performance is deteriorated to that of a linear search.<ref>{{cite web|url=https://www.ics.uci.edu/~thornton/ics46/Notes/BinarySearchTrees/|publisher=[[University of California, Irvine]]|year=2021|first=Alex|last=Thornton|title= ICS 46: Binary Search Trees|archive-url=https://web.archive.org/web/20210704141729/https://www.ics.uci.edu/~thornton/ics46/Notes/BinarySearchTrees/|archive-date=4 July 2021|url-status=live|access-date=21 October 2021}}</ref> Keeping the search tree balanced and height bounded by <math>O(\log n)</math> is a key to the usefulness of the binary search tree. This can be achieved by "self-balancing" mechanisms during the updation operations to the tree designed to maintain the tree height to the binary logarithmic complexity.<ref name="Knuth98" /><ref name="peter11">{{cite book|publisher=[[Cambridge University Press]]|url=https://www.cambridge.org/core/books/advanced-data-structures/D56E2269D7CEE969A3B8105AD5B9254C|title=Advanced Data Structure|date=January 2011|isbn=9780511800191|doi=10.1017/CBO9780511800191|first=Peter|last=Brass}}</ref>{{rp|p=50}}

=== 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 [[red–black tree]].{{r|peter11|pp=50-51}} The heights of all the nodes on the path from the root to the modified leaf node have to be observed and possibly corrected on every insert and delete operation to the tree.{{r|peter11|pp=52}}

=== Weight-balanced trees ===
{{main|Weight-balanced tree}}
In a weight-balanced tree, the criterion of a balanced tree is the number of leaves of the subtrees. The weights of the left and right subtrees differ at most by <math>1</math>.<ref>{{Cite journal|doi=10.1016/0304-3975(80)90018-3|title=On the Average Number of Rebalancing Operations in Weight-Balanced Trees|journal=Theoretical Computer Science|volume=11|issue=3|pages=303–320|year=1978|last1=Blum|first1=Norbert|last2=Mehlhorn|first2=Kurt|url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-date=2022-10-09 |url-status=live}}</ref>{{r|peter11|pp=61}} However, the difference is bound by a ratio <math>\alpha</math> of the weights, since a strong balance condition of <math>1</math> cannot be maintained with <math>O(\log n)</math> rebalancing work during insert and delete operations. The <math>\alpha</math>-weight-balanced trees gives an entire family of balance conditions, where each left and right subtrees have each at least a fraction of <math>\alpha</math> of the total weight of the subtree.{{r|peter11|pp=62}}

=== 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 | pages=540–545 | year=1989 | doi=10.1109/SFCS.1989.63531 | isbn=0-8186-1982-1 | publisher=IEEE Computer Society Press | location=Washington, D.C.| title-link=Symposium on Foundations of Computer Science }}</ref> [[red-black tree]],<ref name="Cormen2001">{{Anchor|Cormen}}{{Cite book |title=Introduction to Algorithms |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |edition=second |publisher=MIT Press |year=2001 |isbn=978-0-262-03293-3 |chapter=Red&ndash;Black Trees |pages=[https://archive.org/details/introductiontoal00corm_691/page/n735 273]–301 |title-link=Introduction to Algorithms }}</ref> [[B-tree]],<ref>{{Citation | last = Comer | first = Douglas | author-link = Douglas Comer | title = The Ubiquitous B-Tree | journal = Computing Surveys | volume = 11 | issue = 2 | pages = 123–137 | date = June 1979 | issn = 0360-0300 | doi = 10.1145/356770.356776 | s2cid = 101673 | doi-access = free }}</ref> [[2–3 tree]],<ref>{{cite book| title=The Art of Computer Programming |volume=3| chapter=6.2.4 |quote=The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. |first1=Donald M |last1=Knuth |edition=2 |isbn=9780201896855 |publisher=Addison Wesley|year=1998}}</ref> and [[Splay tree]].<ref>{{cite journal | first1 = Daniel D. | last1 = Sleator | author1-link = Daniel Sleator | first2 = Robert E. | last2 = Tarjan | author2-link = Robert Tarjan | title = Self-Adjusting Binary Search Trees | journal = [[Journal of the ACM]] | volume = 32 | issue = 3 | pages = 652–686 | year = 1985 | url = https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf | doi = 10.1145/3828.3835 | s2cid = 1165848 }}</ref>