Module 4

Binary Search Trees

A binary search tree has a better performance than any of the data structures stu died so far
when the operations we wish to perform are insertion, deletion, and search ing. In fact, with a
binary search tree we can perform these operations by both key value (for example, delete the
element with key x) and by rank (for example, delete the fifth smallest element).

Definition: A binary search tree is a binary tree. It may be empty. If it is not empty, it satisfies
the following properties:

(1) Every element has a key, and no two elements have the same key, that is, the keys are
unique.
(2) The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.
(3) The keys in a nonempty right subtree must be larger than the key in the root of the subtree.
(4) The left and right subtrees are also binary search trees.
Some sample binary trees are shown in Figure 5.30. The tree of Figure 5.30(a) is not a binary
search tree since the right subtree fails to satisfy property (4). This subtree has a root with a
key value of 25 and a right child with a smaller key value (22). Figure 5.30(b) and Figure
5.30(c) are binary search trees.

Since a binary search tree is a specialized form of a binary tree, the C declarations for a binary
search tree do not differ from the declarations that we previously used to create a binary tree.
Similarly, all the binary tree operations discussed in Sections 5.3 and 5.4 apply directly to
binary search trees. Thus, for example, we may use the inorder, preorder, and postorder
traversals without modification. To these operations, we add those of insertion, deletion, and
search
Searching a Binary Search Tree

Since the definition of a binary search tree is recursive, it is easiest to describe a recur sive
search method. Suppose we wish to search for an element with a key. We begin at the root. If
the root is NULL, the search tree contains no elements and the search is unsuccessful.
Otherwise, we compare key with the key value in root. If key equals root's key value, then the
search terminates successfully. If key is less than roof s key value, then no element in the right
subtree can have a key value equal to key. Therefore, we search the left subtree of root. If key
is larger than roofs key value, we search the right subtree of root. The function search (Program
5.15) recursively searches the sub trees

We can easily replace the recursive search function with a comparable iterative one. The
function search! (Program 5.16) accomplishes this by replacing the recursion with a while loop.

Inserting into a Binary Search Tree

To insert a new element, key, we must first verify that the key is different from those of existing
elements. To do this we search the tree. If the search is unsuccessful, then we insert the element
at the point the search terminated. For instance, to insert an element with key 80 into the tree
of Figure 5.30(b), we first search the tree for 80. This search terminates unsuccessfully, and the
last node examined has value 40. We insert the new element as the right child of this node. The
resulting search tree is shown in Figure 5.31(a). Figure 5.31(b) shows the result of inserting the
key 35 into the search tree of Figure 5.31(a). This strategy is implemented by insert-node
(Program 5.17). This uses the function modified - search which is a slightly modified version
of function search 2 (Program 5.16). This function searches the binary search tree *node for
the key num. If the tree is empty or if num is present, it returns NULL. Otherwise, it returns a
pointer to the last node of the tree that was encountered during the search. The new element is
to be inserted as a child of this node
Deleting From a Binary Search Tree

Deletion of a leaf node is easy. For example, to delete 35 from the tree of Figure 5.31(b), we
set the left child field of its parent to NULL and free the node. This gives us the tree of Figure
5.31(a). The deletion of a nonleaf node that has only a single child is also easy. We erase the
node and then place the single child in the place of the erased node. For example, if we delete
40 from the tree of Figure 5.31(a) we obtain the tree in Figure 5.32

When we delete a nonleaf node with two children, we replace the node with either the largest
element in its left subtree or the smallest element in its right subtree. Then we proceed by
deleting this replacing element from the subtree from which it was taken. For instance, suppose
that we wish to delete 60 from the tree of Figure 5.33(a). We may replace 60 with either the
largest element (55) in its left subtree or the smallest element (70) in its right subtree. Suppose
we opt to replace it with the largest element in the left subtree. We move the 55 into the root of
the subtree. We then make the left child of the node that previously contained the 55 the right
child of the node containing 50, and we free the old node containing 55. Figure 5.33(b) shows
the final result. One may verify that the largest and smallest elements in a subtree are always
in a node of degree zero or one. This observation simplifies the code for the deletion function.
We leave the formal writing of this function as an exercise. From the examples considered, you
should be able to see that a deletion can be performed in O(/i) time where h is the height of the
tree
Height of a Binary Search Tree

Unless care is taken, the height of a binary search tree with n elements can become as large as
n. This is the case, for instance, when we use insert-node to insert the keys 1, 2, 3, • • •, n, in
that order, into an initially empty binary search tree. However, when inser tion and deletions
are made at random using the above functions, the height of the binary search tree is O(log2n),
on the average.

Selection Trees

Suppose we have k ordered sequences called runs, that are to be merged into a single ordered
sequence. Each sequence consists of some number of records and is in nondecreasing order of
a designated field called the key. An ordered sequence is called a run. Let n be the number of
records in the k runs together. The merging task can be accomplished by repeatedly outputting
the record with the smallest key. The smallest has to be found from k possibilities and it could
be the leading record in any of the k-runs. The most direct way to merge k-runs would be to
make k - 1 comparisons to determine the next record to output. For k > 2, we can achieve a
reduction in the number of comparisons needed to find the next smallest element by using the
idea of a selection tree data structure. There are two kinds of selection trees: winner trees and
loser trees.

A winner tree is a complete binary tree in which each node represents the smaller of its two
children. Thus, the root node represents the smallest node in the tree. Figure 5.32 illustrates a
winner tree for the case k = 8.
 Figure 5.32 Winner tree for k=8, showing the first three keys in each of the eight runs

The construction of this winner tree may be compared to the playing of a tournament in which
the winner is the record with the smaller key. Then, each nonleaf node in the tree represents the
winner of a tournament, and the root node represents the overall winner, or the smallest key.
Each leaf node represents the first record in the corresponding run. Since the records being
merged are generally large, each node will contain only a pointer to the record it represents.
Thus, the root node contains a pointer to the first record in run 4.

A winner tree may be represented using the sequential allocation scheme for binary trees that
results from Lemma 5.4. The number above each node in Figure 5.32 is the address of the node
in this sequential representation. The record pointed to by the root has the smallest key and so
may be output. Now, the next record from run 4 enters the winner tree. It has a key value of 15.
To restructure the tree, the tournament has to be replayed only along the path from node 11 to
the root. Thus, the winner from nodes 10 and 11 is again node 11 (15 < 20). The winner from
nodes 4 and 5 is node 4 (9 < 15).

The winner from 2 and 3 is node 3 (8 < 9). The new tree is shown in Figure 5.33. The
tournament is played between sibling nodes and the result put in the parent node.

Lemma 5.4 may be used to compute the address of sibling and parent nodes efficiently.
Each new comparison takes place at the next higher level in the tree.

Figure 5.33: Winner tree of Figure 5.32 after one record has been output at restructured (nodes that were
changed are shaded)

Loser Trees

After the record with the smallest key value is output, the winner tree of Figure 5.32 is to be
restructured. Since the record with the smallest key value is in run 4, this restructuring involves
inserting the next record from this run into the tree. The next record has key value 15.
Tournaments are played between sibling nodes along the path from node 11 to the root. Since
these sibling nodes represent the losers of tournaments played earlier, we can simplify the
restructuring process by placing in each nonleaf node a pointer to the record that loses the
tournament rather than to the winner of the tourna-ment. A selection tree in which each nonleaf
node retains a pointer to the loser is called a loser tree. Figure 5.34 shows the loser tree that
corresponds to the winner tree of Figure 5.32. For convenience, each node contains the key
value of a record rather than a pointer to the record represented. The leaf nodes represent the
first record in each run.

An additional node, node 0, has been added to represent the overall winner of the tourna-ment.
Following the output of the overall winner, the tree is restructured by playing tournaments
along the path from node 11 to node 1. The records with which these tournaments are to be
played are readily available from the parent nodes. As a result, sibling nodes along the path
from 11 to 1 are not accessed.

FORESTS

Definition: A forest is a set of n ≥ 0 disjoint trees. •

A three-tree forest is shown in Figure 5.35. The concept of a forest is very close to that of a tree
because if we remove the root of a tree, we obtain a forest. For example, removing the root of
any binary tree produces a forest of two trees. In this section, we briefly consider several forest
operations, including transforming a forest into a binary tree and forest traversals. In the next
section, we use forests to represent disjoint sets.

5,9.1 Transforming a Forest into a Binary Tree

To transform a forest into a single binary tree, we first obtain the binary tree representation of
each of the trees in the forest and then link these binary trees together through the rightChild
field of the root nodes. Using this transformation, the forest of Figure 5.35 becomes the binary
tree of Figure 5.36.

Figure 5.36: Binary tree representation of forest of Figure 5.35

We can define this transformation in a formal way as follows:

Definition: If T1, •, In is a forest of trees, then the binary tree corresponding to this forest,
denoted by B (Ti, *, In),

(1) is empty if n = 0

(2) has root equal to root (T1); has left subtree equal to B (T11,T12,….., T1m), where T11, …..
T1m are the subtrees of root(T1); and has right subtree B(T2,……, Tn).

Forest Traversals

Preorder and inorder traversals of the corresponding binary tree T of forest F have a natural
correspondence to traversals on F. Preorder traversal of T is equivalent to visit. ing the nodes
of F in forest preorder, which is defined as follows:

(1) If F is empty then return.

(2) Visit the root of the first tree of F.

(3) Traverse the subtrees of the first tree in forest preorder.

(4) Traverse the remaining trees of F in forest preorder.

Inorder traversal of T is equivalent to visiting the nodes of F in forest inorder, which is defined
as follows:

(1) If F is empty then return.

(2) Traverse the subtrees of the first tree in forest inorder.

(3) Visit the root of the first tree.

(4) Traverse the remaining trees in forest inorder.

The proofs that preorder and inorder traversals on the corresponding binary tree are the same
as preorder and inorder traversals on the forest are left as exercises. There is no natural analog
for postorder traversal of the corresponding binary tree of a forest.

Nevertheless, we can define the postorder traversal of a forest as follows:

(1) If F is empty then return.

(2) Traverse the subtrees of the first tree of F in forest postorder.

(3) Traverse the remaining trees of F in forest postorder.

(4) Visit the root of the first tree of F.

In a level-order traversal of a forest, nodes are visited by level, beginning with the roots of each
tree in the forest. Within each level, nodes are visited from left to right. One may verify that
the level-order traversal of a forest and that of its associated binary tree do not necessarily yield
the same result.