10

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.

5

2 Answers 2

5
+50

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;
}
4
  • Thanks a lot @Michael .. you helped a lot! tested it and made a few changes so that I understand it more my way and it works perfectly! don't know what was wrong with the piece of code I submitted here. Sometimes it's really a small thing and you it takes such a long time to see the error even through debugging! Thanks again. Voted up, awarded bounty and set as answer ;)
    – Bernice
    Jan 10, 2013 at 17:23
  • Yeah, I don't really like the style when translated directly to java like this. The boolean->int thing is jarring and I don't like all the nested ifs. Jan 10, 2013 at 17:56
  • Anyway, I'm glad it's helpful. Jan 10, 2013 at 17:57
  • yeah me neither it's really confusing sometimes! the nested ifs make it seem more difficult then it actually is, though shorter!
    – Bernice
    Jan 10, 2013 at 18:14
1

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

1
  • Thanks for your answer Peter. I am already familiar with the sites you gave me, even the MIT lecture. However, these are all bottom-up implementations and I need to understand the top-down implementation since I did the insert function in this manner and also because I am more familiar with top-down thinking.. I have looked all over the internet for a better algorithm than the one I posted the link for in my question but it seems bottom-up is more popular! Do you think my explanation is good? I really can't see what's wrong with the code.. even with debugging :/
    – Bernice
    Jan 2, 2013 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.