5.7.3 Multiway Search Trees and B-Trees

The objective of this assignment is to implement insertions and deletions in multi-way search trees and B-trees, and evaluate their performance. Three scenarios are considered: insertions alone; deletions alone; and insertions and deletions interleaved randomly.

• Scenario 1 - Insertions only:

Generate a random permutation of n numbers, say a₁, a₂,..., a_n. Insert these elements into an initially empty data structure. This process will result in a multi-way search tree and a B-tree, each with n nodes. The order of the tree to be constructed, m, is given as an input. Note that a binary search tree is a multi-way search tree with m = 2, whereas a 2-3 tree is a B-tree with m = 3. Also the number of records per leaf is also to be specified as part of the input. Choose a small number, say 2 or 3, here.
• Scenario 2 - Deletions only:

Start with the tree constructed in Scenario 1 and delete the n elements, one by one, in the following orders:
• In the order of insertion
• In the reversed order of insertion
• In a random order
• Scenario 3 - Interleaved Insertion and Deletions:

Start with the tree constructed in Scenario 1 and do a series of randomly interleaved insertions and deletions. Assume that insertions and deletions are equally likely. Assume that elements currently in the tree and elements not currently in the tree are generated with equal probabilities.

The performance measures are the following:

• Average height of the tree. You should compute it for both MST and BT in all the three scenarios. Also, you should be able to compute the respective heights at any intermediate stage. It should be possible to break execution at any desired point and track the probe sequence for a desired operation.
• Average number of probes required for insertions and deletions. This can be computed for each type of tree in each of the three scenarios.

Repeat the above experiment for several random sequences to obtain better and more credible performance estimates. You will get bonus marks if you implement B*-trees also.