Bst tree delete () method doesn't work

I am currently implementing a binary search tree and I am wondering why my delete () method is not working ... My findMin () method is working, I have tested it so far. I enter a key that doesn't exist in three and I get the correct exception, but whenever I type in a key that does exist, it just doesn't remove the node from three ... So here's my code:

import java.util.NoSuchElementException;

public class Bst {

Node root;
Node head;
Node tail;


public Bst(){
    root = null;
}

public void insert (Node root, int key){
    Node newNode=new Node(key);

    if(root==null){
        root=newNode;
    }

    if(key<=root.getKey()){
        if (root.getLeft()!=null){
            insert(root.getLeft(), key);
        }
        else{
            root.setLeft(newNode);
        }
    }

    if (key>=root.getKey()){
        if (root.getRight()!=null){
            insert(root.getRight(),key);
        }

        else{
            root.setRight(newNode);
        }

    }


    }

public void printTree(Node root){
    if (root==null) return;
    printTree(root.getLeft());
    System.out.print(root.getKey() + " ");
    printTree(root.getRight());
}

public Node treeToCDLL(Node root){
    if (root == null){
        return null;
    }

    Node leftTree=treeToCDLL(root.getLeft());
    Node rightTree=treeToCDLL(root.getRight());


    if (leftTree == null){
        head=root;
    }

    else {
        head=leftTree;
        leftTree.getLeft().setRight(root);
        root.setLeft(leftTree.getLeft());
    }

    if (rightTree==null){
        head.setLeft(root);
        root.setRight(head);
        tail=root;
    }

    else{
        tail=rightTree.getLeft();
        head.setLeft(tail);
        tail.setRight(head);
        root.setRight(rightTree);
        rightTree.setLeft(root);
    }

    return head;
}

public boolean find(Node root, int key){
    Node current=root;

    while(current!=null){

        if(current.getKey()==key){
            return true;
        }
        else if(current.getKey()>key){
            current=current.getLeft();
        }

        else
            current=current.getRight();
        }
    return false;
}

public void printList(Node head){
    Node current = head;

    while(current!=null){
        System.out.print(current.getKey() + " ");
        current=current.getRight();
        if(current==head) break;
    }
}

public Node findMin(Node root){
    Node current=root;
    if(root==null) return null;
    else{
    if(current.getLeft()!=null){
        return findMin(current.getLeft());
    }
    }
    return current;

}

public void delete(Node root, int key){
    Node current=root;

    if(root==null){
        throw new NoSuchElementException("baum ist leer");
    }

    else{
        if(current.getKey()>key){
            delete(current.getLeft(), key);
        }

        else if(current.getKey()<key){
            delete(current.getRight(),key);
        }

        else{
            if(current.getLeft()==null && root.getRight()==null){
                current=null;
            }

            else if(current.getLeft()==null){
                Node tmp=current;
                current=current.getRight();
                tmp=null;
            }

            else if(current.getRight()==null){
                Node tmp=current;
                current=current.getLeft();
                tmp=null;
            }

            else {
                Node min=findMin(current.getRight());
                Node tmp=current;
                current=min;
                tmp=null;

            }
        }
    }
}
public static void main (String[]args){

    Bst bst=new Bst();

    Node root=new Node(4);
    bst.insert(root, 2);
    bst.insert(root, 10);
    bst.insert(root, 3);
    bst.insert(root, 5);
    bst.insert(root, 6);
    bst.insert(root, 0);

    bst.delete(root, 2);

    System.out.print("in-order traversal: ");
    bst.printTree(root);
    System.out.println();
    System.out.print("Der gesuchte Knoten : " + bst.find(root,7));
    System.out.println();
    System.out.print("der kleinste Knoten : " + bst.findMin(root));
    System.out.println();



    System.out.print("circular doubly linked list: ");
    Node head= bst.treeToCDLL(root);
    bst.printList(head);







}

}

      

Node class:

public class Node {

    private Node left;
    private Node right;
    private int key;

    public Node(int key){
        this.key=key;
        left = null;
        right = null;
    }

    public void setLeft(Node left){
        this.left=left;
    }

    public Node getLeft(){
        return left;
    }

    public void setRight(Node right){
        this.right=right;
    }

    public Node getRight(){
        return right;
    }

    public int getKey(){
        return key;
    }

}

      

I would be glad if someone could help me ... I tried to find a solution all day, but it looks like I won't find it on my own

+3


source to share


2 answers


Here, by doing this current = min you are not changing the node in the tree, but simply replacing the local pointer (the current one). Either rewrite the values โ€‹โ€‹of this node with setters, get getLeft updates for the parent node.



 else {
     Node min=findMin(current.getRight());
     Node tmp=current;
     current=min;
     tmp=null;
 }

      

0


source


In the last part of the method, delete()

you are just simply assigning values null

, which does not mean that references point to a value null

.

For example, when the matched node is a leaf node, you just assign the value to the null

variable current

. You have to assign a value null

to left

/ right

parent element current

. Assuming that parent

is the parent node of current

node.

 if(current.getLeft()==null && root.getRight()==null){
            if(current == parent.getLeft()) {
                 parent.left=null;
            } else {
                 parent.right == null;
            }
  }

      



This is the same problem with other subsequent blocks else

.

        else if(current.getLeft()==null){
            if(current == parent.left) {
                 parent.left= current.getRight();
            } else {
                 parent.right = current.getRight();
            }
        }

        else if(current.getRight()==null){
            if(current == parent.left) {
                 parent.left= current.getLeft();
            } else {
                 parent.right = current.getLeft();
            }
        }

      

You need to keep track of the parent node while traversing the tree.

0


source







All Articles