Content deleted Content added
m Open access bot: url-access=subscription updated in citation with #oabot. |
m Removed recurrent information; fixed citations. |
||
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]].
Line 32:
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>
==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}}
| |||