RedBlack BST: New Type Art

Talks about Deletion of Left-leaning RedBlack Binary Search Tree.

Preface

These days I was focusing on reimplementing the dissertation of RedBlack BST [“A Dichromatic Framework for Balanced Trees”, Guibas & Robert Sedgewick, 1972], an equivalent-representation of 2-3 Trees but more elegant.

To be honest, I was totally captivated by its beautiful representation and exactly powerful and elegant implementation.

However, unfortunately, the material I referenced is just like an abstract, and It is actually lack of expositions and code comments, especially for the deletion part of RedBlack Tree, which is almost based on Hibbard deletion. Moreover, It seems that there are not adequate posts to try demonstrating this crucial problem, they just stated that “It is almost likely with Hibbard deletion”. Thus, as for me, a novice and actually noob freshman of Algorithms, I wanna talk about this crucial problem (by JAVA) and attempt to explain it today.

RedBlack Tree Review

Recall that there are many basic operations of Left-Leaning RedBlack BST( a.k.a. LLRB BST ), I consider you should grasp them before reading this post.

I recommand you to review this part by this lecture. You should understand the following concepts and API which is about Insertion Ops of LLRB:

Basic Operations

• rotateLeft(Node)
• rotateRight(Node)
• flipColors(Node)

Insertion

• put(Node, Key, Value)

Deletion

Firstly, as I have said before, the deletion of RedBlack BST is similar with Hibbard deletion of BST. But in order to maintain RedBlack BST’s invariant, We would modify Hibbard deletion by some basic API, and protect its self-balance based on some properties of LLRB BST.

Basic API

moveRed Operations

When we use Hibbard deletion in RedBlack BST, we are always concerned about how to avoid Over-leaning. In the disseration, Sedgewick and Guibas propose that self-balance could be maintained in Hibbard deletion by utilizing moveRed API to check prerequisites before deletion.

As same as other basic operations, we would also do moveRed() recursively. Thus we assume target Node as h, and introduce operations in the following.

moveRedLeft(Node)

Iff h is red, h.left and h.left.left are black $\implies$ Make h.left or one of its children red.

The modifications are just like following figure [invoke from LLRB]:

Implementation

private Node moveRedLeft(Node h)
{
    assert(h != null);
    assert(isRed(h) && !isRed(h.left) && !isRed(h.left.left));
    flipColors(h);

    if(isRed(h.right.left))
    {
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
        flipColors(h);
    }
    return h;
}

moveRedRight(Node)

Iff h is red, h.right and h.right.left are black $\implies$ Make h.right or one of its children red.

Implementation

private Node moveRedRight(Node h) 
{
    assert(h != null);
    assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);

    flipColors(h);
    if(isRed(h.left.left))
    {
        h = rotateRight(h);
        flipColors(h);
    }
    return h;
}

Balance Operation

Balance Operation is a basic operation which is also involved in insertion part. As a summary, it could be inducted as 3 basic rules:

• iff h.right is red $\implies$ rotateLeft.
• iff both h.left and h.left.left are red $\implies$ rotateRight.
• iff both h.left and h.right are red $\implies$ flipColors.

Implementation

private Node balance(Node h) {
    assert(h != null);

    if(isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
    if(isRed(h.left) && isRed(h.left.left))     h = rotateRight(h);
    if(isRed(h.left) && isRed(h.right))     flipColors(h);
    h.size = size(h.left) + size(h.right) + 1;
    return h;
}

Deletion of LLRB BST

Before talk about the deletion of LLRB, we should firstly acknowledge an essential but always ignorable property of LLRB BST(Easy Proved):

• iff h.left is black, h.right does not exist (is null) $\implies$ h is a leaf.

HINT: You could prove it by induction or Graph Theory easily.

Basic Operations

The basic operations in this part is a recursive operation called deleteMin(Node), it is almost similar with Hibbard deletion besides RedBlack-balance. Thus I would mainly talk about how it maintained RedBlack-Balance in this part.

Recall what we talked at moveRed part, we maintain self-balance of LLRB i deletion by Beforehand Check, and then depend on basic balance() to maintain invariant after deletion operation.

(I am such a lazy guy thus it is no figure here XD.)

Implementation

private Node deleteMin(Node h)
{
    if(h.left == null)
    {
        if(h.right == null)
            return null;
        else 
            return h.right;
    }

    //Beforehand Check & Recursive moveRed ops
    if(!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h);
    h.left = deleteMin(h.left);
    return balance(h);
}

The other basic operation in deletion is min(Node) API, it is so regular that I would directly provide implementation here.

Implementation of min API

private Node min(Node h) 
{
    if(h.left == null) return h;
    return min(h.left);
}

Hibbard Deletion for LLRB BST

Finally, we touch down to figure out LLRB BST’s deletion.

As you would see, it is really similar with Hibbard deletion except Color-check. Recall before chapters which mainly talks about Color-check, I consider it would be ease to understand this self-balance modified Hibbard deletion for LLRB BST.

Implementation

private Node delete(Node h, Key key) {
    assert(get(h, key) != null);

    if(key.compareTo(h.key) < 0) {
        if(!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
        h.left = delete(h.left, key);
    }
    else {
        if(isRed(h.left))
            h = rotateRight(h);

        /***************************************************
         * 
         *  Property: 
         *      Assume a Node h;
         *      iff h is a leaf, h.left.color == BLACK 
         *                         && h.right == null; 
         * 
         ***************************************************/ 
        if(key.compareTo(h.key) == 0 && (h.right == null))
            return null;
        if(!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h);
        if(key.compareTo(h.key) == 0) {
            Node x = min(h.right);
            h.key = x.key;
            h.value = x.value;
            h.right = deleteMin(h.right);
        }
        else h.right = delete(h.right, key);
    }
    return balance(h);

}

One More Thing

As an apple guy, it is crucial to say one more thing( LMAO ).

The whole basic API and Code comments of LLRB BST is Here. Welcom to check it in my GitHub Repository.

Thanks for your reading, Take care and Keep learning.