Programming Assignment 3 Solution

This programming assignment is to help you practice with the binary search tree data structure. In this assignment, irrespective of the language you are using, you have to implement the BST data structure from scratch.




The problem concerns maintenance and operations on a dynamic set of intervals. You are given a set of intervals, with insertion and deletion operations. You have to implement the operations Insert, Delete, Min, Max, LoSucc, HiSucc and IsOverlap where, these operations are de ned as follows. An interval i is de ned as the pair (i:lo; i:hi). For the purposes of the problem, assume that no two intervals have the same lo value and no two intervals have the same hi value. Let T denote the dynamic set of intervals.




Insert(T; i) inserts the interval i to the dynamic set T .



Delete(T; i) deletes the interval i from T . If T did not contain i, then this operation makes no change to T .



The Min (T ) operation on a dynamic set of intervals returns an interval with the smallest value of the lo eld among all the intervals in the set.



The Max (T ) operation, returns an interval with the largest value of the hi eld.



The operation LoSucc(T; i) takes an interval i and returns the interval that follows this interval in the sorted order of all the intervals by lo eld (or returns NIL).



The operation HiSucc(T; i), takes an interval i and returns the next interval in the sorted order by the hi eld (or returns NIL).



The operation IsOverlap(T; q), where, i is a given query interval returns 1 if q overlaps with some interval in T and is 0 otherwise (i.e., q does not overlap with any interval of T ).



Input: The input will be an interleaved sequence of operations de ned above encoded in the following way.




1. Intervals may be input pre xed by + (for insertion) or for deletion. Interval coordinates are real numbers of the from l h (with whitespace in between). It may be assumed that l < h. However, l; h may be positive or negative.







The min operator is speci ed as min with whitespace before and after. Similarly, the max operator is speci ed as max .



The operator LoSucc is speci ed as lsucc (with whitespace) and similarly HiSucc is speci ed as hsucc.









1



The operator IsOverlap(i) is speci ed as overlap (with whitespace) followed by the query interval l h.



The input is a single line. To process the input, think of the input as a sequence of commands, starting with + or or min or max or lsucc or hsucc or overlap. Each command, depending on its de nition, will take some argument(s) as de ned above. The + and commands do not yield any output. The other operators give outputs as de ned. The operators min, max, lsucc or hsucc return an interval with the syntax [l h] (whitespace in between). The operator overlap returns 0 or 1 as per its de nition.




Example. Consider the input.




+ 1 5 + 2 4 +3 8 + 11 13 min hsucc 2 4 + 12 20 max overlap 9 10




Explanation. First insert [1; 5], then insert [2; 4], next insert [3; 8], then insert [11; 13]. Now nd the interval with the minimum lo eld, which is [1; 5] ; next nd the HiSucc of [2; 4] which is [1; 5]. Next insert [12; 20], then solve max, which is [11; 13]; and nally, check for overlap with the interval [9; 10], whose answer is 0. The output in a single line is




[1 5] [1 5] [11 13] 0



















































































































2