Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Removing Items from an M-Way Search Tree

The algorithm for removing items from an M-way search tree follows directly from the algorithm for removing items from a binary search tree given in Section gif. The basic idea is that the item to be deleted is pushed down the tree from its initial position to a node from which it can be easily deleted. Clearly, items are easily deleted from leaf nodes. In addition, consider an internal node of an M-way search tree of the form

displaymath64705

If both tex2html_wrap_inline63521 and tex2html_wrap_inline62605 are empty trees, then the key tex2html_wrap_inline63523 can be deleted from T by removing both tex2html_wrap_inline63523 and tex2html_wrap_inline62605, say. If tex2html_wrap_inline63521 is non-empty, tex2html_wrap_inline63523 can be pushed down the tree by swapping it with the largest key in tex2html_wrap_inline63521; and if tex2html_wrap_inline62605 is non-empty, tex2html_wrap_inline63523 can be pushed down the tree by swapping it with the smallest key in tex2html_wrap_inline62605.

Program gif gives the code for the Withdraw method of the MWayTree class. The general form of the algorithm follows that of the Withdraw method for the BinarySearchTree class (Program gif).

   program20941
Program: MWayTree class Withdraw method.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.