问题描述:

I am doing an assignment, implementing own Binary Search Tree. The thing is, we have our own implementation of Node its parent is not directly accessible.

I have searched for answers, but I do not want to copy the solution entirely and I still don't seem to get it right, though. I miss some cases when the element is not removed.

Can you please help what am I doing wrong?

This is the remove method:

void remove(E elem) {

if(elem != null){

if (root != null && contains(elem)) {

removeFromSubtree(elem, root, null);

}

}

}

void removeFromSubtree(E elem, Node<E> current, Node<E> parent) {

if(elem.less(current.contents)){

if(current.left == null) return ;

removeFromSubtree(elem, current.left, current);

} else if(elem.greater(current.contents)){

if(current.right == null)return;

removeFromSubtree(elem, current.right, current);

} else {

if(current.left != null && current.right != null){

//both children

if(parent == null){

Node<E> n = new Node<>(null, null);

n.left = root;

removeFromSubtree(root.contents, n, null);

root = n.left;

root.setParent(null);

}

E min = subtreeMin(current.right);

current.contents = min;

removeFromSubtree(min, current.right, current);

} else if(current.left != null){

//left child

if (parent == null) {

root = current.left;

current.left.setParent(null);

return ;

}

setParentChild(current, parent, current.left);

} else if(current.right != null){

//right child

if (parent == null) {

root = current.right;

current.right.setParent(null);

return ;

}

setParentChild(current, parent, current.right);

} else {

if (parent == null) {

root = null;

return ;

}

setParentChild(current, parent, null);

}

}

}

Nodes use generic interface

class Node<E extends DSAComparable<E>>

which has just methods for comparation. It looks like this

interface DSAComparable<E extends DSAComparable<E>> {

boolean less(E other);

boolean greater(E other);

boolean equal(E other);

}

I use another methon inside remove that sets node's parent's child, depending if its left child or right child.

void setParentChild(Node<E> node, Node<E> parent,Node<E> value){

if(parent!= null){

if (parent.left == node) {

parent.left = value;

} else {

parent.right = value;

}

if(value!= null) value.setParent(parent);

}

}

Method subtreeMin(Node node) finds the smallest value in a subtree (the most left one)

网友答案:

Understanding your code is not so easy, since it still lacks of details.

I would refer to such an implementation of the Binary Search Tree that you can find online.

See for instance the one from Algorithms, 4th Ed..

相关阅读:
Top