Description: You are expected to implement a balanced binary search tree (specifically a Red-Black (RB)-Tree) which performs operations and queries displayed below. Then you are required to improve it by augmenting the tree structure. You must insert each line in “people.txt” to both RB-Tree and Augmented RB-tree. Assignment will be coded in Java. Note: ‘people.txt’ contains id of a person, birthdate of this person (day/month/year) separated by comma (,). Trees will be generated by the age.

• INSERT: insert an input item (each line in ‘people.txt’)
• GETNUMSMALLER1: get the number of people who are born before a given input date
• GETNUMSMALLER2: get the number of people who are born before a person with a given id
• GETMAX: get maximum aged (oldest) person and print the id and birthdate of the person
• GETMIN: get minimum aged (youngest) person and print the id and birthdate of the person
• GETNUM: get number of all people in the tree by using in-­‐‐order tree walk.
• PRINT: display all items of the tree by applying in-­‐‐order tree walk.

• The program should run the methods in the following order for testing.
• Insert all elements in the input file (people.txt)
• Print the result of GETNUMSMALLER1 for the item with value 7/6/1991
• Print the result of GETNUMSMALLER2 for the item with value 9988
• Print the maximum age (with the birthdate and id)
• Print the minimum age (with the birthdate and id)
• Print the number of all items (GETNUM)

Improve the RB-Tree class by augmenting the structure so that each node holds an additional field: the number of all nodes (age) that are smaller than the current node’s age. Note that you need to update this value on each insert operation. You must update some of operations for this Augmented RB-tree. Not all operations will be the same as in the original RB-tree. Consider the additional field and plan which operations should be updated.

An example output of your program should appear as follows (This is just an example output which may not be correct output of your code for the ‘poeple.txt’)

------ RB-Tree ------

• All items were inserted.

• The result of GETNUMSMALLER1 for the node with birthdate 7/6/1991 is 35

• The result of GETNUMSMALLER2 for the node with id 9988 is 35

• The maximum age of all people is 98, id : 4434, Birthdate : 1920

• The minimum age of all people is 13, id : 6060, Birthdate : 2003

• The number of all people is 49

------ Augmented RB-Tree ------

• All items were inserted.

• The result of GETNUMSMALLER1 for the node with birthdate 7/6/1991 is 35

• The result of GETNUMSMALLER2 for the node with id 9988 is 35

• The maximum age of all people is 98, id : 4434, Birthdate : 1920

• The minimum age of all people is 13, id : 6060, Birthdate : 2003

• The number of all people is 49

Menu

1- Insert a new person**

2- GETNUMSMALLER

3- GETMAX

4-GETMIN

5-GETNUM

6-PRINT**

Prepare a menu as shown above. After choosing between 1-6, provide other necessary inputs from the user. Note: Your code must work on different kind of inputs (Two input fields, it means that your input data types must be Generic). You are expected to change your input with a new file in the code control.

Prepare a report that explains which methods / functions are updated in the Augmented RB-Tree. Why did you update these functions? What kind of advantages / disadvantages were obtained by Augmented RB-Tree?