CODEWITHSUNDEEP
java
Berzerker
Berzerker

Reputation: 155

java Delete a Binary Tree node containing two children

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;

Upvotes: 1

Views: 2321

Answers (2)

preetham tk
preetham tk

Reputation: 13

I have given the code for deletion of a node in a BST which would work for any condition and that too using a for loop. 

public void delete(int key) {

    Node<E> temp = find(key);
    System.out.println(temp.key);

    for (;;) {
        // case 1 : external node
        if (temp.isExternal()) {
            if (temp.getParent().getrChild() == temp) {
                temp.parent.rightchild = null;
                temp = null;
            } else {

                temp = null;
            }
            break;

        }

        // case2 : one child is null
        else if ((temp.getlChild() == null) || (temp.getrChild() == null)) {
            if ((temp.parent.leftchild != null) && temp.getParent().getlChild().key == temp.key) {
                if (temp.getlChild() == null) {
                    temp.getParent().setLeft(temp.getrChild());
                    temp.getrChild().setParent(temp.getParent());
                    break;

                }

                else
                    temp.getParent().setLeft(temp.getlChild());
                temp.getlChild().setParent(temp.getParent());
            }

            else {
                if (temp.rightchild != null) {
                    System.out.println("in");
                    temp.getParent().setRight(temp.getrChild());

                    temp.getrChild().setParent(temp.getParent());
                    break;

                }

                else
                    temp.getParent().setRight(temp.getlChild());
                temp.getlChild().setParent(temp.getParent());
            }

            break;
        }
        // case 3 : has both the children
        else {
            int t = temp.key;
            temp.key = temp.getlChild().key;
            temp.getlChild().key = t;
            temp = temp.getlChild();

            continue;
        }
    }

}

Upvotes: 0

LtWorf
LtWorf

Reputation: 7608

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.

Upvotes: 1

Related Questions