Results 1 to 7 of 7
  1. #1
    X-Malleus is offline Member
    Join Date
    Apr 2010
    Posts
    4
    Rep Power
    0

    Default Generic Binary Search Tree, Allowing Only Comparable Elements

    Hi, everyone. I'm new to generics, and I can't figure out exactly how to do this. I need to implement a binary search tree. This is easy enough to do if I only allow it to contain integers, but I want it to accept any object that implements Comparable. So normally, the class definition would look something like this:

    Java Code:
    public class BinarySearchTree {
    ...
    }
    I want to make it a BinarySearchTree that can, and must, be assigned to a particular Comparable type. Something like this:

    Java Code:
    public class BinarySearchTree<Comparable> {
    ...
    }
    I know that this isn't the correct way to do it, though. How can I do this?

  2. #2
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    Java Code:
    public class BinarySearchTree<T extends Comparable> {
    ...
    }

  3. #3
    X-Malleus is offline Member
    Join Date
    Apr 2010
    Posts
    4
    Rep Power
    0

    Default

    Quote Originally Posted by iluxa View Post
    Java Code:
    public class BinarySearchTree<T extends Comparable> {
    ...
    }
    I found things looking like this in searching for the answer to this problem. I must admit that I'm confused by it, though. From what I understand, extends causes the subclass to inherit all methods and variables from the superclass. Comparable is an interface, though, so doesn't that mean that anything that extends Comparable is also an interface? I'm sure that I'm missing something here, but my line of thinking is that if T extends Comparable, then T is an interface, but I want to pass a class, such as Integer, when I create a new BinarySearchTree. Something in my understanding of one or more of these ideas must be incorrect.

  4. #4
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    actually, when applied to interfaces, extends behaves a bit different:

    Java Code:
    interface A {
    ...
    }
    interface B extends A {
    ...
    }
    in my code snippet,

    T extends Comparable

    means you'll be able to use any type as long as its a sub-type of Comparable. Since Integer implements Comparable, you can use Integer.

  5. #5
    X-Malleus is offline Member
    Join Date
    Apr 2010
    Posts
    4
    Rep Power
    0

    Default

    Ah, well now I think I understand it better. Thankfully, my code will now compile, but I do get a warning when I do this:
    Java Code:
    public class BinarySearchTree<T extends Comparable> {
    ...
    }
    The warning is this:

    Comparable is a raw type. References to generic type Comparable<T> should be parameterized.

    I fixed this by using BinarySearchTree<T extends Comparable<T>> instead. Will this produce the results that I'm looking for?

  6. #6
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    I think so... Your general approach is correct, the syntax technicalities of Java generics though are not for mere mortals... I mean take a look here:

    Enum (Java 2 Platform SE 5.0)

    public abstract class Enum<E extends Enum<E>>

    !!!

  7. #7
    X-Malleus is offline Member
    Join Date
    Apr 2010
    Posts
    4
    Rep Power
    0

    Default

    Hahah wow! That is indeed a bit crazy-looking. In any case, it seems that I've gotten what I need. Thanks so much for your help!

Similar Threads

  1. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  2. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 01:42 AM
  3. Binary Search Tree
    By anmadie in forum New To Java
    Replies: 5
    Last Post: 11-17-2009, 02:39 AM
  4. Binary Search Tree
    By Goo in forum New To Java
    Replies: 0
    Last Post: 03-06-2009, 04:46 PM
  5. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 02:03 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •