How to easily remember Red-Black Tree insert and delete?

Question

It is quite easy to fully understand standard Binary Search Tree and its operations. Because of that understanding, I even don't need to remember the implementations of those insert, delete, search operations.

I am learning Red-Black Tree now and I understand its properties for keeping the tree balanced. However I feel very hard to understand its insert and delete procedures.

I understand when inserting a new node, we mark the node as red (because red is the best we can do to avoid breaking less Red-Black tree laws). The new red node may still break the "no continuous red nodes law". Then we fix it via:

1. check its uncle's colour, if red, then mark its parent and uncle as black, and go to grandparent.

2. if it is right child, left rotate its parent

3. mark its parent as black and its grandparent as red, then right rotate its grandparent.

done (basically like above).

Many places describes Red-Black tree's insert like above. They just tell you how to do it. But why those steps can fix the tree? Why first left rotate, and then right rotate?

Can anyone explains why to me more clearly, even more clear than CLRS? What's the magic of rotation?

I really wish to understand so after 1 year, I can implement Red-Black tree by myself without review a book.

Thanks

Answer 1

ignore my (now deleted) comment - i think okasaki's code is going to help you. if you have the book ("purely functional data structures"), look at the text on page 26 and figure 3.5 (facing, p 27). it's hard to get clearer than that.

unfortunately the thesis available on-line doesn't have that part.

i'm not going to copy it out because the diagram is important, but it shows that all the different cases are basically the same thing, and it gives some very simple ML code that hammers that home.

[update] it looks like you may be able to see this on amazon. go to the book's page, mouse over the image and enter "red black" in the search box. that gives you results that include pages 25 and 26, but you need to be logged on to see them (apparently - i haven't tried logging in to check).

Answer 2

For the benefit of anybody else reading this thread who doesn't have access to the book mentioned in the accepted answer, here is what I hope will be an acceptable descriptive answer.

Rotating puts the tree in a state where it meets the criteria to recolor (the child node has a red uncle). There are two key differences:

• which node is the "child" and which node is the "uncle" has changed;
• instead of recoloring the parent and uncle to black and the grandparent to red, you recolor the parent to red, and the grandparent to black.

When the child node doesn't have a red uncle, you have to rotate because if the uncle node is already black, then making the parent black would increase the black height by 1 on only one side of the grandparent. This would violate the height invariant property of red-black trees and make the tree unbalanced.

Now let's look at how the rotation transforms the tree so that we have a child node with a red uncle and can use recoloring. I recommend drawing this out to fully understand it.

• Let x be the current red node with a red parent.
• Let p be the red parent of x before the rotation (if the parent was black, we'd be done already).
• Let y be the black uncle of x before the rotation (if the uncle was red, we wouldn't need a rotation. We'd simply recolor the parent and uncle to black and the grandparent to red).
• Let g be the black grandparent of x before the rotation (since the parent is red, the grandparent must be black; otherwise this was not a red-black tree to begin with.)
• When you have a left-left (LL) or right-right (RR) case (that is, x is the left child of p and p is the left child of g OR x is the right child of p and p is the right child of g), after a single rotation (right if LL, left if RR), y becomes the child and x its uncle. Since x is a red uncle, you now have a case where you can recolor. So, recolor the parent of the child (since the child is now y, its parent is g) to red, and the child's grandparent (which is now p) to black.
• When you have an LR (x is the left child or p and p is the right child of g) or RL case (x is the right child of p and p is the left child of g), after a double rotation (right then left if LR, left then right if RL), y becomes the child and p its uncle. Since p is a red uncle, you again have a case where you can recolor. So, recolor the parent (since the child is now y, its parent is g) to red, and the child's grandparent (which is now x) to black.

Before the rotation and recoloring, you had a black grandparent with 2 red nodes and 0 black nodes on side A (left or right) and 0 red nodes and 1 black node on side B (the opposite of side A). After the rotation and recoloring, you have a black grandparent with 1 red node and 0 black nodes on side A and 1 red node and 1 black node on side B. So you essentially moved one of the red nodes to the other sub-tree of the grandparent without increasing the black height of either sub-tree.

That's the magic of rotation. It allows you to move the extra red node to another branch without changing the black height, and still preserving the sorted traversal property of a binary search tree.

Answer 3

The logic is fairly simple. Suppose z is red and z's parent is red: If z's uncle is red, do step 1 to push the problematic node upwards until either (1) the parent becomes the root. Then simply mark the root black. Done or (2) z's uncle is black.

In case (2) either (a) z is the left child of its parent, then step 3 will be the last step as all properties of BST are fulfilled. Done. or (b) z is the right child of its parent. Step 2 will convert the problem to case (a). Then do step3. Done.

Thus the logic is to try to reach case (1) and (2a), whichever comes first. Those are the situations we know the solutions.

Answer 4

Any 2-4 (2-3-4) tree can be converted into a Red-black tree. And understanding of 2-4 trees is much easier. If you just go through the insert and delete operations in 2-4 trees, you will feel that there is no need to remember any rules to achieve the same. You will see a clear simple logic which enables you to come up with the solutions to take care of different insertion and deletion scenarios.

Once you have a clear understanding of 2-4 trees, when ever you deal with Red-black trees, you can mentally map this Red-black trees to 2-4 trees and come up with a logic by yourself.

I found following couple of videos which are extremely useful in understanding 2-4 trees, Red-black trees and mapping of 2-4 trees to Red-black trees. I would recommend to go through these videos.

1) For 2-4 trees : http://www.youtube.com/watch?v=JZhdUb5F7oY&list=PLBF3763AF2E1C572F&index=13

2) For Red-black trees : http://www.youtube.com/watch?v=JRsN4Oz36QU&list=PLBF3763AF2E1C572F&index=14

Even though they are one hour long videos each, I felt it was worth going through them.

Answer 5

Here is my implementation :

import java.util.Optional;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

/**
 *
 * @author Gaurav Ratnawat
 * <p>
 * Red Black Tree
 * <p>
 * Time complexity
 * Insert - O(logn)
 * Delete - O(logn)
 * Search - O(logn)
 * <p>
 * Does not work for duplicates.
 * <p>
 * References
 * http://pages.cs.wisc.edu/~skrentny/cs367-common/readings/Red-Black-Trees/
 * https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
 */
public class RedBlackTree {

    public enum Color {
        RED,
        BLACK
    }

    public static class Node {
        int data;
        Color color;
        Node left;
        Node right;
        Node parent;
        boolean isNullLeaf;
    }

    private static Node createBlackNode(int data) {
        Node node = new Node();
        node.data = data;
        node.color = Color.BLACK;
        node.left = createNullLeafNode(node);
        node.right = createNullLeafNode(node);
        return node;
    }

    private static Node createNullLeafNode(Node parent) {
        Node leaf = new Node();
        leaf.color = Color.BLACK;
        leaf.isNullLeaf = true;
        leaf.parent = parent;
        return leaf;
    }

    private static Node createRedNode(Node parent, int data) {
        Node node = new Node();
        node.data = data;
        node.color = Color.RED;
        node.parent = parent;
        node.left = createNullLeafNode(node);
        node.right = createNullLeafNode(node);
        return node;
    }

    /**
     * Main insert method of red black tree.
     */
    public Node insert(Node root, int data) {
        return insert(null, root, data);
    }

    /**
     * Main delete method of red black tree.
     */
    public Node delete(Node root, int data) {
        AtomicReference<Node> rootReference = new AtomicReference<>();
        delete(root, data, rootReference);
        if (rootReference.get() == null) {
            return root;
        } else {
            return rootReference.get();
        }
    }

    /**
     * Main print method of red black tree.
     */
    public void printRedBlackTree(Node root) {
        printRedBlackTree(root, 0);
    }

    /**
     * Main validate method of red black tree.
     */
    public boolean validateRedBlackTree(Node root) {

        if (root == null) {
            return true;
        }
        //check if root is black
        if (root.color != Color.BLACK) {
            System.out.print("Root is not black");
            return false;
        }
        //Use of AtomicInteger solely because java does not provide any other mutable int wrapper.
        AtomicInteger blackCount = new AtomicInteger(0);
        //make sure black count is same on all path and there is no red red relationship
        return checkBlackNodesCount(root, blackCount, 0) && noRedRedParentChild(root, Color.BLACK);
    }

    private void rightRotate(Node root, boolean changeColor) {
        Node parent = root.parent;
        root.parent = parent.parent;
        if (parent.parent != null) {
            if (parent.parent.right == parent) {
                parent.parent.right = root;
            } else {
                parent.parent.left = root;
            }
        }
        Node right = root.right;
        root.right = parent;
        parent.parent = root;
        parent.left = right;
        if (right != null) {
            right.parent = parent;
        }
        if (changeColor) {
            root.color = Color.BLACK;
            parent.color = Color.RED;
        }
    }

    private void leftRotate(Node root, boolean changeColor) {
        Node parent = root.parent;
        root.parent = parent.parent;
        if (parent.parent != null) {
            if (parent.parent.right == parent) {
                parent.parent.right = root;
            } else {
                parent.parent.left = root;
            }
        }
        Node left = root.left;
        root.left = parent;
        parent.parent = root;
        parent.right = left;
        if (left != null) {
            left.parent = parent;
        }
        if (changeColor) {
            root.color = Color.BLACK;
            parent.color = Color.RED;
        }
    }

    private Optional<Node> findSiblingNode(Node root) {
        Node parent = root.parent;
        if (isLeftChild(root)) {
            return Optional.ofNullable(parent.right.isNullLeaf ? null : parent.right);
        } else {
            return Optional.ofNullable(parent.left.isNullLeaf ? null : parent.left);
        }
    }

    private boolean isLeftChild(Node root) {
        Node parent = root.parent;
        return parent.left == root;
    }

    private Node insert(Node parent, Node root, int data) {
        if (root == null || root.isNullLeaf) {
            //if parent is not null means tree is not empty
            //so create a red leaf node
            if (parent != null) {
                return createRedNode(parent, data);
            } else { //otherwise create a black root node if tree is empty
                return createBlackNode(data);
            }
        }

        //duplicate insertion is not allowed for this tree.
        if (root.data == data) {
            throw new IllegalArgumentException("Duplicate date " + data);
        }
        //if we go on left side then isLeft will be true
        //if we go on right side then isLeft will be false.
        boolean isLeft;
        if (root.data > data) {
            Node left = insert(root, root.left, data);
            //if left becomes root parent means rotation
            //happened at lower level. So just return left
            //so that nodes at upper level can set their
            //child correctly
            if (left == root.parent) {
                return left;
            }
            //set the left child returned to be left of root node
            root.left = left;
            //set isLeft to be true
            isLeft = true;
        } else {
            Node right = insert(root, root.right, data);
            //if right becomes root parent means rotation
            //happened at lower level. So just return right
            //so that nodes at upper level can set their
            //child correctly
            if (right == root.parent) {
                return right;
            }
            //set the right child returned to be right of root node
            root.right = right;
            //set isRight to be true
            isLeft = false;
        }

        if (isLeft) {
            //if we went to left side check to see Red-Red conflict
            //between root and its left child
            if (root.color == Color.RED && root.left.color == Color.RED) {
                //get the sibling of root. It is returning optional means
                //sibling could be empty
                Optional<Node> sibling = findSiblingNode(root);
                //if sibling is empty or of BLACK color
                if (sibling.isEmpty() || sibling.get().color == Color.BLACK) {
                    //check if root is left child of its parent
                    if (isLeftChild(root)) {
                        //this creates left left situation. So do one right rotate
                        rightRotate(root, true);
                    } else {
                        //this creates left-right situation so do one right rotate followed
                        //by left rotate

                        //do right rotation without change in color. So sending false.
                        //when right rotation is done root becomes right child of its left
                        //child. So make root = root.parent because its left child before rotation
                        //is new root of this subtree.
                        rightRotate(root.left, false);
                        //after rotation root should be root's parent
                        root = root.parent;
                        //then do left rotate with change of color
                        leftRotate(root, true);
                    }

                } else {
                    //we have sibling color as RED. So change color of root
                    //and its sibling to Black. And then change color of their
                    //parent to red if their parent is not a root.
                    root.color = Color.BLACK;
                    sibling.get().color = Color.BLACK;
                    //if parent's parent is not null means parent is not root.
                    //so change its color to RED.
                    if (root.parent.parent != null) {
                        root.parent.color = Color.RED;
                    }
                }
            }

        } else {
            //this is mirror case of above. So same comments as above.
            if (root.color == Color.RED && root.right.color == Color.RED) {
                Optional<Node> sibling = findSiblingNode(root);
                if (!sibling.isPresent() || sibling.get().color == Color.BLACK) {
                    if (!isLeftChild(root)) {
                        leftRotate(root, true);
                    } else {
                        leftRotate(root.right, false);
                        root = root.parent;
                        rightRotate(root, true);
                    }
                } else {
                    root.color = Color.BLACK;
                    sibling.get().color = Color.BLACK;
                    if (root.parent.parent != null) {
                        root.parent.color = Color.RED;
                    }

                }

            }

        }

        return root;
    }

    /**
     * Using atomicreference because java does not provide mutable wrapper. Its like
     * double pointer in C.
     */
    private void delete(Node root, int data, AtomicReference<Node> rootReference) {
        if (root == null || root.isNullLeaf) {
            return;
        }
        if (root.data == data) {
            //if node to be deleted has 0 or 1 null children then we have
            //deleteOneChild use case as discussed in video.
            if (root.right.isNullLeaf || root.left.isNullLeaf) {
                deleteOneChild(root, rootReference);
            } else {
                //otherwise look for the inorder successor in right subtree.
                //replace inorder successor data at root data.
                //then delete inorder successor which should have 0 or 1 not null child.
                Node inorderSuccessor = findSmallest(root.right);
                root.data = inorderSuccessor.data;
                delete(root.right, inorderSuccessor.data, rootReference);
            }
        }
        //search for the node to be deleted.
        if (root.data < data) {
            delete(root.right, data, rootReference);
        } else {
            delete(root.left, data, rootReference);
        }
    }

    private Node findSmallest(Node root) {
        Node prev = null;
        while (root != null && !root.isNullLeaf) {
            prev = root;
            root = root.left;
        }
        return prev != null ? prev : root;
    }

    /**
     * Assumption that node to be deleted has either 0 or 1 non leaf child
     */
    private void deleteOneChild(Node nodeToBeDelete, AtomicReference<Node> rootReference) {
        Node child = nodeToBeDelete.right.isNullLeaf ? nodeToBeDelete.left : nodeToBeDelete.right;
        //replace node with either one not null child if it exists or null child.
        replaceNode(nodeToBeDelete, child, rootReference);
        //if the node to be deleted is BLACK. See if it has one red child.
        if (nodeToBeDelete.color == Color.BLACK) {
            //if it has one red child then change color of that child to be Black.
            if (child.color == Color.RED) {
                child.color = Color.BLACK;
            } else {
                //otherwise we have double black situation.
                deleteCase1(child, rootReference);
            }
        }
    }


    /**
     * If double black node becomes root then we are done. Turning it into
     * single black node just reduces one black in every path.
     */
    private void deleteCase1(Node doubleBlackNode, AtomicReference<Node> rootReference) {
        if (doubleBlackNode.parent == null) {
            rootReference.set(doubleBlackNode);
            return;
        }
        deleteCase2(doubleBlackNode, rootReference);
    }

    /**
     * If sibling is red and parent and sibling's children are black then rotate it
     * so that sibling becomes black. Double black node is still double black so we need
     * further processing.
     */
    private void deleteCase2(Node doubleBlackNode, AtomicReference<Node> rootReference) {
        Node siblingNode = findSiblingNode(doubleBlackNode).get();
        if (siblingNode.color == Color.RED) {
            if (isLeftChild(siblingNode)) {
                rightRotate(siblingNode, true);
            } else {
                leftRotate(siblingNode, true);
            }
            if (siblingNode.parent == null) {
                rootReference.set(siblingNode);
            }
        }
        deleteCase3(doubleBlackNode, rootReference);
    }

    /**
     * If sibling, sibling's children and parent are all black then turn sibling into red.
     * This reduces black node for both the paths from parent. Now parent is new double black
     * node which needs further processing by going back to case1.
     */
    private void deleteCase3(Node doubleBlackNode, AtomicReference<Node> rootReference) {

        Node siblingNode = findSiblingNode(doubleBlackNode).get();

        if (doubleBlackNode.parent.color == Color.BLACK && siblingNode.color == Color.BLACK && siblingNode.left.color == Color.BLACK
                && siblingNode.right.color == Color.BLACK) {
            siblingNode.color = Color.RED;
            deleteCase1(doubleBlackNode.parent, rootReference);
        } else {
            deleteCase4(doubleBlackNode, rootReference);
        }
    }

    /**
     * If sibling color is black, parent color is red and sibling's children color is black then swap color b/w sibling
     * and parent. This increases one black node on double black node path but does not affect black node count on
     * sibling path. We are done if we hit this situation.
     */
    private void deleteCase4(Node doubleBlackNode, AtomicReference<Node> rootReference) {
        Node siblingNode = findSiblingNode(doubleBlackNode).get();
        if (doubleBlackNode.parent.color == Color.RED && siblingNode.color == Color.BLACK && siblingNode.left.color == Color.BLACK
                && siblingNode.right.color == Color.BLACK) {
            siblingNode.color = Color.RED;
            doubleBlackNode.parent.color = Color.BLACK;
            return;
        } else {
            deleteCase5(doubleBlackNode, rootReference);
        }
    }

    /**
     * If sibling is black, double black node is left child of its parent, siblings right child is black
     * and sibling's left child is red then do a right rotation at siblings left child and swap colors.
     * This converts it to delete case6. It will also have a mirror case.
     */
    private void deleteCase5(Node doubleBlackNode, AtomicReference<Node> rootReference) {
        Node siblingNode = findSiblingNode(doubleBlackNode).get();
        if (siblingNode.color == Color.BLACK) {
            if (isLeftChild(doubleBlackNode) && siblingNode.right.color == Color.BLACK && siblingNode.left.color == Color.RED) {
                rightRotate(siblingNode.left, true);
            } else if (!isLeftChild(doubleBlackNode) && siblingNode.left.color == Color.BLACK && siblingNode.right.color == Color.RED) {
                leftRotate(siblingNode.right, true);
            }
        }
        deleteCase6(doubleBlackNode, rootReference);
    }

    /**
     * If sibling is black, double black node is left child of its parent, sibling left child is black and sibling's right child is
     * red, sibling takes its parent color, parent color becomes black, sibling's right child becomes black and then do
     * left rotation at sibling without any further change in color. This removes double black and we are done. This
     * also has a mirror condition.
     */
    private void deleteCase6(Node doubleBlackNode, AtomicReference<Node> rootReference) {
        Node siblingNode = findSiblingNode(doubleBlackNode).get();
        siblingNode.color = siblingNode.parent.color;
        siblingNode.parent.color = Color.BLACK;
        if (isLeftChild(doubleBlackNode)) {
            siblingNode.right.color = Color.BLACK;
            leftRotate(siblingNode, false);
        } else {
            siblingNode.left.color = Color.BLACK;
            rightRotate(siblingNode, false);
        }
        if (siblingNode.parent == null) {
            rootReference.set(siblingNode);
        }
    }

    private void replaceNode(Node root, Node child, AtomicReference<Node> rootReference) {
        child.parent = root.parent;
        if (root.parent == null) {
            rootReference.set(child);
        } else {
            if (isLeftChild(root)) {
                root.parent.left = child;
            } else {
                root.parent.right = child;
            }
        }
    }

    private void printRedBlackTree(Node root, int space) {
        if (root == null || root.isNullLeaf) {
            return;
        }
        printRedBlackTree(root.right, space + 5);
        for (int i = 0; i < space; i++) {
            System.out.print(" ");
        }
        System.out.println(root.data + " " + (root.color == Color.BLACK ? "B" : "R"));
        printRedBlackTree(root.left, space + 5);
    }

    private boolean noRedRedParentChild(Node root, Color parentColor) {
        if (root == null) {
            return true;
        }
        if (root.color == Color.RED && parentColor == Color.RED) {
            return false;
        }

        return noRedRedParentChild(root.left, root.color) && noRedRedParentChild(root.right, root.color);
    }

    private boolean checkBlackNodesCount(Node root, AtomicInteger blackCount, int currentCount) {

        if (root.color == Color.BLACK) {
            currentCount++;
        }

        if (root.left == null && root.right == null) {
            if (blackCount.get() == 0) {
                blackCount.set(currentCount);
                return true;
            } else {
                return currentCount == blackCount.get();
            }
        }
        return checkBlackNodesCount(root.left, blackCount, currentCount) && checkBlackNodesCount(root.right, blackCount, currentCount);
    }

    public static void main(String[] args) {
        Node root = null;
        RedBlackTree redBlackTree = new RedBlackTree();

        root = redBlackTree.insert(root, 10);
        root = redBlackTree.insert(root, 15);
        root = redBlackTree.insert(root, -10);
        root = redBlackTree.insert(root, 20);
        root = redBlackTree.insert(root, 30);
        root = redBlackTree.insert(root, 40);
        root = redBlackTree.insert(root, 50);
        root = redBlackTree.insert(root, -15);
        root = redBlackTree.insert(root, 25);
        root = redBlackTree.insert(root, 17);
        root = redBlackTree.insert(root, 21);
        root = redBlackTree.insert(root, 24);
        root = redBlackTree.insert(root, 28);
        root = redBlackTree.insert(root, 34);
        root = redBlackTree.insert(root, 32);
        root = redBlackTree.insert(root, 26);
        root = redBlackTree.insert(root, 35);
        root = redBlackTree.insert(root, 19);
        redBlackTree.printRedBlackTree(root);

        root = redBlackTree.delete(root, 50);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 40);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, -10);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 15);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 17);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 24);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 21);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 32);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 26);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 19);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 25);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 17);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, -15);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 20);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 35);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 34);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 30);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 28);
        System.out.println(redBlackTree.validateRedBlackTree(root));
        root = redBlackTree.delete(root, 10);
        System.out.println(redBlackTree.validateRedBlackTree(root));
    }
}

Answer 6

Perhaps it is worth starting with left-leaning red black trees. They offer an interesting simplified implementation.

Answer 7

you really make good conclusion that three cases.

after insertion in RB-Tree, there left a main problem to solve if there is. there two continuous red nodes!! how could we make that two continuous red nodes disappear without violate that rule (every path have same count black node) so we see the two node, there only exists 3 circurm...

I am sorry, you could see the text book of Instruction to Algorithms

no body can help you think through rb-tree. they can only guide you at some key point.