CH08-320201-HOMEWORK8 Solved

HOMEWORK8

ALGORITHMS AND DATA STRUCTURES (CH08-320201)



             Problem 1: Understanding Red Black Trees                                                                       (3+3+3* = 9 points)
Make sure you submit your solution in the specified format. Points will be deducted if your solution does not follow the format. For a short explanation of pre-order tree traversal, check this assignment’s last page.

FORMATFORA) ANDB): Write your solutions into the text files solutiona.txt and solutionb .txt, respectively. Each tree is to be represented using pre-order traversal. Separate individual values within trees with single spaces. Separate different trees with new lines. Each node’s value needs to be immediately followed by ’B’ or ’R’, representing the node’s color. Do not add nil nodes. Example: 17B 12R 7R. You are welcome to also upload your detailed solution (drawn trees), into solutiondetailed.pdf. Grading will be based on the .txt files that you submit, but in case they are incorrect, we can give you partial points for the detailed solution. FORMATFORC): Please submit your argumentation in the file solutionc.pdf.

(a)    Describe all valid red-black trees that store the numbers 1,2,3,4,5.

(b)    Describe the red-black trees that result after successively inserting the keys [14, 42, 35, 7, 26, 17] into an empty red-black tree. You are required to describe the tree after each insertion, as well as any additional recoloring and balancing.

(c)     Bonus. Consider a red-black tree formed by inserting n nodes with the algorithm described in class. Argue that if n>1, the tree contains at least one red node.

             Problem 2: Implementing Red Black Trees                                                                                        (16 points)
Implement a Red Black Tree (with integer nodes), closely following the specifications and algorithms from the lecture. Write your code either in C++ or Python - no other languages will be accepted. Save your solution to rbt.py for Python and rbt.cpp (header in rbt.h) for C++. Make sure you handle errors appropriately.

Grading will be based on case-tests, therefore make sure that you use the exact naming of functions and classes below. We will test all functions, classes, structs that are listed below. Feel free to define any number of helper functions.

 enum Color { RED, BLACK };

struct Node

{

5int data;

Color color;

Node *left, *right, *parent;

};

10class RedBlackTree

{ private:

Node *root; protected:

15void rotateLeft(Node*&);

void rotateRight(Node*&);

public:

RedBlackTree(); void insert(int);

20void delete(Node*&);

Node* predecessor(Node*&);

Node* successor(Node*&);

Node* getMinimum();

Node* getMaximum();

25Node* search(int);

};

Listing 1: Methods and classes to implement for a Red Black Tree

Background: Pre-order tree traversal
Trees can be represented with the pre-order traversal.

 function preorder(tree):

1.      Write down tree.value.

2.      Call preorder(tree.left_child)

3.      Call preorder(tree.right_child)

The following tree is represented via pre-order traversal by: a b d e c f.