[Solved] SOLVED:Lab Assignment 3

Goals:1. Understanding of red-black trees.2. Understanding of recursive binary tree processing.3. Understanding of subtree root ranks in binary search trees for supporting ranking queries.Requirements:1. Modify the provided C code for maintaining a red-black tree to process a sequence of commands (standard input) from thefollowing list:0 – Exit the program1 x – Insert positive integer key x, unless x is already present in the tree. Besides inserting the key, subtree root ranks mustbe updated. (Error message if x is a duplicate.)2 x – Find the rank of x, i.e. the number of keys in the tree that are smaller than x (error message if x is not in the tree).3 k – Find the key with rank k (error message if k is not between 0 and n – 1, inclusive).4 – Perform an audit on the subtree rank at each node to give a final indication that the tree is “clean” or “corrupt”.Each command must be echoed to standard output. Commands 1, 2, and 3 must be processed in€Θ(logn) time.2. Submit your program source files as a zipped file on Blackboard by 10:45 am on November 18. One of the comment linesshould include the compilation command used on OMEGA.Getting Started:1. The code changes for maintaining subtree root ranks during command 1 are minor and will include the rotation code.2. The code for commands 2 and 3 may be coded as variations on recursive search of a binary search tree, but recursion isnot required.3. Command 4 should traverse the tree, compute the rank of the root of each subtree, and verify the stored ranks. Optionally,you could also check 1) the inorder key property, 2) that there is no downward path with consecutive red nodes, and 3) theblack-heights are consistent.4. You are not required to maintain any satellite data related to the integer keys.5. You may use the driver in the lab directory.6. An example of a red-black tree with subtree root ranks:240/720/140/360/1 100/1120/3140/1160/15320/8330/0340/1300/2200/310/0 30/0 50/0 70/0 90/0 110/0 130/0 150/0180/1 220/1170/0 190/0 210/0 230/0 260/1250/0350/0280/3270/0 290/1 310/0285/080/77. The same tree as 6., but using subtree sizes:240/2020/340/760/3 100/3120/7140/3160/36320/12330/1340/3300/4200/710/1 30/1 50/1 70/1 90/1 110/1 130/1 150/1180/3 220/3170/1 190/1 210/1 230/1 260/3250/1350/1280/8270/1 290/2 310/1285/180/15