Java: Should I favor generics when implementing various tree structures?
I've just came over this article, that suggest various techniques with generics.
Author decided to use following:
public class BinarySearchTree<T extends Comparable<? super T&开发者_C百科gt;> {
And I don't get it. Why did author decide to use private Entry<T> root;
and not just private Comparable root
?
What particular advantage can generic tree node bring over implemented Comparable interface? Do I need to know more than compare 2 elements in such structures like Binary Search Tree, AVL Tree, Splay Tree, Red-Black Tree and so?
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.
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.
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.
精彩评论