CSE 326 Summer 2003
Homework 4

Due Wed July 23, beginning of class
This is a written assignment, so late homework is not accepted.

NOTE: If you collaborate with others, please be sure to do the problems on your own and write your own answers.  In addition, please write the names of your collaborators at the top of your paper.  Thanks!

70 Points total.

1. (20 points)
    a. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty AVL tree.

    b. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty Splay tree.

    c. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty Leftist Heap.

    d. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty Skew Heap.

2. (10 points) We define 2 binary trees to be similar if they are either both empty or else they are both nonempty and have similar left and right subtrees. Give an algorithm to decide whether 2 binary trees are similar. What is the running time of your algorithm?

3. (10 points) Give an algorithm that takes a binary search tree as input along with 2 keys, x and y, with x <= y, and prints all keys z in the tree such that x <= z <= y. What is the running time of your algorithm?

4. (10 points) Given the root of a tree, suppose we want to verify that the tree is an AVL tree.

    a. Give an algorithm to test whether the tree satisfies the search tree order property at every node. Your algorithm should run in O(n) time, where n is the number of nodes in the tree.

    b. Assuming height information is stored at each node, give an algorithm to test whether this height information is correctly maintained and whether the balance property is satisfied at each node. This method should also run in O(n) time.

5. (18 points) Define a level order traversal of a binary tree to traverse each node on the top level of the tree (the root) from left to right, and then the second level from left to right, . .., and finally each node on the lowest level of the tree from left to right. For example, the level order traversal of the tree below is 9,14,4,11,8,15,2.  Define a reverse level order traversal of a binary tree to traverse each node on the lowest level of the tree from left to right, and then each node on the second lowest level of the tree from left to right, ..., and finally each node on the top level of the tree (the root) from left to right. For example, the reverse level order traversal of the tree below is 2,11,8,15,14,4,9.  Please note that a reverse level order traversal is not just an inverted level order traversal. 
   

    a. Given the root of a binary tree, give an algorithm to print out the level order traversal. (Hint: consider what you learned in Homework 3!) 

    b. Given the root of a binary tree, give an algorithm to perform a reverse level order traversal of the tree. (Hint: try using a stack and queues in your algorithm)

6. (2 pts extra credit) A B*-tree of order M is a B-tree in which each interior node has between 2M/3 and M children. Describe a method to perform insertion into a B*-tree.

7. (2 points) What did you enjoy about this assignment? What did you dislike? Could we have done anything better?