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. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.

Binary search trees allow binary search for fast lookup, addition, and removal of data items. 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 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 search time.

The complexity analysis of BST shows that, on average, the insert, delete and search takes ${\displaystyle O(\log n)}$ for ${\displaystyle n}$ nodes. In the worst case, they degrade to that of a singly linked list: ${\displaystyle O(n)}$. 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. AVL trees were the first self-balancing binary search trees, invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis.

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.

History

The binary search tree algorithm was discovered independently by several researchers, including P.F. Windley, Andrew Donald Booth, Andrew Colin, Thomas N. Hibbard.^[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.^[1]

The time complexities 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 trees were introduced to bound the height of the tree to ${\displaystyle O(\log n)}$.^[4] Various height-balanced binary search trees were introduced to confine the tree height, such as AVL trees, Treaps, and red–black trees.^[5]

The AVL tree was invented by Georgy Adelson-Velsky and Evgenii Landis in 1962 for the efficient organization of information.^[6][7] It was the first self-balancing binary search tree to be invented.^[8]

Overview

A binary search tree is a rooted binary tree in which nodes are arranged in strict total order in which the nodes with keys greater than any particular node A is stored on the right 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.^{[9]: 298 [10]: 287}

Binary search trees are also efficacious in sortings and search algorithms. 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.

Operations

Searching

Searching in a binary search tree for a specific key can be programmed recursively or iteratively.

Searching begins by examining the root node. If the tree is nil, the key being searched for does not exist in the tree. 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 ${\displaystyle {\text{nil}}}$. If the searched key is not found after a ${\displaystyle {\text{nil}}}$ subtree is reached, then the key is not present in the tree.^{[10]: 290–291}

Recursive search

The following pseudocode implements the BST search procedure through recursion.^[10]: 290

Recursive-Tree-Search(x, key)
    if x = NIL or key = x.key then
        return x
    if key < x.key then
        return Recursive-Tree-Search(x.left, key)
    else
        return Recursive-Tree-Search(x.right, key)
    end if

The recursive procedure continues until a ${\displaystyle {\text{nil}}}$ or the ${\displaystyle {\text{key}}}$ being searched for are encountered.

Iterative search

The recursive version of the search can be "unrolled" into a while loop. On most machines, the iterative version is found to be more efficient.^[10]: 291

Iterative-Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Since the search may proceed till some leaf node, the running time complexity of BST search is ${\displaystyle O(h)}$ where ${\displaystyle h}$ is the height of the tree. However, the worst case for BST search is ${\displaystyle O(n)}$ where ${\displaystyle n}$ is the total number of nodes in the BST, because an unbalanced BST may degenerate to a linked list. However, if the BST is height-balanced the height is ${\displaystyle O(\log n)}$.^[10]: 290

Successor and predecessor

For certain operations, given a node ${\displaystyle {\text{x}}}$, finding the successor or predecessor of ${\displaystyle {\text{x}}}$ is crucial. Assuming all the keys of a BST are distinct, the successor of a node ${\displaystyle {\text{x}}}$ in a BST is the node with the smallest key greater than ${\displaystyle {\text{x}}}$'s key. On the other hand, the predecessor of a node ${\displaystyle {\text{x}}}$ in a BST is the node with the largest key smaller than ${\displaystyle {\text{x}}}$'s key. The following pseudocode finds the successor and predecessor of a node ${\displaystyle {\text{x}}}$ in a BST.^{[12][13][10]: 292–293}

 BST-Successor(x)
     if x.right ≠ NIL then
         return BST-Minimum(x.right)
     end if
     y := x.parent
     while y ≠ NIL and x = y.right do
         x := y
         y := y.parent
     repeat
     return y

 BST-Predecessor(x)
     if x.left ≠ NIL then
         return BST-Maximum(x.left)
     end if
     y := x.parent
     while y ≠ NIL and x = y.left do
         x := y
         y := y.parent
     repeat
     return y

Operations such as finding a node in a BST whose key is the maximum or minimum are critical in certain operations, such as determining the successor and predecessor of nodes. Following is the pseudocode for the operations.^{[10]: 291–292}

 BST-Maximum(x)
     while x.right ≠ NIL do
         x := x.right
     repeat
     return x

 BST-Minimum(x)
     while x.left ≠ NIL do
         x := x.left
     repeat
     return x

Insertion

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. New nodes are inserted as leaf nodes in the BST.^{[10]: 294–295} Following is an iterative implementation of the insertion operation.^[10]: 294

1    BST-Insert(T, z)
2      y := NIL
3      x := T.root
4      while x ≠ NIL do
5        y := x
6        if z.key < x.key then
7          x := x.left
8        else
9          x := x.right
10       end if
11     repeat
12     z.parent := y
13     if y = NIL then
14       T.root := z
15     else if z.key < y.key then
16       y.left := z
17     else
18       y.right := z
19     end if

The procedure maintains a "trailing pointer" ${\displaystyle {\text{y}}}$ as a parent of ${\displaystyle {\text{x}}}$. After initialization on line 2, the while loop along lines 4-11 causes the pointers to be updated. If ${\displaystyle {\text{y}}}$ is ${\displaystyle {\text{nil}}}$, the BST is empty, thus ${\displaystyle {\text{z}}}$ is inserted as the root node of the binary search tree ${\displaystyle {\text{T}}}$, if it is not ${\displaystyle {\text{nil}}}$, insertion proceeds by comparing the keys to that of ${\displaystyle {\text{y}}}$ on the lines 15-19 and the node is inserted accordingly.^[10]: 295

Deletion

The deletion of a node, say ${\displaystyle {\text{Z}}}$, from the binary search tree ${\displaystyle {\text{BST}}}$ has three cases:^{[10]: 295-297}

1. If ${\displaystyle {\text{Z}}}$ is a leaf node, the parent node of ${\displaystyle {\text{Z}}}$ gets replaced by ${\displaystyle {\text{NIL}}}$ and consequently ${\displaystyle {\text{Z}}}$ is removed from the ${\displaystyle {\text{BST}}}$, as shown in (a).
2. If ${\displaystyle {\text{Z}}}$ has only one child, the child node of ${\displaystyle \text{Z}}$Zdroj:https://en.wikipedia.org?pojem=Binary_search_tree
   Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

   ---