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

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

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?