Binary search tree: Difference between revisions

Revision as of 16:34, 23 March 2023

Revision as of 16:39, 23 March 2023

Line 39:

A binary search tree is a rooted binary tree in which the 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 is stored on the right [[Tree (data structure)#Terminology|sub-trees]] and the ones with equal to or less than are stored on the left sub-tree 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. (Thereby, the implemented order relation need not be strict and identifying so that duplicates may occur in the tree, i.&nbsp;e. more than one item with the same key.) 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}}</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.