At this point all the important operations on binary search trees have been considered except deletion. The purpose of this section is to derive an algorithm for deleting a record from a binary search tree so that the remaining tree is still a binary search tree. To delete a terminal record, simply replace it by a null tree. To delete a record with only one successor, simply insert the successor's subtree at the position occupied by the deleted node. For instance, in the tree shown in Figure 9.9(a), deleting 51 and 71 yields the tree shown in Figure 9.9(b).
Consider Figure 9.9 again. A difficulty occurs if you wish to delete 80, a record with two successors. The node 80 must be replaced by a record that will allow the tree to retain its binary search tree property. This means that the record replacing 80 must be at least as large as any record in the left subtree of 80, and no larger than any record in the right subtree of 80. There are two choices: replace 80 with the largest record in its left subtree or the smallest record in its right subtree.
Notice that the largest record in any binary search tree is always found by going to its root and following right successors until a null tree is reached. The smallest record is found by going to its root and following left successors until a null tree is reached. Thus, in the example, we may take either 77's or 81's record to replace 80's record. The record selected, say 77, must then be inserted in place of 80's record, which is then effectively deleted. Taking 77 requires that 74's record replace it. The result is Figure 9.9(c). It should be clear that searching, inserting, or deleting, using the procedures in a search tree of depth d, will take worst-case time proportional to d.
Binary search trees are treated in this chapter as abstract objects. A sequential representation for deep but sparse trees requires array lengths proportional to 2d - 1. Deletions for this representation require a great deal of shifting of records. For instance, to delete 85 requires shifting 84, 83, and 81. To save storage, and to achieve faster insertions and deletions, requires using a linked representation.
