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);
}
publi