CSE 326, Spring 1995: Homework 5

Due 5/3/95

1. (20 points) Design a recursive AVL tree deletion procedure. You may assume that rotation and height calculation procedures are available to you. Your procedure should be based on the attached recursive binary search tree deletion algorithm.
2. (10 points) Design an efficient algorithm for finding the minimum in a binary search tree that employs lazy deletion. You should consider adding two extra fields, one which marks nodes as deleted and one which marks a node if all the nodes in the subtree rooted at the node are deleted. What is the time complexity of your algorithm in terms of the height of the binary search tree?
3. (10 points) Design an efficient algorithm for binary search trees which, given two keys x and y prints out all the keys in the binary search tree which are between x and y, inclusive. For example, if the binary search tree contains the elements 1,5,9,11,12,20,25,30,35, and your algorithm is called with x = 5 and y = 21 then 5,9,11,12,20 are printed. What is the time complexity of your algorithm as a function of the height of the binary search tree and the number of items actually printed.