To accomplish an insertion, storage must first be allocated for a new record. Next, its fields must be set correctly; this includes entering data into the record and setting its pointers to the succeeding left and right nodes, or to null if it is a leaf. Finally the proper pointer adjustments must be made in the tree to the predecessor of the new entry. Consider Figure 7.6, which shows a binary tree t before and after the insertion of a new entry C, which replaces predecessor O's null right subtree. The information for the new record is assumed to reside in value, so C is stored in value. Thus the new record must have its information field set to value and its left and right pointer fields set to null. The predecessor's right pointer field must be set to point to the new record. This is accomplished by the following.
p = avail();
setinfo(p,&value);
setleft(p,null);
setright(p,null);
setright(predecessor,p);
Setinfo copies the contents of the storage pointed to by its second parameter into the info field of the record pointed to by its first parameter. Note that it is defined somewhat differently from the setinfo used in previous chapters. Setleft and setright copy the contents of their second parameter into the proper field of the record pointed to by their first parameter. Notice that setleft is used to set the left pointer of the new record; similarly for setright. However, setright is also used to change the right pointer of the predecessor record so that it points to the new record, which is now its right node. Thus setleft and setright can be used to set pointers for any node in the tree. Together with setinfo and avail, these functions reflect the binary tree's implementation details. The code for the insertion itself is independent of the implementation.
If a new record is to replace a nonnull subtree (say, if C were to replace U in t), then the new record's left and right pointer fields would have to be adjusted accordingly. The left and right pointers from U would have to be copied into the new record's (C's) pointer fields. Furthermore, the storage for the replaced record U might be reclaimable. If so, care is required to save the pointer to it in its predecessor's left or right field so that its storage can be reclaimed. In this example, after saving the pointer to U, the right pointer of U's predecessor, L, would be replaced by a pointer to C, its new right node. Then U's storage can be reclaimed. The code below does this correctly, assuming predecessor points to a record whose nonnull right subtree is to be replaced.
Right returns a copy of the right pointer field value of the record pointed to by its parameter. This code is for illustrative purposes. If the record is really reclaimable, it would be more efficient simply to replace its info field by the new info value. The statement setinfo(q,&value) would suffice. However, if the replaced record were needed for another purpose, say for insertion in another binary tree, then this would not work.
The deletion of a terminal node pointed to by p, whose predecessor is pointed to by predecessor, may be accomplished by the following.
Left is analogous to right. The decision is required in order to know whether it is predecessor's left or right successor that is to be deleted. Again, if the deleted node's storage may be reclaimed, care must be taken not to lose the pointer to it. Deletion of an internal node must take into account what is to be done with the node's subtrees.
The wary reader may have qualms about the code developed for insertion and deletion. Remember?/FONT>special cases must always be checked. When insertion or deletion occurs at the root node, indicated by a null value in predecessor, it is the name of the tree whose pointer must be adjusted. The illustrative code fails in this case. You should modify the program segments so that they also account for this special case.
Figure 7.6 A Binary Tree T before and after the Insertion of C
q = right(predecessor);
p = avail();
setinfo(p,&value);
setleft(p,left(q));
setright(p,right(q));
setright(predecessor,p);
reclaim(q);
if(left(predecessor) == p)
setleft(predecessor,null);
else
1 otherwise
setright(predecessor, null);
1 set its predecessor's right pointer to null