1

I'm working on this homework that's kind of confusing me...

I am provided with the following BinarySearchTree class

import java.util.NoSuchElementException;

/**
 *
 * @param <T> The type of data stored in the nodes of the tree, must implement  Comparable<T> with the compareTo method.
 */
public class BinarySearchTree<T extends Comparable<T>> {


    BinaryTree<T> tree;

    int size;
    public BinarySearchTree() {
        tree = new BinaryTree<T>();
        size = 0;
    }

    public boolean isEmpty() {
        return tree.isEmpty();
    }

    protected BinaryTree<T> recursiveSearch(BinaryTree<T> root, T key) {
        if (root == null) {
            return null;
        }
        int c = key.compareTo(root.data);
        if (c == 0) {
            return root;
        }
        if (c < 0) {
            return recursiveSearch(root.left, key);
        } else {
            return recursiveSearch(root.right, key);
        }
    }

    public T search(T key) {
        if (tree.isEmpty()) { 
            return null;
        }
        return recursiveSearch(tree, key).data;
    }

    public void insert(T item) {

        if (tree.isEmpty()) { // insert here
            tree.makeRoot(item);
            size++;
            return;
        }

        // do an iterative descent
        BinaryTree<T> root = tree;
        boolean done=false;
        BinaryTree<T> newNode = null;
        while (!done) {
            int c = item.compareTo(root.data);
            if (c == 0) { // duplicate found, cannot be inserted
                throw new OrderViolationException();
            }
            if (c < 0) { // insert in left subtree
                if (root.left == null) { // insert here as left child
                    newNode = new BinaryTree<T>();
                    root.left = newNode;
                    done=true;
                } else { // go further down left subtree
                    root = root.left;
                }
            } else { // insert in right subtree
                if (root.right == null) { // insert here as right child 
                    newNode = new BinaryTree<T>();
                    root.right = newNode;
                    done=true;
                } else { // go further down right subtree
                    root = root.right;
                }
            }
        }
        // set fields of new node
        newNode.data = item;
        newNode.parent = root;
        size++;
    }

    /**
     * @param deleteNode Node whose parent will receive new node as right or left child,
     *                  depending on whether this node is its parent's right or left child. 
     * @param attach The node to be attached to parent of deleteNode.
     */
    protected void deleteHere(BinaryTree<T> deleteNode, BinaryTree<T> attach) {

        // deleteNode has only one subtree, attach
        BinaryTree<T> parent = deleteNode.parent;
        deleteNode.clear();  // clear the fields
        if (parent == null) {
            return;
        }
        if (deleteNode == parent.left) {
            // left child of parent, attach as left subtree
            parent.detachLeft();
            parent.attachLeft(attach);
            return;
        }
        // attach as right subtree
        parent.detachRight();
        parent.attachRight(attach);
    }


    protected BinaryTree<T> findPredecessor(BinaryTree<T> node) {
        if (node.left == null) {
            return null;
        }
        BinaryTree<T> pred = node.left; // turn left once
        while (pred.right != null) { // keep turning right
            pred = pred.right;
        }
        return pred;
    }


    public T delete(T key) {
        if (tree.isEmpty()) { // can't delete from an empty tree
            throw new NoSuchElementException();
        }

        // find node containing key 
        BinaryTree<T> deleteNode = recursiveSearch(tree, key);
        if (deleteNode == null) { // data not found, can't delete
            throw new NoSuchElementException();
        }

        BinaryTree<T> hold;

        // case c: deleteNode has exactly two subtrees
        if (deleteNode.right != null && deleteNode.left != null) {
            hold = findPredecessor(deleteNode);
            deleteNode.data = hold.data;
            deleteNode = hold; // fall through to case a or b
        }

        // case a: deleteNode is a leaf
        if (deleteNode.left == null && deleteNode.right == null) {
            deleteHere(deleteNode, null);
            size--;
            return deleteNode.data;
        }       

        // case b: deleteNode has exactly one subtree
        if (deleteNode.right != null) {
            hold = deleteNode.right;
            deleteNode.right = null;
        } else {
            hold = deleteNode.left;
            deleteNode.left = null;
        }

        deleteHere(deleteNode,hold);
        if (tree == deleteNode) { // root deleted
            tree = hold;
        }
        size--;
        return deleteNode.data;
    }


    public T minKey() {
        if (tree.data == null) { // tree empty, can't find min value
            throw new NoSuchElementException();
        }

        BinaryTree<T> root = tree;
        T min=root.data;
        root = root.left;  // turn left once
        while (root != null) {  // keep going left to leftmost node
            min = root.data;
            root = root.left;
        }
        return min;
    }


    public T maxKey() {
        if (tree.getData() == null) { // tree empty, can't find max value
            throw new NoSuchElementException();
        }

        BinaryTree<T> root=tree;
        T max=root.data;
        root = root.right;  // turn right once
        while (root != null) { // keep going to rightmost node
            max = root.data;
            root = root.right;
        }
        return max;
    }


    public int size() {
        return size;
    }


    protected void recursivePreOrder(BinaryTree<T> root, Visitor<T> visitor) {
        if (root != null) {
            visitor.visit(root);
            recursivePreOrder(root.left, visitor);
            recursivePreOrder(root.right, visitor);
        }
    }


    public void preOrder(Visitor<T> visitor) {
        if (tree.isEmpty()) {
            return;
        }
        recursivePreOrder(tree, visitor);
    }


    protected void recursiveInOrder(BinaryTree<T> root, Visitor<T> visitor) {
        if (root != null) {
            recursiveInOrder(root.left, visitor);
            visitor.visit(root);
            recursiveInOrder(root.right, visitor);
        }
    }


    public void inOrder(Visitor<T> visitor) {
        if (tree.isEmpty()) {   
            return;
        }
        recursiveInOrder(tree, visitor);
    }


    protected void recursivePostOrder(BinaryTree<T> root, Visitor<T> visitor) {
        if (root != null) {
            recursivePostOrder(root.left, visitor);
            recursivePostOrder(root.right, visitor);
            visitor.visit(root);
        }
    }

    public void postOrder(Visitor<T> visitor) {
        if (tree.isEmpty()) {
            return;
        }
        recursivePostOrder(tree, visitor);
    }
}

================================================================================

Now I have another class Student.... I want to create a binary search tree of Student objects..

BinarySearchTree<Student> tree = new BinarySearchTree<Student>();

However when I do that I get the following error:

Bound mismatch: The type Student is not a valid substitute for the bounded parameter > of the type BinarySearchTree

Any ideas what's happening here... I can't figure it out.

Improve this question
1
  • By the way I recommend that the bound be "BinarySearchTree<T extends Comparable<? super T>>" instead of just "BinarySearchTree<T extends Comparable<T>>". The way you have it is more restrictive than it needs to be and will run into problems when you have subclasses of classes which implement Comparable. Commented May 2, 2009 at 5:59

3 Answers 3

Reset to default
6 
 public class BinarySearchTree<T extends Comparable<T>>

A formal generics argument, in your case T, lists what's required for a class to be a valid T. In you case, you've said, "to be a valid T, a class must implement Comparable" (The keyword is "extends", but in practice that means "extends or implements".)

In your instantiation, T is Student. If we substitute Student for T:

public class BinarySearchTree<Student extends Comparable<Student>>

is that a true statement? Does Student really implement Comparable?

If it does, Student fits the requirement of being a T, and so you can use Student as the actual parameter for the formal parameter T.

If not, you get the compiler's complaint you saw.

Actually, to cover more complicated situations where a subclass's implementation of Comparable is done by a super class, the more general form would be:

   public class BinarySearchTree<T extends Comparable<? super T > >

So you need to make Student implement Comparable< Student >.

Note that I didn't say that the compiler's looking for a Student.compareTo. It doesn't even get that far. It's looking to see if T (in your case, Student) is declared as implementing Comparable< T> (in your case, Comparable< Student >).

Now adding implements Comparable< Student > to Student will also make the compiler ensure that there's a public int compareTo method on Student. But without the "implements Comparable", even if the compiler knows there's a method Student.compareTo, it doesn't know that that compareTo is the Comparable.compareTo.

(In other words, we're looking for declared implementation, not just that there happens to be a method with the right name and signature.)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thanks for your help... It worked... I changed T for Student, implemented Comparable and added the compareTo method.
Whoa -- don't change T for student in BinarySearchTree -- tpdi was just saying to think what happens when you call new BinarySearchTree<Student> - the compiler will plug in Student for T. Your declaration should still read public class BinarySearchTree<T extends Comparable<T>>.
Yes, Scott is right. T is the formal argument, Student the actual argument.
0

Does the class Student implement Comparable?

Improve this answer

4 Comments

No it does not.... that's what I was thinking I should do, but I'm not quite sure how to implement the compareTo method.
If you don't implement comparable, you don't fit the requirements for <T extends Comparable<T>>. Without comparison, a binary search is meaningless.
Ok I implemented Comparable in the student class... my compareTo looks like this: public int compareTo(Object o) { Student cr = (Student) o; int cn1 = Integer.parseInt(this.id); int cn2 = Integer.parseInt(cr.id); if(cn1 > cn2) return 1; else if(cn1 < cn2) return -1; else return 0; } However I still get the same error
You should implement "int compareTo(Student o)", note parameter type. Compiler should warn about it otherwise.
0

but I'm not quite sure how to implement the compareTo method.

Basically it's something like the following. How the ordering works you have to decide.

class Student implements Comparable<Student> {

    //...

    int compareTo(Student other) {
        // return some negative number if this object is less than other
        // return 0 if this object is equal to other
        // return some positive number if this object is greater than other
    }
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.