D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

CHAPTER 2. LINKED LISTS
18
list.

---

Chapter 3
Binary Search Tree
Binary search trees (BSTs) are very simple to understand. We start with a root
node with value x, where the left subtree of x contains nodes with values < x
and the right subtree contains nodes whose values are ≥ x. Each node follows
the same rules with respect to nodes in their left and right subtrees.
BSTs are of interest because they have operations which are favourably fast:
insertion, look up, and deletion can all be done in O(log n) time. It is important
to note that the O(log n) times for these operations can only be attained if
the BST is reasonably balanced; for a tree data structure with self balancing
properties see AVL tree defined in §7).
In the following examples you can assume, unless used as a parameter alias
that root is a reference to the root node of the tree.
23
14
31
7
17
9
Figure 3.1: Simple unbalanced binary search tree
19

---

CHAPTER 3. BINARY SEARCH TREE
20
3.1
Insertion
As mentioned previously insertion is an O(log n) operation provided that the
tree is moderately balanced.
1) algorithm Insert(value)
2)
Pre: value has passed custom type checks for type T
3)
Post: value has been placed in the correct location in the tree
4)
if root = ∅
5)
root ← node(value)
6)
else
7)
InsertNode(root, value)
8)
end if
9) end Insert
1) algorithm InsertNode(current, value)
2)
Pre: current is the node to start from
3)
Post: value has been placed in the correct location in the tree
4)
if value < current.Value
5)
if current.Left = ∅
6)
current.Left ← node(value)
7)
else
8)
InsertNode(current.Left, value)
9)
end if
10)
else
11)
if current.Right = ∅
12)
current.Right ← node(value)
13)
else
14)
InsertNode(current.Right, value)
15)
end if
16)
end if
17) end InsertNode
The insertion algorithm is split for a good reason. The first algorithm (non-
recursive) checks a very core base case - whether or not the tree is empty. If
the tree is empty then we simply create our root node and finish. In all other
cases we invoke the recursive InsertN ode algorithm which simply guides us to
the first appropriate place in the tree to put value. Note that at each stage we
perform a binary chop: we either choose to recurse into the left subtree or the
right by comparing the new value with that of the current node. For any totally
ordered type, no value can simultaneously satisfy the conditions to place it in
both subtrees.

---

CHAPTER 3. BINARY SEARCH TREE
21
3.2
Searching
Searching a BST is even simpler than insertion. The pseudocode is self-explanatory
but we will look briefly at the premise of the algorithm nonetheless.
We have talked previously about insertion, we go either left or right with the
right subtree containing values that are ≥ x where x is the value of the node
we are inserting. When searching the rules are made a little more atomic and
at any one time we have four cases to consider:
1.
the root = ∅ in which case value is not in the BST; or
2.
root.Value = value in which case value is in the BST; or
3.
value < root.Value, we must inspect the left subtree of root for value; or
4.
value > root.Value, we must inspect the right subtree of root for value.
1) algorithm Contains(root, value)
2)
Pre: root is the root node of the tree, value is what we would like to locate
3)
Post: value is either located or not
4)
if root = ∅
5)
return false
6)
end if
7)
if root.Value = value
8)
return true
9)
else if value < root.Value
10)
return Contains(root.Left, value)
11)
else
12)
return Contains(root.Right, value)
13)
end if
14) end Contains

---

CHAPTER 3. BINARY SEARCH TREE
22
3.3
Deletion
Removing a node from a BST is fairly straightforward, with four cases to con-
sider:
1.
the value to remove is a leaf node; or
2.
the value to remove has a right subtree, but no left subtree; or
3.
the value to remove has a left subtree, but no right subtree; or
4.
the value to remove has both a left and right subtree in which case we
promote the largest value in the left subtree.
There is also an implicit fifth case whereby the node to be removed is the
only node in the tree. This case is already covered by the first, but should be
noted as a possibility nonetheless.
Of course in a BST a value may occur more than once. In such a case the
first occurrence of that value in the BST will be removed.
23
14
31
7
9
#1: Leaf Node
#2: Right subtree
no left subtree
#3: Left subtree
no right subtree
#4: Right subtree
and left subtree
Figure 3.2: binary search tree deletion cases
The Remove algorithm given below relies on two further helper algorithms
named F indP arent, and F indN ode which are described in