# Binary Search Trees

Search trees are data structures that support many dynamic set operations including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE. Thus, a search tree can be used both as a dictionary and a priority queue.
Binary search trees are search trees in which the keys are stored in such a way as to satisfy the binary search tree property (see Figure 1):
Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $\mathrm{key}\left[y\right]<\mathrm{key}\left[x\right]$. If $z$ is a node in the right subtree of $x$, then $\mathrm{key}\left[x\right]\le \mathrm{key}\left[z\right]$.
Figure 1: Binary Search Tree Property: $\mathrm{key}\left[y\right]<\mathrm{key}\left[x\right]\le \mathrm{key}\left[z\right]$

## 1  Traversing

There are three ways to traverse binary search trees:
1. Inorder tree walk - visit the left subtree, the root, and right subtree.
2. Preorder tree walk - visit the root, the left subtree and right subtree.
3. Postorder tree walk - visit the left subtree, the right subtree, and the root.
INORDER-TREE-WALK $\left(x\right)$
1    if  $x\ne \text{NIL}$
2          then  INORDER-TREE-WALK $\left(\mathrm{left}\left[x\right]\right)$
3                      print $\mathrm{key}\left[x\right]$  /* or some other operation on $x$ */
4                       INORDER-TREE-WALK $\left(\mathrm{right}\left[x\right]\right)$
PREORDER-TREE-WALK $\left(x\right)$
1    if  $x\ne \text{NIL}$
2          then print $\mathrm{key}\left[x\right]$
3                       PREORDER-TREE-WALK $\left(\mathrm{left}\left[x\right]\right)$
4                       PREORDER-TREE-WALK $\left(\mathrm{right}\left[x\right]\right)$
POSTORDER-TREE-WALK $\left(x\right)$
1    if  $x\ne \text{NIL}$
2          then  POSTORDER-TREE-WALK $\left(\mathrm{left}\left[x\right]\right)$
3                       POSTORDER-TREE-WALK $\left(\mathrm{right}\left[x\right]\right)$
4                      print $\mathrm{key}\left[x\right]$

## 2  Querying

### 2.1  Search

The TREE-SEARCH algorithm comes in two flavours: the recursive and the iterative approaches. In the recursive approach, we examine the input node $x$ and compare its $\mathrm{key}$ with the key we are looking for, $k$. If it matches, then we have found a node with the correct key; and can therefore return $x$. Otherwise, depending on the value of $k$ and $\mathrm{key}\left[x\right]$, the node we are after is either in the left subtree or right subtree of node $x$.
TREE-SEARCH $\left(x,k\right)$
1    if  $x=\text{NIL}$ or $k=\mathrm{key}\left[x\right]$
2          then return  $x$
3    if  $k<\mathrm{key}\left[x\right]$
4          then return  TREE-SEACH $\left(\mathrm{left}\left[x\right],k\right)$
5          else  return  TREE-SEACH $\left(\mathrm{right}\left[x\right],k\right)$
ITERATIVE-TREE-SEARCH $\left(x,k\right)$
1    while  $x\ne \text{NIL}$ and $k\ne \mathrm{key}\left[x\right]$
2                  do if  $k<\mathrm{key}\left[x\right]$
3                              then  $x$ $←$  $\mathrm{left}\left[x\right]$
4                              else   $x$ $←$  $\mathrm{right}\left[x\right]$
5    return  $x$

### 2.2  Minimum and Maximum

The propertities of the binary search tree makes the implementation of TREE-MINIMUM and TREE-MAXIMUM very simple. For minimum, simply start at the root and ask "is there a left child". If so, visit it and repeat the question. The final left most node is the tree-minimum. Conversely, the right most node is the tree-maximum.
TREE-MINIMUM $\left(x\right)$
1    while  $\mathrm{left}\left[x\right]\ne \text{NIL}$
2                  do  $x$ $←$  $\mathrm{left}\left[x\right]$
3    return  $x$
TREE-MAXIMUM $\left(x\right)$
1    while  $\mathrm{right}\left[x\right]\ne \text{NIL}$
2                  do  $x$ $←$  $\mathrm{right}\left[x\right]$
3    return  $x$

### 2.3  Successor

The successor of a node $x$ is the node with the next biggest key. Essentially, this is the minimum of all the nodes with equal or greater keys. If node $x$ has a right sub-tree $R$, then its successor is the minimum of $R$. Otherwise, its successor must be the lowest ancestor of $x$ whose left child is either an ancestor of $x$ or $x$ itself.
TREE-SUCCESSOR $\left(x\right)$
1    if  $\mathrm{right}\left[x\right]\ne \text{NIL}$
2          then return  TREE-MINIMUM $\left(\mathrm{right}\left[x\right]\right)$
3     $y$ $←$  $p\left[x\right]$
4    while  $y\ne \text{NIL}$ and $x=\mathrm{right}\left[y\right]$
5                  do  $x$ $←$  $y$
6                         $y$ $←$  $p\left[y\right]$
7    return  $y$

## 3  Data Manipulation

### 3.1  Insert

TREE-INSERT inserts a node $z$ into tree $T$. The algorithm starts at the root of the tree and traverses down the tree following the rules of binary search trees. If the node to be inserted is smaller, then it has to be inserted into the left subtree, else it should be inserted in the right subtree. The process continues until the appropriate subtree does not exist. That is to say, the left/right child of the current node is $\text{NIL}$. Node $z$ is then inserted into the tree as the appropriate child of the current node.
TREE-INSERT $\left(T,z\right)$
1     $y$ $←$  $\text{NIL}$
2     $x$ $←$  $\mathrm{root}\left[T\right]$
3    while  $x\ne \text{NIL}$
4                  do  $y$ $←$  $x$
5                        if  $\mathrm{key}\left[z\right]<\mathrm{key}\left[x\right]$
6                              then  $x$ $←$  $\mathrm{left}\left[x\right]$
7                              else   $x$ $←$  $\mathrm{right}\left[x\right]$
8     $p\left[z\right]$ $←$  $y$
9    if  $y=\text{NIL}$
10          then  $\mathrm{root}\left[T\right]$ $←$  $z$  /* The tree was empty. */
11          else  if  $\mathrm{key}\left[z\right]<\mathrm{key}\left[y\right]$
12                            then  $\mathrm{left}\left[y\right]$ $←$  $z$
13                            else   $\mathrm{right}\left[y\right]$ $←$  $z$

### 3.2  Delete

TREE-DELETE deletes a node $z$ from tree $T$. There are three possible states for node $z$ prior to deletion. It may have no children, one child, or two children. The TREE-DELETE algorithm works by considering each of these possibilities and behaving accordingly. If $z$ has no children, then it is simply removed from the tree. For the case where $z$ has one child, $p\left[z\right]$'s left/right child pointer that is currently directed at $z$ is redirected to $z$'s child (see Figure 2). Lastly, if $z$ has two children, it's successor is removed from the tree and is used to replace $z$. The algorithm follows:
TREE-DELETE $\left(T,z\right)$
1    if  $\mathrm{left}\left[z\right]=\text{NIL}$ or $\mathrm{right}\left[z\right]=\text{NIL}$
2          then  $y$ $←$  $z$
3          else   $y$ $←$  TREE-SUCCESSOR $\left(z\right)$
4    if  $\mathrm{left}\left[y\right]\ne \text{NIL}$
5          then  $x$ $←$  $\mathrm{left}\left[y\right]$
6          else   $x$ $←$  $\mathrm{right}\left[y\right]$
7    if  $x\ne \text{NIL}$
8          then  $p\left[x\right]$ $←$  $p\left[y\right]$
9    if  $p\left[y\right]=\text{NIL}$
10          then  $\mathrm{root}\left[T\right]$ $←$  $x$
11          else  if  $y=\mathrm{left}\left[p\left[y\right]\right]$
12                            then  $\mathrm{left}\left[p\left[y\right]\right]$ $←$  $x$
13                            else   $\mathrm{right}\left[p\left[y\right]\right]$ $←$  $x$
14    if  $y\ne z$
15          then  $\mathrm{key}\left[z\right]$ $←$  $\mathrm{key}\left[y\right]$
16                      copy $y$'s satellite data into $z$
17    return  $y$
Figure 2: TREE-DELETE. If $z$ has one child, it is simply spliced out of the tree. Since $z$ can be the left or right child of its parent $p$, and it may have a left or right child $c$ itself, there are four possibilities (a), (b), (c), and (d).
Figure 3: TREE-DELETE. If $z$ has two children, we remove its successor $s$. Node $s$ is guaranteed to have at most one child because it is the minimum of sub-tree $R$. It's removal is thus either of the other two TREE-DELETE cases. When this is done, $s$ is used to replace $z$.

File translated from TEX by TTM, version 3.67.
On 31 Mar 2006, 18:12.