Berzerker - 5 months ago 31

Java Question

This is the last case where the node to be deleted has two children. I cant figure out what I am doing wrong . Please help.

`//BTNode has two children`

else if (u.getLeft() != null && u.getRight() != null){

//if node to delete is root

BTNode<MyEntry<K,V>> pred = u.getRight();

while (pred.getLeft().element() != null){

pred = pred.getLeft();

}

BTNode<MyEntry<K,V>> predParent = pred.getParent();

if (!hasRightChild(pred)){

predParent.setLeft(new BTNode<MyEntry<K,V>>(null,predParent,null,null));}

if (hasRightChild(pred)){

BTNode<MyEntry<K,V>> predChild = pred.getRight();

predParent.setLeft(predChild);

predChild.setParent(predParent);

}

return returnValue;

ok so modify it like this ??

`u.setElement(succ.element());`

BTNode<MyEntry<K,V>> succParent = succ.getParent();

if (!hasLeftChild(succ)){

succParent.setRight(new BTNode<MyEntry<K,V>>(null,succParent,null,null));}

if (hasLeftChild(succ)){

BTNode<MyEntry<K,V>> predChild = succ.getLeft();

succParent.setRight(predChild);

predChild.setParent(succParent);

}

return returnValue;

Answer

From wikipedia:

Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

So, take for example the left children, and then find the rightmost leaf in that subtree, then replace the information of the node to delete with that of the leaf, and then delete that leaf easily.

You might want to create a function that returns the rightmost leaf from a subtree.