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