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
source to share
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;
}
source to share
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.
source to share