Assignment 2: Red-Black Tree

Modify your solution to assignment 1 to add tree balancing using the red-black algorithm (for insert only). You may at your option add a parent pointer to the tree.

Repeat the timing measurements of assignment 1 and submit a graph with 4 curves¹:

• random order, unbalanced (data from assignment 1)
• sorted order, unbalanced (data from assignment 1)
• random order, balanced
• sorted order, balanced

If you need to, reuse the hand-in checklist.

• 1  Or 4 graphs with one cuve each (whatever).