Binary search tree

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 ${\displaystyle {\text{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}

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.

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 then
     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

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 the BST are distinct, the successor of a node ${\displaystyle {\text{x}}}$ in 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 BST is the node with the largest key smaller than ${\displaystyle {\text{x}}}$'s key. Following is pseudocode for finding the successor and predecessor of a node ${\displaystyle {\text{x}}}$ in 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 then
     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 then
     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 then
     x := x.right
   repeat
   return x

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

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

Fig. 2: Binary search tree special cases deletion illustration.

Deletion of a node, say ${\displaystyle {\text{z}}}$, from a binary search tree ${\displaystyle {\text{T}}}$ should abide three cases:[10]^: 295

1. If ${\displaystyle {\text{z}}}$ is a leaf node, the parent node's pointer to ${\displaystyle {\text{z}}}$ gets replaced with ${\displaystyle {\text{nil}}}$ and consequently ${\displaystyle {\text{z}}}$ gets removed from the tree.
2. If ${\displaystyle {\text{z}}}$ has a single child node, the child gets elevated as either left or right child of ${\displaystyle {\text{z}}}$'s parent depending on the position of ${\displaystyle {\text{z}}}$ within the BST, as shown in fig. 2 part (a) and part (b), and as a result, ${\displaystyle {\text{z}}}$ gets removed from the tree.
3. If ${\displaystyle {\text{z}}}$ has both a left and right child, the successor of ${\displaystyle {\text{z}}}$ (let it be ${\displaystyle {\text{y}}}$) takes the position of ${\displaystyle {\text{z}}}$ in the tree. This depends on the position of ${\displaystyle {\text{y}}}$ within the BST:[10]^: 296
   1. If ${\displaystyle {\text{y}}}$ is ${\displaystyle {\text{z}}}$'s immediate right child, ${\displaystyle {\text{y}}}$ gets elevated and ${\displaystyle {\text{y}}}$'s left child made point to ${\displaystyle {\text{z}}}$'s initial left sub-tree, as shown in fig. 2 part (c).
   2. If ${\displaystyle {\text{y}}}$ is not the immediate right child of ${\displaystyle {\text{z}}}$, deletion proceeds by replacing the position of ${\displaystyle {\text{y}}}$ by its right child, and ${\displaystyle {\text{y}}}$ takes the position of ${\displaystyle {\text{z}}}$ in the BST, as shown in fig. 2 part (d).

The following pseudocode implements the deletion operation in a binary search tree.[10]^: 296-298

1    BST-Delete(T, z)
2      if z.left = NIL then
3        Shift-Nodes(T, z, z.right)
4      else if z.right = NIL then
5        Shift-Nodes(T, z, z.left)
6      else
7        y := Tree-Successor(z)
8        if y.parent ≠ z then
9          Shift-Nodes(T, y, y.right)
10         y.right := z.right
11         y.right.parent := y
12       end if
13       Shift-Nodes(T, z, y)
14       y.left := z.left
15       y.left.parent := y
16     end if

1    Shift-Nodes(T, u, v)
2      if u.parent = NIL then
3        T.root := v
4      else if u = u.parent.left then
5        u.parent.left := v
5      else
6        u.parent.right := v
7      end if
8      if v ≠ NIL then
9        v.parent := u.parent
10     end if

The ${\displaystyle {\text{Tree-Delete}}}$ procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. The helper function ${\displaystyle {\text{Shift-Nodes}}}$ is used within the deletion algorithm for the purpose of replacing the node ${\displaystyle {\text{u}}}$ with ${\displaystyle {\text{v}}}$ in the binary search tree ${\displaystyle {\text{T}}}$.[10]^: 298 This procedure handles the deletion (and substitution) of ${\displaystyle {\text{u}}}$ from the BST.

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.[15]^: 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.[15]^: 52

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 ${\displaystyle 1}$.[16][15]^: 61 However, the difference is bound by a ratio ${\displaystyle \alpha }$ of the weights, since a strong balance condition of ${\displaystyle 1}$ cannot be maintained with ${\displaystyle O(\log n)}$ rebalancing work during insert and delete operations. The ${\displaystyle \alpha }$-weight-balanced trees gives an entire family of balance conditions, where each left and right subtrees have each at least a fraction of ${\displaystyle \alpha }$ of the total weight of the subtree.[15]^: 62

There are several self-balanced binary search trees, including T-tree,[17] treap,[18] red-black tree,[19] B-tree,[20] 2–3 tree,[21] and Splay tree.[22]

Binary search trees are used in sorting algorithms such as tree sort, where all the elements are inserted at once and the tree is traversed at an in-order fashion.[23] BSTs are also used in quicksort.[24]

Binary search trees are used in implementing priority queues, using the node's key as priorities. Adding new elements to the queue follows the regular BST insertion operation but the removal operation depends on the type of priority queue:[25]

• If it is an ascending order priority queue, removal of an element with the lowest priority is done through leftward traversal of the BST.
• If it is a descending order priority queue, removal of an element with the highest priority is done through rightward traversal of the BST.