Homework 6, Fundamental Algorithms, Fall 97

Due Date: Monday, October 20.

1. Explain how to modify a 2-3 tree so that it can store items which are pairs of the form (key, value), where the keys are used to order the items and the values are positive integers.

In addition to supporting the standard search, insert and delete operations, the modified 2-3 tree should also support the following query:

FindMinValue(LowKey, HighKey)

It reports the smallest value for the items with keys in the range [LowKey, HighKey].

e.g. For items (2,10), (3,9), (4,6), (5,22), (8,39), the query FindMinValue(3,5) returns the answer 6.

All the operations, including FindMinValue are to run in O(log n) time.

You need to explain how to modify the 2-3 tree, the changes, if any, needed in the implementation of search, insert, delete, and how to implement FindMinValue. Remember to explain how to achieve an O(log n) running time.

Problems 2.9, 3.2, 3.14. (See back of text, pages 398-403).

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Oct 13, 1997