Problem 9.1 Understanding Red Black Trees (9 points)
(a) (3 points) Draw (or describe by using preorder traversal) the red-black trees that result after successively inserting the values step by step in the following order [13; 44; 37; 7; 22; 16] into an empty red-black tree. You are required to draw (or describe by using preorder traversal) the tree after each insertion, as well as any additional recoloring and balancing.
(b) (3 points) Draw (or describe by using preorder traversal) all valid red-black trees that store the values f1; 2; 3; 4g.
(c) Bonus (3 points) Consider a red-black tree formed by inserting n nodes with the algorithm described in the lecture slides. Prove that if n > 1, the tree contains at least one red node.
Problem 9.2 Implementing Red Black Trees (16 points)
Implement a red black tree (with integer nodes), closely following the specifications and algo-rithms from the lecture. Make sure you handle errors appropriately by printing messages or throwing exceptions. Your implementation has to be along the interface below with the follow-ing or equivalent components:
enum Color {RED, BLACK};
struct Node
{
int data;
Color color;
Node left, right, parent;
};
class RedBlackTree
{
private:
protected:
void rotateLeft(Node &);
public:
RedBlackTree();
void insert(int);
Node predecessor(const Node &);
Node getMaximum();
};
How to submit your solutions
You can submit your solutions via Grader at https://grader.eecs.jacobs-university.de as a generated PDF file and/or source code files.
If there are problems with Grader (but only then), you can submit the file by sending mail to k.lipskoch@jacobs-university.de with a subject line that starts with CH-231-A.
Please note, that after the deadline it will not be possible to submit solutions. It is useless to send solutions by mail, because they will not be graded.
