Given a collection of points (their x and y coordinates), you are required to ou
ID: 3649734 • Letter: G
Question
Given a collection of points (their x and y coordinates), you arerequired to output all points that lie within (including the boundary
of) a rectangle where the rectangle is specified by the coordinates of
the end-points of one of its diagonals.
You are required to implement a binary search tree where each node
contains a point. The binary search property is defined differently
for even levels (root is at level 0) and odd levels. At even levels,
all nodes maintain the binary search property with respect to x-coordinate
whereas at odd levels, they do so with respect to y-coordinates. Equal
values belong in the left-sub-tree. You are not allowed to have duplicate
points in your tree. An error message should be output if insertion of
a duplicate point is attempted.
To test this data structure, write a main program that inputs a series
of transactions with a transaction code.
(I for insert a point,
S for search and output all points in the rectangle provided, and
O for output the data in the tree in in order).
Appropriate input data is given for each transaction. Read all this input from a file,
and produce the output in an output file.
Prompt the user to specify the name of the input file without hard coding it.
Produce a thoroughly neat, and self-explanatory output
Explanation throughout the code.
Test Data:
I 5 7 This means insert a point (5,7)
I 3 9
I 4 15
I 8 10
I 6 12
O Means output the data in the tree are in order
At this stage, make sure that your output is correct
by checking it manually.
I 3 7
I 5 3
O
I 5 7
I 10 15
I 7 6
O
S 1 3 4 9 Means search all points in the rectangle whose
diagonal joins end-points (1,3) and (4,9)
I 3 8
I 6 14
O
I 1 10
I 5 12
I 6 8
I 4 1
I 9 10
I 15 12
I 9 9
O
S 1 3 4 9
S 9 9 1 3
S 4 6 10 13
S 6 8 6 8
S 20 20 17 17
S 1 3 4 9