Page 131 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes If we want to delete a node pointed to by x, then we can do it as follows: Let y be a pointer to the
node which is the root of the node pointed to by x. Make the left child of the node pointed by y
to be the right child of the node pointed by x, and dispose the node pointed by x as shown below
in Figure 6.6:
Figure 6.6: A Binary Tree after Deletion of a Node Pointed to by x

50

y
60
30
x 65
52
25 35

Nil
55
15

53 57

56 58

y->lchild = x->rchild;
x->rchild = NULL;
delete(x);

6.4.3 Deletion of a Node with no Child

Consider the binary search tree shown below in Figure 6.7:

Figure 6.7: A Binary Tree before Deletion of a Node Pointed to by x

50

y
60
30
x 65
52

Nil Nil

Let the left child of the node pointed by y be nil, and dispose node pointed by x as shown in
Figure 6.8.

126 LOVELY PROFESSIONAL UNIVERSITY