Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel