CSE 326, Spring 1998: Homework 4

Due 4/24/98

When asked to design an algorithm please provide the pseudocode with enough explanation that it can be understood easily.

1. (10 points) A generalization of the find operation in a binary search tree is the range query. Given a <= b, a range query returns a list of keys x such that a <= x <= b.
   • Design an efficient algorithm to do range queries.
   • Argue that your algorithm runs in worst case time O(h + k) where h is the height of the tree and k is the number of keys returned in the list.
2. (10 points) In this problem you will explore lazy deletion in an ordinary binary search tree. Assume that your nodes have four fields, data, left_child, right_child, and deleted. Deleted is a boolean field where true when the key is deleted, but still resides in the tree.
   • Design the lazy deletion algorithm that simply marks nodes as deleted.
   • Design an algorithm that finds the minimum.
   • Design an algorithm to put all the undeleted keys in order in an array.
3. (15 points) In this problem you will design a recursive AVL deletion procedure and execute it on a simple example.
   • 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 deletion procedure of lecture 8, slide 9 and the description of AVL deletion given in lecture 10.
   • Demonstrate your algorithm by doing all the rotations needed to delete 20 from the following AVL tree. If there is more than one rotation show the result after each rotation.

                                 20
                             /        \
                          10           30
                        /    \       /   \
                       5     15    25     35
                     /      /  \            \
                    3      12  18            40
                          /
                        11