CSCE 221

Programming Assignment 4

Red-Black Trees

Approved Includes

Code Coverage

Starter Code

Files to Submit

Task

Requirements

Files

Class

Member types (public)

Functions (public)

Constructors & Rule of Three

Element Access

Iterators

Capacity

Modifiers

Lookup

Visualization

For Testing

Optional

Example

Example Output

Red-Black Tree Insert and Remove Help

CSCE 221 Spring 2021

Approved Includes

<cstddef>

<iostream>

<sstream>

<stdexcept>

<utility>

<tuple>

“red_black_tree.h”

Code Coverage

You must submit a test suite for each task that, when run, covers at least 90% of your code. You should,

at a minimum, invoke every function at least once. Best practice is to also check the actual behavior

against the expected behavior, e.g. verify that the result is correct. You should be able to do this

automatically, i.e. write a program that checks the actual behavior against the expected behavior.

Your test suite should include ALL tests that you wrote and used, including tests you used for debugging.

You should have MANY tests.

Starter Code

compile_test.cpp

Makefile

red_black_tree.h

red_black_tree_tests.cpp

Files to Submit

red_black_tree.h

red_black_tree_tests.cpp

CSCE 221 Spring 2021

Task

Implement a Red-Black tree (auto-balancing binary search tree).

You can implement a top-down or bottom-up Red-Black tree. The top-down tree is more efficient but,

since it must be done iteratively as opposed to recursively, the code will be more complex and therefore

more prone to errors.

Requirements

Files

red_black_tree.h – contains the template definitions

red_black_tree_tests.cpp – contains the test cases and test driver (main)

Class

template <typename Comparable>

class RedBlackTree;

Member types (public)

enum Color {RED,BLACK} – member constants for node color, e.g. RedBlackTree<T>::RED

struct Node – must have attributes Comparable value, Node* left, Node* right, and int color (in any

order). The name of the class does not need to be Node.

Functions (public)

Constructors & Rule of Three

RedBlackTree() – makes an empty tree

RedBlackTree(const RedBlackTree&) – constructs a copy of the given tree

~RedBlackTree() – destructs this tree

RedBlackTree& operator=(const RedBlackTree&) – assigns a copy of the given tree

Element Access

N/A

Iterators

Optional

Capacity

Optional

CSCE 221 Spring 2021

Modifiers

void insert(const Comparable&) – insert the given lvalue reference into the tree

void remove(const Comparable&) – remove the specified value from the tree (use minimum of

right child tree when value has two children)

Lookup

bool contains(const Comparable&) const – returns Boolean true if the specified value is in the

tree

const Comparable& find_min() const – return the minimum value in the tree or throw

std::invalid_argument if the tree is empty

const Comparable& find_max() const – return the maximum value in the tree or throw

std::invalid_argument if the tree is empty

Visualization

Optional, but strongly recommended.

For Testing

int color(const Node* node) const – return the color of the specified node (the null pointer is

black). This function is required to be public by the instructor’s tests.

const Node* get_root() const – return the root of the tree or nullptr if the tree is empty. This

function is required by the instructor’s tests.

Optional

RedBlackTree(RedBlackTree&&) – move constructs a copy of the given (rvalue) tree

RedBlackTree& operator=(RedBlackTree&&) – move assigns a copy of the given (rvalue) tree

bool is_empty() const – returns Boolean true if the tree is empty

void insert(Comparable&&) – insert the given rvalue reference into the tree using move semantics

void make_empty() – remove all values from the tree

void print_tree(std::ostream&=std::cout) const – pretty print the tree

CSCE 221 Spring 2021

Example

// make an empty tree

RedBlackTree<int> tree;

// insert 5 values into the tree

std::cout << “insert 6, 4, 2, 8, 10 ” << std::endl;

tree.insert(6);

tree.insert(4);

tree.insert(2);

tree.insert(8);

tree.insert(10);

// print the tree (this is not executed on Gradescope)

std::cout << “tree: ” << std::endl;

{

std::ostringstream ss;

tree.print_tree(ss);

std::cout << ss.str() << std::endl;

}

std::cout << “contains 4? ” << std::boolalpha <<tree.contains(4) << std::endl;

std::cout << “contains 7? ” << std::boolalpha << tree.contains(7) <<

std::endl;

// remove the root

std::cout << “remove 4” << std::endl;

tree.remove(4);

// find the minimum element

std::cout << “min: ” << tree.find_min() << std::endl;

// find the maximum element

std::cout << “max: ” << tree.find_max() << std::endl;

// print the tree (this is not executed on Gradescope)

std::cout << “tree: ” << std::endl;

{

std::ostringstream ss;

tree.print_tree(ss);

std::cout << ss.str() << std::endl;

}

CSCE 221 Spring 2021

Example Output

insert 6, 4, 2, 8, 10

tree:

R:10

8

R:6

4

2

contains 4? true

contains 7? false

remove 4

min: 2

max: 10

tree:

R:10

8

6

2

CSCE 221 Spring 2021

Red-Black Tree Insert and Remove Help

1. The textbook has the cases. The rules are different for bottom-up and top-down trees,

so it depends on which way you go. Assuming you go top-down (which is recommended

for efficiency), we have the following rules for insert:

1. on the way down, a black parent with 2 red kids → flip the colors

1. if the grandparent is also red, do the appropriate AVL rotation and re-color

(new “root” is black, kids are red)

2. after insert, if the parent is red, do the appropriate AVL rotation around

grandparent and re-color (new “root” is black, kids are red)

2. For remove, the idea is to make sure the node we eventually remove (which will be a

leaf because removing an internal node is just a value replacement) will be red

1. turn the parent of the root red (pretend the root has a parent and it is red)

2. on the way down

1. the parent is always red (this is the property we maintain)

2. therefore the current node and its sibling are black

3. if the current node has 2 black kids, there are 4 cases:

1. sibling also has 2 black kids → flip the colors

2. sibling has a red kid on the inside (near the current node) → AVL

double rotation to bring that red kid up to the root of the subtree

(where parent is now) and re-color (red kid stays red, parent and

sibling are black, current node is red)

3. sibling has a red kid on the outside (away from the current node)

→ AVL single rotation to bring the sibling up to the root of the

subtree (where parent is now) and re-color (sibling turns red,

parent and red kid turn black, current node turns red)

4. if the sibling has two red kids, then you can do either rotation (i.e.

choose case 2 or 3).

4. else, the current node has a red kid so we fall through to the next level

and hope we land on the red kid so we can continue (fall through again

because we want the parent to be red)

1. if we land on the black kid, we know the parent is black and sibling

is red, so we rotate the parent with the sibling to make the current

node’s new parent red and its grandparent black. then we

continue from the first main case (parent is red, current and sibling

are black)

Sale!