comparable used as structure in a binary tree

Question

I have a binary tree in Java that works nicely. But I want to enhance the data content in the node. Currently I can add values on it doing such as:

for( int i = 1; i <=10; i++ )
    t.insert( new Integer( i ) );

Which will add the item like this:

public void insert( Comparable item ) {
    current = parent = grand = header;
    nullNode.element = item;
    ...
}

Here is the format of the tree:

private static class RedBlackNode {
    // Constructors
    RedBlackNode( Comparable theElement ) {
        this( theElement, null, null );
    }

    RedBlackNode( Comparable theElement, RedBlackNode lt, RedBlackNode rt ) {
        element  = theElement;
        left     = lt;
        right    = rt;
        color    = RedBlackTree.BLACK;
    }

    Comparable   element;    // The data in the node
    RedBlackNode left;       // Left child
    RedBlackNode right;      // Right child
    int          color;      // Color
}

For showing the tree, I do like that:

private void printTree( RedBlackNode t ) {
    if( t != nullNode ) {
        printTree( t.left );
        System.out.println(t.element);
        printTree( t.right );
    }
}

While when programming in many other languages, the element would be declared as a struct, for this sample code in Java it is declared as Comparable, and currently is only taking one element as integer. My question is, how can I use it similarly as a struct, in order to be able to also manipulate it such as doing in this pseudo code:

System.out.println(t.element.valueInt);
System.out.println(t.element.firstNameString);
System.out.println(t.element.lastNameString);

I have tried different syntax combinations based on some previous posts, but none has worked so far.

For the current code version with added comments, check Gist.

All suggestions are deeply appreciated.

I think you will need implement Comparable interface and override compareTo() method. — gyanu, May 18 '14 at 01:54

Sergey Kalinichenko · Accepted Answer · 2014-05-18T02:26:26.270

Comparable is an interface. Any class can implement it. Since the only thing a tree needs to know about its nodes is how to compare, and because Comparable provides precisely this kind of knowledge, using Comparable is sufficient for the tree.

However, it may not be enough for you, because you may want to know the other attributes that are part of your Comparable implementation. For that reason you may choose to make your RedBlackNode class generic on the exact type of the item that goes into the node, provided that it implements Comparable:

public class RedBlackTree <T extends Comparable<? super T>> {
    private static class RedBlackNode {
        ...
       T element;
    }
}

The rest of your code remains the same. For methods of the tree that expose Comparable, such as ones for getting node information, use the generic type T instead.

You need to supply the type of the node when creating RedBlackTree, like this:

RedBlackTree<MyClass> tree = new RedBlackTree<MyClass>();

Of course, MyClass must implement Comparable. The overall effect of the change is that when your code gets an element from the tree, it is strongly typed, letting you access its methods and fields without a cast.

Would you mind expanding on this syntax: `>`? I am new to generics AND the `Comparable` interface so the combination is blowing my mind.... — rocksNwaves, May 10 '21 at 12:57

comparable used as structure in a binary tree

1 Answers1