For all program or data structure design problems such as the two below you must provide pseudocode (see the manual) and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Straight pseudocode with no additional documentation is not enough. Your pseudocode can contain English if needed. This is assignment is for practice only, please do not turn in.
1 In this problem you will design a recursive AVL deletion procedure and execute it on a simple example.
o Design a recursive AVL tree deletion procedure. You may assume that rotation and height calculation procedures are available to you. Your procedure should be modeled on the recursive deletion procedure on page 115 of the text. After each recursive call and before returning, rotations must be done to rebalance the tree. See the way this is done for AVL tree insertion on page 128 of the text.
o Demonstrate your algorithm by doing all the rotations needed to delete 10 from the following AVL tree. If there is more than one rotation show the result after each single or double rotation.
20/ \
10 30
/ \ / \
5 15 25 35
/ \ \ \
3 7 18 40
\
9
2 In this problem you will demonstrate how splay tree insertion and deletion work on the example tree above.
o Insert 8 into the tree above. Show the tree after zig-zig, zig-zag, and zig operation.
o Delete 10 from the tree above. Show the tree after each zig-zig, zig-zag, and zig operation.
3 Show the result of inserting 1,2,…,12 in this order into an empty B-tree of order 3 (a 2-3 tree). Show the result after each insertion.
4 Imagine that you have been asked to to implement a new IRS database. There are 100,000,000 records, each of which take an average of 2,000 bytes. The records are keyed with a Social Security Number which is 4 bytes. The computer that you will be using has 2,048 byte pages and pages are addressed with 4 byte integers. Assume that a B-tree node completely as possible fills a page. This may means that leaves will hold may hold more or less keys than internal nodes depending on what data is stored on the leaves. Assume that the computer has 16 MB of memory that is usable for storing all or part of a search structure. For the B-tree, disk addresses are used for pointers, and a 2 byte integer is used to keep track of the length of the active area in the B-tree node. The leaves of the B-tree contain pointers to the actual records. We assume that the nodes, other than the root, of the B-tree are about 3/4-th full on average.
o Calculate the maximum number of children (M) that an internal node of the B-tree can have. Calculate the maximum number of entries (L) a leaf of the B-tree can have.
o Calculate the height of the B-tree with that order so that all the 100,000,000 records can be accessed. About how many children does the root have.
o Calculate how many levels of the B-tree can fit into the memory of the computer. Several full levels and the portion of one level will fit into memory.
o Calculate how many disk accesses in the worst case are necessary to find a specific record using this search structure. How many on average
5 Consider the following points. (10,20), (20,10), (15,15), (5,10), (10,4). Enter these into a balanced k-d tree. Show the work along the way.