a. Show the result of inserting 3,1,4,6,9,2,5, 7 into an initially empty binary search tree.
b. Show the result of deleting the root.
2. Splay Tree
a. Show the result of accessing the keys 3,9,1,5 in order in the splay tree
b. Show the result of deleting key 6 after doing (a).
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?
4. B-trees
a. 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.
b. 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.
