ansaurus

Question

Java: Should I favor generics when implementing various tree structures?

Answer 1

+1 A:

He decided to go for the Entry<Comparable> because Entry is an additional class representing a node in the tree. Most probably entry is defined similar to that

class Entry<T extends Comparable<? super T>> { T value; Entry<T> leftAncestor; Entry<T> rightAncestor; }

And then the binary tree structure has the root of the tree and the methods required to use it.

vstoyanov 2010-10-22 19:09:18

So main idea, is to allow me to insert Comparable implementation, but not to mix apples with pears? (Apple : Comparable, Pear : Comparable)

Xorty 2010-10-22 19:54:40

This is the main idea behind the Generics in this example. The idea behind using `Entry` instead of `Comparable` is because that's how node based data structures are implemented when you have `class`/`struct`.

vstoyanov 2010-10-22 20:00:06

Answer 2

+1 A:

You need to know children and structure about the tree. Comparable just gives you compareTo. Entry at least gives you left and right child so after your comparisons, you'll know how to manipulate the structure to keep the tree consistent.

SB 2010-10-22 19:09:40

@SB You partially answered about Comparable, now what about generics? See my comments to Kel's post ;)

Xorty 2010-10-22 19:34:30

You don't have to use Generics, but it's a good way to maintain type safety and object consistency in the tree. You could always use a standard Node class that returns Object, but if you wanted your Tree to be reusable across different objects, Generics are great. There's a reason that the Collections API moved to using Generics when introduced - they add safety and help developers understand a bit more about what they can and cannot do with a class.

SB 2010-10-22 19:37:42

Well I was not thinking of using Object as node's data holder :) I was thinking of using Comparable instead :) So node has: data(Comparable), leftson(Node), rightson(Node)

Xorty 2010-10-22 19:39:19

Sure you can do that too - but what if you built a tree that was supposed to only take Strings and someone added a Node that had a Date? Both are Comparable but can't be compared to each other

SB 2010-10-22 19:53:29

That's it. Thanks :)

Xorty 2010-10-22 20:09:05

Answer 3

A:

As far as I understand, this example shows details of implementation of binary search tree. Tree entries have to be not only Comparable, they also have to include information about left-right children entities and (if necessary) parent element.

Kel 2010-10-22 19:10:04

Ok and why he dind't extend Comparable interface with another - Node interface? It could also store left/right son. Can you think of any particular reason of generics usage here?

Xorty 2010-10-22 19:13:18

I think, Comparable interface is also suitable here. Generics is used to be able to store arbitrary data.

Kel 2010-10-22 19:17:31

But you won't be using any of the methods of generic aribtrary data, unless you create a very custom tree implementation, will you?

Xorty 2010-10-22 19:22:00

Of course for custom tree implementation it is not necessary. But it's claimed in the article header, that it's about generics: "This post is more about generics than the actual implementation of the binary search tree..." :)

Kel 2010-10-22 19:28:36

ansaurus

tags:

views:

answers:

Java: Should I favor generics when implementing various tree structures?

related questions