Problem descrption

In this programming assignment, you will implement the Red-Black tree data structure. This will include the insert routine, re-balance routine, prefix tour routine, and visit routine. The tree should be implemented using nodes having fields "data, color, parent, left child, right child". Pointer root points to the root node.

Input format : 

Your input will consist of a single number n, which denote the number of insertions to be made, followed by n numbers a_i, which denote the numbers to be inserted into the red-black tree.

n a_1 a_2 .... a_n

Output format : 

Your output will consist of n different lines, each corresponding to the prefix tour print statement of a particular node on your tour. The order in which you print the information is determined by the red-black tree structure that is formed by the input, and the prefix tour algorithm that has been given in the statement on Moodle. The format will be "V C P", with V denoting Value at the node, C denoting color of the node, and P denoting the parent of the node. 

Sample Input :

5 4 1 6 10 11

Sample Output :

1 B 4

4 B NIL

6 R 10

10 B 4

11 R 10

Note that the root has parent denoted by "NIL" and color Black. This convention will have to be adhered to for your output. Also, this sample test case provided here is the first test case, but your code will be tested on other test cases as well. Passing just the first test case will not get any credit.