3
\$\begingroup\$

I use this interface for my BST node class:

public interface BinNode<E> {
    public E getValue();
    public void setValue(E value);

    public BinNode<E> getLeftChild();

    public BinNode<E> getRightChild();

    public boolean isLeaf();
}

My BSTNode is implemented as follows:

public class BinarySearchTreeNode<Key, E> implements BinNode<E> {
    private Key key;
    private E value;

    private BinarySearchTreeNode<Key, E> leftChild;
    private BinarySearchTreeNode<Key, E> rightChild;

    public BinarySearchTreeNode(Key key, E value,
        BinarySearchTreeNode<Key, E> leftChild,
        BinarySearchTreeNode<Key, E> rightChild) {
    this.key = key;
    this.value = value;
    this.leftChild = leftChild;
    this.rightChild = rightChild;
    }

    public Key getKey() {
    return this.key;
    }

    public void setKey(Key key) {
    this.key = key;
    }

    @Override
    public E getValue() {
    return this.value;
    }

    @Override
    public void setValue(E value) {
    this.value = value;
    }

    @Override
    public BinarySearchTreeNode<Key, E> getLeftChild() {
    return this.leftChild;
    }

    public void setLeftChild(BinarySearchTreeNode<Key, E> leftChild) {
    this.leftChild = leftChild;
    }

    @Override
    public BinarySearchTreeNode<Key, E> getRightChild() {
    return this.rightChild;
    }

    public void setRightChild(BinarySearchTreeNode<Key, E> rightChild) {
    this.rightChild = rightChild;
    }

    @Override
    public boolean isLeaf() {
    if (this.leftChild == null && this.rightChild == null) {
        return true;
    } else {
        return false;
    }
    }
}

And finally my binary search tree is implemented as:

public class BinarySearchTree<Key extends Comparable<? super Key>, E>
    implements Dictionary<Key, E> {

    private BinarySearchTreeNode<Key, E> rootNode;
    private int numberOfNodes;

    public BinarySearchTree() {
    this.rootNode = null;
    this.numberOfNodes = 0;
    }

    @Override
    public void clear() {
    this.rootNode = null;
    this.numberOfNodes = 0;
    }

    @Override
    public void insert(Key key, E element) {
    this.rootNode = this.insertHelp(this.rootNode, key, element);
    this.numberOfNodes++;
    }

    @Override
    public E remove(Key key) {
    // first find the node to remove
    E nodeToRemove = this.findHelp(this.rootNode, key);
    if (nodeToRemove != null) {
        // now remove the found node
        this.rootNode = this.removeHelp(this.rootNode, key);
        this.numberOfNodes--;
    }
    return nodeToRemove;
    }

    @Override
    public E removeRandomElement() {
    if (this.rootNode == null) {
        return null;
    }
    E randomeNodeToRemove = this.rootNode.getValue();
    this.rootNode = this.removeHelp(this.rootNode, this.rootNode.getKey());
    this.numberOfNodes--;
    return randomeNodeToRemove;
    }

    @Override
    public E find(Key key) {
    return this.findHelp(this.rootNode, key);
    }

    @Override
    public int size() {
    return this.numberOfNodes;
    }

    private E findHelp(BinarySearchTreeNode<Key, E> rootNode, Key key) {
    if (rootNode == null) {
        return null;
    }
    if (rootNode.getKey().compareTo(key) > 0) {
        return this.findHelp(rootNode.getLeftChild(), key);
    } else if (rootNode.getKey().compareTo(key) == 0) {
        return rootNode.getValue();
    } else {
        return this.findHelp(rootNode.getRightChild(), key);
    }
    }

    private BinarySearchTreeNode<Key, E> insertHelp(
        BinarySearchTreeNode<Key, E> rootNode, Key key, E element) {
    if (rootNode == null) {
        return new BinarySearchTreeNode<Key, E>(key, element, null, null);
    }
    if (rootNode.getKey().compareTo(key) > 0) {
        rootNode.setLeftChild(this.insertHelp(rootNode.getLeftChild(), key,
            element));
    } else {
        rootNode.setRightChild(this.insertHelp(rootNode.getRightChild(),
            key, element));
    }
    return rootNode;
    }

    private BinarySearchTreeNode<Key, E> removeHelp(
        BinarySearchTreeNode<Key, E> rootNode, Key key) {
    if (rootNode == null) {
        return null;
    }
    if (rootNode.getKey().compareTo(key) > 0) {
        rootNode.setLeftChild(this.removeHelp(rootNode.getLeftChild(), key));
    } else if (rootNode.getKey().compareTo(key) < 0) {
        rootNode.setRightChild(this.removeHelp(rootNode.getRightChild(),
            key));
    } else { // found node to remove
        if (rootNode.getLeftChild() == null) {
        return rootNode.getRightChild();
        } else if (rootNode.getRightChild() == null) {
        return rootNode.getLeftChild();
        } else { // there are 2 children
        BinarySearchTreeNode<Key, E> nodeToRemove = this
            .getNodeWithMinimumValue(rootNode.getRightChild());
        rootNode.setValue(nodeToRemove.getValue());
        rootNode.setKey(nodeToRemove.getKey());
        rootNode.setRightChild(this.deleteNodeWithMinimumValue(rootNode.getRightChild()));
        }
    }
    return rootNode;
    }

    private BinarySearchTreeNode<Key, E> getNodeWithMinimumValue(
        BinarySearchTreeNode<Key, E> rootNode) {
    if (rootNode.getLeftChild() == null) {
        return rootNode;
    }
    return this.getNodeWithMinimumValue(rootNode.getLeftChild());
    }

    private BinarySearchTreeNode<Key, E> deleteNodeWithMinimumValue(
        BinarySearchTreeNode<Key, E> rootNode) {
    if (rootNode.getLeftChild() == null) {
        return rootNode.getRightChild();
    }
    rootNode.setLeftChild(this.deleteNodeWithMinimumValue(rootNode.getLeftChild()));
    return rootNode;
    }

    // TODO: add traversal functions
}
\$\endgroup\$
3
\$\begingroup\$

When you have a custom implementation of something, and it has internal structures, like, in your case, the BinarySearchTreeNode, there is no real reason to have the interface for it. There is no public use of the interface, and not even your actual tree uses it. It is redundant. You can delete it, and remove the reference from the BinarySearchTreeNode

Additionally, there is no need for the BinarySearchTreeNode to be public. You never return the instance from the Tree, so there is no reason to expose it. Leaving it package-private (no public or private declaration) would be a decent choice, but commonly, the class is actually nested as a private-static inner class in the actual tree.

I am not sure what the Dictionary<> interface is ... Oh... really? java.util.Dictionary ... this should be java.util.Map<...> since the documentation for Dictionary (which, in 10 years, I have never seen before now) says:

NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.

Apart from that, the class looks pretty good.

public class BinarySearchTree<Key extends Comparable<? super Key>, E>
implements Map<Key, E> {

    private static class BinarySearchTreeNode<Key, E> {

        ....

   }

   .....

}
\$\endgroup\$
3
\$\begingroup\$

Just a small improvement: although this might be seen as a matter of taste, I personally find this kind of construction too verbose:

 if (this.leftChild == null && this.rightChild == null) {
        return true;
 } else {
        return false;
 }

You could easily convert it into a one-liner:

return (this.leftChild == null && this.rightChild == null);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.