Red Black Tree Top-Down Deletion Algorithm

Question

I am implementing a Red Black Tree with insert, search and delete functions in O (log n) time. Insert and search are working fine. However I am stuck on delete. I found this ppt slide on the internet which shows the algorithm of RBT deletion: http://www.slideshare.net/piotrszymanski/red-black-trees#btnNext on page 56 onwards. I know I am asking a bit too much but I have been stuck on this for over 2 weeks and I can't find the problem. The way I'm understanding Top-Down deletion that you have to rotate and recolor nodes accordingly until you find the predecessor of the node to be deleted. When you do find this node - which would be either a leaf or a node with one right child, replace node to be deleted data by the data of this node and delete this node like normal BST deletion, right?

This is the code I did, based on what I learnt from that slide. If anyone would be so kind to go over it, I would be more than grateful! Or at least if you think there's a better algorithm than what I'm using, please tell me!

 public void delete(int element){

    if (root == null){ 
        System.out.println("Red Black Tree is Empty!");

    } else {

      Node X = root; 
      parent = null; 
      grandParent = null; 
      sibling = null; 

      if (isLeaf(X)){

          if (X.getElement() == element){
              emptyRBT();
          } 

      } else {

      if (checkIfBlack(root.getLeftChild()) && checkIfBlack(root.getRightChild())){
          root.setIsBlack(false);

          if (X.getElement() > element && X.getLeftChild() != null){ 
              X = moveLeft(X);

          } else if (X.getElement() < element && X.getRightChild() != null){
              X = moveRight(X);
          } 

          Step2(X, element);

      } else { 

          Step2B(X, element);

       } 
     }
   } 
   root.setIsBlack(true);
}

public void Step2(Node X, int element)
{
    int dir = -1;

    while (!isLeaf(X)){

      if (predecessor == null){  // still didn't find Node to delete

        if (X.getElement() > element && X.getLeftChild() != null){
            X = moveLeft(X);
            dir = 0;
        } else if (X.getElement() < element && X.getRightChild() != null){
            X = moveRight(X);
            dir = 1;
        } else if (X.getElement() == element){
            toDelete = X;
            predecessor = inorderPredecessor(X.getRightChild());
            X = moveRight(X);
        }

      } else { // if node to delete is already found and X is equal to right node of to delete
               // move always to the left until you find predecessor

          if (X != predecessor){
              X = moveLeft(X);
              dir = 0;
          } 
      }

      if (!isLeaf(X)){
        if (!hasOneNullNode(X)){

         if (checkIfBlack(X.getLeftChild()) && checkIfBlack(X.getRightChild())){
             Step2A(X, element, dir);
         } else {
             Step2B(X, element);
         }
       }
     }
   }

   removeNode(X);

   if (predecessor != null){
       toDelete.setElement(X.getElement());
   }
}

public Node Step2A(Node X, int element, int dir) {

    if (checkIfBlack(sibling.getLeftChild()) && checkIfBlack(sibling.getRightChild())) {
        X = Step2A1(X);

    } else if ((checkIfBlack(sibling.getLeftChild()) == false) && checkIfBlack(sibling.getRightChild())) {
        X = Step2A2(X);

    } else if ((checkIfBlack(sibling.getLeftChild()) && (checkIfBlack(sibling.getRightChild()) == false))) {
        X = Step2A3(X);

    } else if ((checkIfBlack(sibling.getLeftChild()) == false) && (checkIfBlack(sibling.getRightChild()) == false)) {
        X = Step2A3(X);
    }

    return X;
}

public Node Step2A1(Node X) {

    X.setIsBlack(!X.IsBlack());
    parent.setIsBlack(!parent.IsBlack());
    sibling.setIsBlack(!sibling.IsBlack());

    return X;
}

public Node Step2A2(Node X) {

    if (parent.getLeftChild() == sibling){
        LeftRightRotation(sibling.getLeftChild(), sibling, parent);

    } else RightLeftRotation(sibling.getRightChild(), sibling, parent);

    X.setIsBlack(!X.IsBlack());
    parent.setIsBlack(!parent.IsBlack());

    return X;
}

public Node Step2A3(Node X) {

    if (parent.getLeftChild() == sibling){
        leftRotate(sibling);
    } else if (parent.getRightChild() == sibling){
        rightRotate(sibling);  
    }

    X.setIsBlack(!X.IsBlack());
    parent.setIsBlack(!parent.IsBlack());
    sibling.setIsBlack(!sibling.IsBlack());
    sibling.getRightChild().setIsBlack(!sibling.getRightChild().IsBlack());

    return X;
}

public void Step2B(Node X, int element){

    if (predecessor == null){
        if (X.getElement() > element && X.getLeftChild() != null){
            X = moveLeft(X);
        } else if (X.getElement() < element && X.getRightChild() != null){
            X = moveRight(X);
        } else if (X.getElement() == element){
            Step2(X, element);
        }

    } else {

        if (X != predecessor)
            X = moveLeft(X);
        else Step2(X, element);
    }

    if (X.IsBlack()){

       if (parent.getLeftChild() == sibling){
           leftRotate(sibling);
       } else if (parent.getRightChild() == sibling){
           rightRotate(sibling);
       }

       parent.setIsBlack(!parent.IsBlack());
       sibling.setIsBlack(!sibling.IsBlack()); 

       Step2(X, element);

    } else {
        Step2B(X, element);
    }
}

public void removeNode(Node X) {

    if (isLeaf(X)) {
        adjustParentPointer(null, X);
        count--;

    } else if (X.getLeftChild() != null && X.getRightChild() == null) {
        adjustParentPointer(X.getLeftChild(), X);
        count--;

    } else if (X.getRightChild() != null && X.getLeftChild() == null) {
        adjustParentPointer(X.getRightChild(), X);
        count--;
    } 
}

public Node inorderPredecessor(Node node){

   while (node.getLeftChild() != null){
       node = node.getLeftChild();
   }

   return node;
}

public void adjustParentPointer(Node node, Node current) {

    if (parent != null) {

        if (parent.getElement() < current.getElement()) {
            parent.setRightChild(node);
        } else if (parent.getElement() > current.getElement()) {
            parent.setLeftChild(node);
        }
    } else {
        root = node;
    }
}

public boolean checkIfBlack(Node n){
    if (n == null || n.IsBlack() == true){
        return true;
    } else return false;
}

public Node leftRotate(Node n)
{  
    parent.setLeftChild(n.getRightChild());
    n.setRightChild(parent);

    Node gp = grandParent;

    if (gp != null){

        if (gp.getElement() > n.getElement()){
            gp.setLeftChild(n);
        } else if (gp.getElement() < n.getElement()){
            gp.setRightChild(n);
        }

    } else root = n;

    return n;
}

public Node rightRotate(Node n)
{  
    parent.setRightChild(n.getLeftChild());
    n.setLeftChild(parent);

    Node gp = grandParent;

    if (gp != null){

        if (gp.getElement() > n.getElement()){
            gp.setLeftChild(n);
        } else if (gp.getElement() < n.getElement()){
            gp.setRightChild(n);
        }

    } else root = n;

    return n;
}

The node is being deleted, but the tree after deletion would be black violated, which is very wrong.

Answer 1

The eternally confuzzled blog has top-down implementations of both insert and delete for red-black trees. It also goes through case-by-case why it works. I won't replicate it here (it's rather lengthy).

I've used that blog as a reference for implementing red-black trees in both c++ and java. As I discussed in an earlier answer, I found the implementation to be faster than std::map's bottom-up implementation of red-black trees (whatever STL came with gcc at the time).

Here's an untested, direct translation of the code to Java. I would highly suggest you test it and morph it to match your style.

private final static int LEFT = 0;
private final static int RIGHT = 1;

private static class Node {
    private Node left,right;
    private boolean red;
    ...

    // any non-zero argument returns right
    Node link(int direction) {
        return (direction == LEFT) ? this.left : this.right;
    }
    // any non-zero argument sets right
    Node setLink(int direction, Node n) {
        if (direction == LEFT) this.left = n;
        else this.right = n;
        return n;
    }
}

boolean remove(int data) {
  if ( this.root != null ) {
    final Node head = new Node(-1, null, null); /* False tree root */
    Node cur, parent, grandpa; /* Helpers */
    Node found = null;  /* Found item */
    int dir = RIGHT;

    /* Set up helpers */
    cur = head;
    grandpa = parent = null;
    cur.setLink(RIGHT, this.root);

    /* Search and push a red down */
    while ( cur.link(dir) != null ) {
      int last = dir;

      /* Update helpers */
      grandpa = parent, parent = cur;
      cur = cur.link(dir);
      dir = cur.data < data ? RIGHT : LEFT;

      /* Save found node */
      if ( cur.data == data )
        found = cur;

      /* Push the red node down */
      if ( !is_red(cur) && !is_red(cur.link(dir)) ) {
        if ( is_red(cur.link(~dir)) )
          parent = parent.setLink(last, singleRotate(cur, dir));
        else if ( !is_red(cur.link(~dir)) ) {
          Node s = parent.link(~last);

          if ( s != null ) {
            if (!is_red(s.link(~last)) && !is_red(s.link(last))) {
              /* Color flip */
              parent.red = false;
              s.red = true;
              cur.red = true;
            }
            else {
              int dir2 = grandpa.link(RIGHT) == parent ? RIGHT : LEFT;

              if ( is_red(s.link(last)) )
                grandpa.setLink(dir2, doubleRotate(parent, last));
              else if ( is_red(s.link(~last)) )
                grandpa.setLink(dir2, singleRotate(parent, last));

              /* Ensure correct coloring */
              cur.red = grandpa.link(dir2).red = true;
              grandpa.link(dir2).link(LEFT).red = false;
              grandpa.link(dir2).link(RIGHT).red = false;
            }
          }
        }
      }
    }

    /* Replace and remove if found */
    if ( found != null ) {
      found.data = cur.data;
      parent.setLink(
        parent.link(RIGHT) == cur ? RIGHT : LEFT,
        cur.link(cur.link(LEFT) == null ? RIGHT : LEFT));
    }

    /* Update root and make it black */
    this.root = head.link(RIGHT);
    if ( this.root != null )
      this.root.red = false;
  }

  return true;
}

Answer 2

quick link : http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html

--> Caution : the code on the site is relying on two jars. In the datastructures however the dependency might be minimal. Sometimes it's enough to comment out the main method (that only serves as a test client) If not : the jars are downloadable on the same site.

If you are looking for two weeks and studying algoritms, chances are you know about

http://algs4.cs.princeton.edu/

the website that is accompanying the famous

Algorithms, by Robert Sedgewick and Kevin Wayne

book.

On this website, there is this implementation of a red black (balances) tree :

http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html

I didnot look into it yet (I will later on this year) , but I fully trust it to be a working implementation of a RBTree.

Some sidenote that might be interesting for visitors of this topic: MIT placed excellent courses concerning algoritms online. The one concerning rbtrees is http://www.youtube.com/watch?v=iumaOUqoSCk