Binary search tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.
BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to Conway Berners-Lee and David Wheeler.
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 search time.
The complexity analysis of BST shows that, on average, the insert, delete and search takes
In the worst case, they degrade to that of a singly linked list:
To address the boundless increase of the tree height with arbitrary insertions and deletions, self-balancing variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm.
Binary search trees can be used to implement abstract data types such as dynamic sets, lookup tables and priority queues, and used in sorting algorithms such as tree sort.
The binary search tree algorithm was discovered independently by several researchers, including P.F.
[1][2] The algorithm is attributed to Conway Berners-Lee and David Wheeler, who used it for storing labeled data in magnetic tapes in 1960.
[3] One of the earliest and popular binary search tree algorithm is that of Hibbard.
[5] The AVL tree was invented by Georgy Adelson-Velsky and Evgenii Landis in 1962 for the efficient organization of information.
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.
[11][9]: 299-302 Binary search trees are also a fundamental data structure used in construction of abstract data structures such as sets, multisets, and associative arrays.
Otherwise, if the key equals that of the root, the search is successful and the node is returned.
If the key is less than that of the root, the search proceeds by examining the left subtree.
Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree.
This process is repeated until the key is found or the remaining subtree is
[10]: 290–291 The following pseudocode implements the BST search procedure through recursion.
[10]: 291–292 Operations such as insertion and deletion cause the BST representation to change dynamically.
The data structure must be modified in such a way that the properties of BST continue to hold.
is inserted as the root node of the binary search tree
has three cases:[10]: 295-297 The following pseudocode implements the deletion operation in a binary search tree.
is used within the deletion algorithm for the purpose of replacing the node
A BST can be traversed through three basic algorithms: inorder, preorder, and postorder tree walks.
[10]: 287–289 Without rebalancing, insertions or deletions in a binary search tree may lead to degeneration, resulting in a height
is number of items in a tree), so that the lookup performance is deteriorated to that of a linear search.
[14] Keeping the search tree balanced and height bounded by
-weight-balanced trees gives an entire family of balance conditions, where each left and right subtrees have each at least a fraction of
