0

I am trying to implement a Binary Search Tree and if I use the generic programming in java then this tree should be able to store any kind of data e.g. int, Strings or basically any other object. But the problem with such a class is with coding the functions e.g. if I am coding the addToTree function, then "<" operator can be used to compare int and it would successfully insert int into the tree but it won't insert strings or other objects because comparing strings and other objects using "<" operator may not be allowed.

This problem is same for other data structures too.

Improve this question
3
  • First of all, you can't use primitive types as parameters for generics (so, you can't use '<', '>' and other operators). Secondary, you should bound your collection to classes that implements Comparable and use compareTo method, that should do the trick. Commented Dec 10, 2013 at 6:51
  • You cannot use arithmetic operators to generics. If you need objects comparison, than your generic type will have to be restricted to <T extends Comparable> or any other common type base (usually interface) you will create for implementation logic. Commented Dec 10, 2013 at 6:51
  • Or you'll have to delegate the comparison to a Comparator defined when constructing the binary tree, just as TreeSet does. Why don't you look at its documentation and code? Commented Dec 10, 2013 at 7:03

3 Answers 3

Reset to default
2

You should limit the generic type for your BinarySearchTree,

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

The element should implement Comparable interface, otherwise you are not able to order the elements.

Edit: As @JB Nizet suggests, don't use raw Comparable

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

3 Comments

It should be BinarySearchTree<T extends Comparable<? super T>>. Don't use the raw Comparable type.
@JBNizet just out of curiosity..why shouldn't raw comparable be used?
Because you would lose the type-safety that generic types provide. Just as you wouldn't use ArrayList to store Strings, but ArrayList<String>.
0

I think I get what you're saying. Typically, well-designed classes (likely all the standard ones you'll ever use in the JDK) implement Comparable and override the built-in compareTo method which defines how the <, >, and == operations work. compareTo returns 1 if greater, 0 if equal, -1 if less.

If you wish to create your own class to put in the binary tree, then yes, you will have to implement Comparable.

Edit: Answer below me makes a very important point: if you intend on using comparisons, you should restrict the possible class types to ones that extend Comparable!

Improve this answer

3 Comments

So you're implying that java.util.List is not well-designed because it does not implement Comparable? Comparison only makes sense for a very limited subset of classes.
@heuster insertion in a binary search tree needs sorting and that is why elements need to be compared.. in case of list class elements do not need to be compared for writing basic functions like addToList so list does not require comparable anyway
List isn't really relevant to comparison, but I suppose I worded it less precisely than I could have. What I mean to say is data classes typically implement Comparable.
0

To accomplish the other answers:

Implementing the Comparable interface only makes sense for classes who really have a natural ordering. Additionally, this ordering should be consistent with the equals method. Implementing the equals and the compareTo methods sounds easier, than it sometimes really is. This should be well-designed.

Often enough, there is no real natural ordering on the objects of a class. But you will have tasks to order them on a specific property, nevertheless. For this kind of tasks, you can implement another interface: Comparator. A comparator then can be used to order your objects as you need.

Take a look at TreeSet, which is such a search tree. This Set implementation provides two constructors: One is designed for being used with objects that are comparable. The other takes a comparator for that task, and is designed for being used with non-comparable objects.

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.