Delete a Node in BST
Page 1 of 1
Delete a Node in BST
public Set<E> delete(E x){
if(!contains(x)) return this;
reutrn new Set<E>(deleteAux(x, root));
}
private Node deleteAux(E x, Node t){
if(t==null) return null;
int c=x.compareTo(t.v);
if(c=0)
return join(t.l, t.r);
if(c<0)
return create(deleteAux(x,t.l), t.v,t.r);
else
return create(t.l, t.v, deleteAux(x,t.r));
}
public Node join(Node t1, Node t2){
if(t1==null)
return t2;
if(t2==null)
return t1;
return create(t1, minAux(t2), deleteMin(t2));
}
public Node deleteMin(Node t){
if(t.l==null) return t.r;
return create(deleteMin(t.l),t.v, t.r);
}
if(!contains(x)) return this;
reutrn new Set<E>(deleteAux(x, root));
}
private Node deleteAux(E x, Node t){
if(t==null) return null;
int c=x.compareTo(t.v);
if(c=0)
return join(t.l, t.r);
if(c<0)
return create(deleteAux(x,t.l), t.v,t.r);
else
return create(t.l, t.v, deleteAux(x,t.r));
}
public Node join(Node t1, Node t2){
if(t1==null)
return t2;
if(t2==null)
return t1;
return create(t1, minAux(t2), deleteMin(t2));
}
public Node deleteMin(Node t){
if(t.l==null) return t.r;
return create(deleteMin(t.l),t.v, t.r);
}
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|