### **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