Problem 9.1 Understanding Red Black Trees
(a) 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) Draw (or describe by using preorder traversal) all valid red-black trees that store the values {1,2,3,4}.
(c) Bonus 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
Implement a red black tree (with integer nodes), closely following the specifications and algorithms 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 following or equivalent components:
enum Color {RED, BLACK}; struct Node
{ int data; Color color;
Node ∗left, ∗right, ∗parent;
};
class RedBlackTree
{ private:
Node ∗root; protected:
void rotateLeft(Node ∗&); void rotateRight(Node ∗&); public:
RedBlackTree(); void insert(int); void delete(Node ∗&);
Node ∗ predecessor(const Node ∗&);
Node ∗ successor(const Node ∗&);
Node ∗ getMinimum();
Node ∗ getMaximum();
Node ∗ search(int); };
