Binary Search Trees 327
(a) (b)
FIGURE 20.9: Examples of binary search trees.
(a) (b)
pre-order 8 4 1 7 11 9 8 4 1 7 5 11 9 10 12
in-order 1 4 7 8 9 11 1 4 5 7 8 9 10 11 12
post-order 1 7 4 9 11 8 1 5 7 4 10 9 12 11 8
Answering this question helps visualize the different traversal techniques. To write the
output of a pre-order traversal for (b), write the value of the root first:
8
It is followed by the outputs of the left subtree and then the right subtree.
8 pre-order of left subtree pre-order of right subtree
The pre-order traversal of the left subtree starts with 4. The pre-order traversal of 4’s
left subtree is 1 and the pre-order traversal of 4’s right subtree is 7 5.
The pre-order traversal of the right subtree starts with 11. The pre-order traversal of
11’s left subtree is 9 10 and the pre-order traversal of 11’s right subtree is 12.
Thus, the output is
8 4 1 7 5 11 9 10 12
20.5 Deleting from a Binary Search Tree
Deleting a node from a binary search tree is more complex than inserting because in-
sertion adds only leaf nodes. Deleting a non-leaf node must maintain the tree’s ordering
property. When deleting a node, there are three different scenarios, as shown in Fig. 20.10.
1. If the node has no children, then release the memory occupied by this node. The
pointer that originally points to this child is set to NULL. Fig. 20.10 (b) illustrates this
scenario.
2. If the node has only one child, then the node’s parent points to the node’s only child
and releases the memory occupied by the node. Fig. 20.10 (c) illustrates this scenario.
328 Intermediate C Programming
(a)
(b)
(c)
FIGURE 20.10: (a) The original binary search tree. (b) Deleting the node “5”. The node
is a leaf node (has no children). This is the first case. The left child of node “7” becomes
NULL. (c) Deleting the node “14”. This node has one child. This is the second case. The
parent of “14” points to the only child of “14”, i.e., “12”.
3. If the node has two children, then find this node’s immediate successor. The immediate
successor is the node that appears immediately after this node in an in-order traversal.
The successor must be on the right side of the node. Exchange the values of the
node with its immediate successor. Then delete the successor. Fig. 20.11 (a) and (b)
illustrates this scenario. Note that the successor cannot not have the left child. Why?
Below is a sample implementation of the delete function. Lines 39–43 finds tn’s imme-
diate successor. The immediate successor is at the right side of tn and hence su starts with
tn -> right. The immediate successor must also be the leftmost node on tn’s right side.
The immediate successor cannot have a left child. Otherwise it would not be the immediate
successor. Note that the immediate successor may have the right child. It is also possible to
use the immediate predecessor but this book uses the successor.
// treedelete.c
1
#include "tree.h"2
#include <stdlib.h>3
TreeNode * Tree_delete(TreeNode * tn, int val)4
Binary Search Trees 329
(a)
(b)
FIGURE 20.11: (a) The node “8” has two children. This is the third case. Exchange the
values of this node and its successor. The tree temporarily loses its ordering property. (b)
Deleting the node “8” restores the property of the binary search tree.
{
5
if (tn == NULL) { return NULL; }6
if (val < (tn -> value))7
{8
tn -> left = Tree_delete(tn -> left, val);9
return tn;10
}11
if (val > (tn -> value))12
{13
tn -> right = Tree_delete(tn -> right , val);14
return tn;15
}16
// v is the same as tn -> value17
if (((tn -> left) == NULL) && ((tn -> right) == NULL))18
{19
// tn has no child20
free (tn);21
return NULL;22
}23
if ((tn -> left) == NULL)24
{25
// tn -> right must not be NULL26
TreeNode * rc = tn -> right;27
free (tn);28
return rc;29
}30
if ((tn -> right) == NULL)31
{32
// tn -> left must not be NULL33
330 Intermediate C Programming
TreeNode * lc = tn -> left;
34
free (tn);35
return lc;36
}37
// tn have two children38
// find the immediate successor39
TreeNode * su = tn -> right; // su must not be NULL40
while ((su -> left) != NULL)41
{42
su = su -> left;43
}44
// su is tn’s immediate successor45
// swap their values46
tn -> value = su -> value;47
su -> value = val;48
// delete su49
tn -> right = Tree_delete(tn -> right , val);50
return tn;51
}52
After swapping the values, Fig. 20.11 (a) is temporarily not a binary search tree. This is
because the value “8” is now on the right side of “9”, a violation of the binary search tree’s
properties. When “8” is deleted, then the tree becomes a binary search tree again.
A common mistake at line 49 is calling Tree
delete(tn, val). This is wrong because
“8” is smaller than “9”. Using Tree
delete(tn, val) causes the function to search for
(and attempt to delete) “8” from the left side of “9”. Since “8” is not on the left side, the
function will fail to do anything. If nothing is deleted, the function returns the root tn and
this line becomes tn -> right = tn. A node that is its own parent creates many problems
and furthermore all nodes to the right side (“8”, “11”, and “12”) are lost.
Another common mistake is to write while (su != NULL) at line 40. The while loop
will continue until su is NULL, and the program will have segmentation fault at line 46 when
it attempts to read su -> value.
20.6 Destroying a Binary Search Tree
The Tree destroy function destroys the whole tree by releasing the memory occupied
by all the tree nodes.
// treedestroy.c
1
#include "tree.h"2
#include <stdlib.h>3
void Tree_destroy(TreeNode * n)4
{5
if (n == NULL)6
{7
return ;8
}9
Tree_destroy(n -> left);10
Tree_destroy(n -> right);11
Binary Search Trees 331
free(n);
12
}13
Note that every node must be destroyed once, and only once. Thus it is necessary to
traverse the tree. Also note that both left and right must be destroyed before this tree
node’s memory is released. Can you tell what type of traversal this is?
20.7 main
Below is a main function that inserts and deletes random values into a binary search
tree:
// main.c
1
#include "tree.h"2
#include <time.h>3
#include <stdlib.h>4
#include <stdio.h>5
int main(int argc , char * argv[])6
{7
TreeNode * root = NULL;8
int num = 0;9
int iter;10
unsigned i nt seed = time(NULL);11
seed = 0;12
srand(seed);13
if (argc >= 2)14
{15
num=(int) strtol(argv[1], NULL, 10);16
}17
if (num < 8)18
{19
num = 8;20
}21
int * array = malloc( sizeof( int) * num);22
for (iter = 0; iter < num; iter ++)23
{24
array[iter] = rand() % 10000;25
}26
for (iter = 0; iter < num; iter ++)27
{28
int val = array[iter];29
printf("insert%dn", val);30
root = Tree_insert(root, val);31
Tree_print(root);32
}33
for (iter = 0; iter < num; iter ++)34
{35
int index = rand() % (2 * num);36
if (index < num)37
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.