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…

Accepted Answer

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;
}
```

Red Black Tree Top-Down Deletion Algorithm

Solution

Problem

Related problems