### **Homework 5, Fundamental Algorithms, Fall 97**

Due Date: Monday, October 13.

Problems 2.6. (See back of text, page 398).

2. 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.

Course Home Page

cole@cs.nyu.edu (Richard Cole)

Last modified: Oct 3, 1997