[Solved] CE3345 Assignment 4

1. Show the result of inserting 3,1,4,6,9,2,5, 7 into an initially empty binary search tree.
2. Show the result of deleting the root.

[10 Points]

2. Splay Tree

1. Show the result of accessing the keys 3,9,1,5 in order in the splay tree [5 Points]
2. Show the result of deleting key 6 after doing (a). [5 Points]

3. Two binary trees are similar if they are both empty or both nonempty and have similar left and right subtree. Write a method to decide whether two binary tree are similar. What is the

running time of your method? [10 Points]

4. B-trees [10 Points]
   1. Given the following parameters:

1 Page on disk = 2048 bytes

Disk access time = 1milli-sec per byte

Pointer = 4 bytes

Key = 8 bytes

Data = 512 bytes per record (includes key) What are the best values for M and L.

2. Insert the following values in this order, into a B-tree where M = 3 and L =2.

8, 4, 6, 2, 3, 1, 7, 9

5. Given a binary search tree and a value k, write a pseudo code to find a node in the binary search tree whose value is closest to k. [10 Points]