In Linux, red black tree is used for a couple of applications in the Completely Fair Scheduler and for keeping track of the virtual memory segments for a process.
In the completely fair scheduler, the process’ virtual runtimes are used as the key and the start address of the range is used as the key for keeping track of the virtual memory segments for a process.
A main benefit of employing red black tree in above applications is to retrieve a node by its key faster than linear time likely otherwise.
1. Implement insertion and deletion for a red-black tree as defined in class.
Note that insertion should check for duplicate keys, and when there is no such key after exhausting the input in case of deletion, display “the key does not exist.”
Example input file:
in 56.in 23.in 45.in 7.in 5.in 23.del 45.del
Example output: For the same input example file as above, the output should will be as follows:
Operation: 56.in
Before: NULL / EMPTY
After: 56B
Operation: 23.in
Before: 56B
After: 23R 56B
Operation: 45.in
Before: 23R 56B
After: 23R 45B 56R
Operation: 7.in
Before: 23R 45B 56R
After: 7R 23B 45B 56B
Operation: 5.in
Before: 7R 23B 45B 56B
After: 5R 7B 23R 45B 56B
Operation: 23.del
Before: 5R 7B 23R 45B 56B
After: 5R 7B 45B 56B
Operation: 45.del
Before: 5R 7B 45B 56B
After: 5B 7B 56B
Note: The output will be different if the traversal mentioned is different in the input file i.e. for input “ post 1.in 3.in 5.in 5.del 2.in” the output would be different as the “post” traversal would produce a different output even though the tree looks similar. The output should be printed as per the traversal mentioned in the input.
