6. Red-Black Trees

A popular alternative to the AVL tree is the red-black tree.

The popularity of this BST comes from the fact that each operation takes \(O(\log N)\) time in the worst-case.

An added bonus is that it is easy to implement a nonrecursive insertion function.

6.1. How is it different from another BST?

A red-black tree is a BST with the following coloring properties:

  1. Every node is colored either in red or black.

  2. The root is always black.

  3. If a node is red, its children must be black. (A null node is considered to be black node)

  4. Every path from a node to a null node must contain the same number of black nodes.

These rules ensure that the height of a red-black tree is at most \(2\log (N+1)\).

The direct consequence is that searching is guaranteed to be a logarithmic operation.

The following figure represents a red-black tree. The red nodes are shown with double circles.

../../_images/rbt.drawio.png

Activity

  • Check that each property is respected.

  • What happens if we insert a new node?

Red-black tree will be similar in terms of structure to a BST with some modifications:

 1/**
 2 * Self-balancing binary search tree using algorithm defined by
 3 * Leo Guibas and Robert Sedgewick.
 4 * @param <E> Type contained in the tree.
 5 */
 6public class RedBlackTree<E extends Comparable<E>> extends BinarySearchTreeWithRotate<E> {
 7
 8    //Additional Data Field
 9    /* Flag to indicate success of adding an item */
10    private boolean addReturn;
11
12    /**
13     * Class to represent a Red-Black node
14     * @param <E> The data type of items stored in the node. Must be Comparable
15     */
16    private static class RedBlackNode<E> extends Node<E> {
17
18        //Additional Data Fields
19        /* Color indicator; true if red, false if black */
20        private boolean isRed;
21
22        /**
23         * Constructor to create a node with the default color of red with the given data
24         * @param data The data item to be stored in the node
25         */
26        public RedBlackNode(E data) {
27            super(data);
28            isRed = true;
29        }
30
31        //Methods
32        /**
33         * Return a String representation of the node
34         * @return A String representation of the node
35         */
36        @Override
37        public String toString(){
38            if(isRed){
39                return "Red: " + super.toString();
40            } else {
41                return "Black: " + super.toString();
42            }
43        }
44
45    }
46}

6.2. Insertion

We can see that inserting a new node in the tree is not simple.

We consider that the nodes are initially colored in red to maintain property 4. Then there are few cases to consider.

We can take the figure to illustrate the different cases:

  • If the parent is black:

    • We are done.

  • If the parent is red.

    • It will violate condition 3.

    • We need to adjust the tree to ensure condition 3 is enforced.

Basically, we need to focus on the cases in which the parent is red.

6.2.1. Case 1

The parent sibling is also red.

We can change the grandparent’s color to red and change the parent and parent’s sibling color to black.

If the grandparent is also the root, then we change its color to black to restore property 2.

../../_images/rbt_case_1.drawio.png

6.2.2. Case 2

This case appears when we insert a new node with a red parent, but the parent does not have a sibling.

The situation is more complicated and we need to apply the following processes:

  • Color the grandparent to red.

  • Color the parent to black.

    • Note that it violates the property 4.

  • Apply a left rotation around the grandparent.

../../_images/rbt_case_2.drawio.png

Activity

  • Insert 2 in the following tree and balance it.

../../_images/rbt_activity_1.drawio.png

6.2.3. Case 3

The last case is the most complicated one.

It happens when we insert a left node of a right node.

Then we need to apply a double rotation.

Consider the following example.

Example

Consider the following tree.

../../_images/rbt_case_3_1.drawio.png

If we insert 7 we obtain the following tree.

../../_images/rbt_case_3_2.drawio.png

We apply property 3 and color 7 to black.

../../_images/rbt_case_3_3.drawio.png

Then we apply the first rotation (right rotation).

../../_images/rbt_case_3_4.drawio.png

The issue now is that property 4 is not true anymore.

../../_images/rbt_case_3_5.drawio.png

To fix that we color 5 to red.

../../_images/rbt_case_3_6.drawio.png

Property 4 is not fixed yet, so we apply a left rotation on 5.

../../_images/rbt_case_3_7.drawio.png

Now, we can see that every properties holds.

../../_images/rbt_case_3_8.drawio.png

Activity

  • Consider the following tree.

  • Insert 25 and balance the tree.

../../_images/rbt_activity_2.drawio.png

6.3. Insertion

Before implementing the insertion, we must take a look at the pseudocode.

Algorithm

../../_images/insertion_algorithm_rbt.png

We can implement the start add method. This method only checks if the root is empty and insert the nod. Otherwise call the recursive method add.

public boolean add(E item) {
    if (root == null) {
        root = new RedBlackNode<>(item);
        ((RedBlackNode<E>) root).isRed = false;
        // root is black.
        return true;
    }
    else {
        root = add((RedBlackNode<E>) root, item);
        ((RedBlackNode<E>) root).isRed = false;  // root is always black.
        return addReturn;
    }
}

Now we can implement the recursive add method.

private Node<E> add(RedBlackNode<E> localRoot, E item) {
    if (item.compareTo(localRoot.data) == 0) {
        // item already in the tree.
        addReturn = false;
        return localRoot;
    }
    else if (item.compareTo(localRoot.data) < 0) {
        // item < localRoot.data.
        if (localRoot.left == null) {
            // Create new left child.
            localRoot.left = new RedBlackNode<>(item);
            addReturn = true;
            return localRoot;
        }
        else {   // Need to search.
            // Check for two red children, swap colors if found.
            moveBlackDown(localRoot);
            // Recursively add on the left.
            localRoot.left = add((RedBlackNode<E>) localRoot.left, item);
            // See whether the left child is now red
            if (((RedBlackNode<E>) localRoot.left).isRed) {
                // Check whether right grandchildren are red
                if (localRoot.left.left != null && ((RedBlackNode<E>) localRoot.left.left).isRed) {
                    // Left-left grandchild is also red.
                    // Single rotation is necessary.
                    ((RedBlackNode<E>) localRoot.left).isRed = false;
                    localRoot.isRed = true;
                    return rotateRight(localRoot);
                }
                else if (localRoot.left.right != null && ((RedBlackNode<E>) localRoot.left.right).isRed) {
                    // Left-right grandchild is also red.
                    // Double rotation is necessary.
                    localRoot.left = rotateLeft(localRoot.left);
                    ((RedBlackNode<E>) localRoot.left).isRed = false;
                    localRoot.isRed = true;
                    return rotateRight(localRoot);
                }
            }
        }
    }
    else{
    // ...
    }
}

Activity

  • Implement the method moveBlackDown(RedBlackNode<E> node).

  • This method swaps the color of the two children to black and node to red.

6.4. Deletion

After insertion, deletion is important too. And as the section suggest it, it can be down with a top-down strategy.

In practice, we need to be able to delete a leaf.

  • To delete a node \(X\) with two children, we swap it with the smallest node in the right subtree. Then delete it.

  • Same for a node with only a right child.

  • To delete a node with only one left child, we find the largest one in the subtree and swap it. Then we delete it.

Deleting a red leaf is trivial.

Important

However, deleting a black node will violate condition 4, so we need to ensure during the top-down pass that the leaf is red.

  • We start by coloring the root red.

  • When we arrive at a new node:

    • We are certain that \(P\) is red,

    • and \(X\) and \(T\) (the sibling) are black. (We cannot have two consecutive red nodes).

6.4.1. \(T\) has two black children

Then there are 3 subcases.

6.4.1.1. First case

In this case \(T\) has two black children.

We just need to flip the colors of \(X\), \(T\) and \(P\).

../../_images/delete_01.drawio.png

6.4.1.2. Second Case

The left children of \(T\) is red.

We apply a zig-zag rotation on \(R\).

../../_images/delete_02.drawio.png

6.4.1.3. Third Case

The right children of \(T\) is red.

We apply a double rotation on \(T\).

../../_images/delete_03.drawio.png

6.4.2. One of \(X\)’s children is red

We go to the next level to obtain new \(X\), \(T\) and \(P\).

If the new \(X\) is the red node, we can continue to the next level.

Otherwise \(T\) is red and \(X\) and \(P\) are black.

We rotate \(T\) and \(P\) making \(X\)’s new parent red.

At this point we can go back to the first main case.

6.5. Java API

Red-Black tree is implemented in the Java API java.util with the TreeMap class.