[Ap0C552]

I am reading a few articles on binary search tree, and I have a few questions that they are not clear on.

I started coding a Binary search tree using generics. Then I realized I had the problem of how to compare them, if I don't know exactly what the objects I am comparing are.

Then I started to notice that the code examples had something called "comparables" in them. Unfortunately non of them went into detail about these. I assume they are used to solve the aforementioned problem I had about comparing generic types.

Do I just add "implements comparable" to my Binary Search tree node class? This allows me to use compareTo on the generic type?

[blackcompe]

It's incorrect to make the tree Comparable. Your not comparing trees, your comparing the data encapsulated in its node.

public class BST<T> implements Comparable<BST>

No.

The type argument should be Comparable.

public class BST<T extends Comparable<? super T>> {

That may be a little confusing. You could also have

public class BST<T extends Comparable<T>> {

The extends keyword requires the type T to implement the Comparable interface. Then you could insert String, Integer, GregorianCalendar .... whatever implements that interface. If your inserting instances of a user-defined class it must implement the interface. See my BST snippet and the Java tutorials on object ordering.

This post has been edited by blackcompe: 01 November 2011 - 10:49 AM

[Ap0C552]

Ok I understand. Kind of..

So now whatever generic we hold, it must implement the interface comparable. So things like ints and string already implement comparable?

But what exactly is this part saying/doing....

<? super T>


EDIT:

I am looking at some examples in my course notes and I am wondering what the the variable key is for in the example....

public class TreeNode<E> {
public int key;
public E data;
public TreeNode<E> left;
public TreeNode<E> right;
public TreeNode<E> parent;
}
public class BST<E> implements DictionaryADT<E> {
private TreeNode<E> treeRoot;
public BST() { treeRoot = null; }

This post has been edited by Ap0C552: 01 November 2011 - 11:15 AM

[blackcompe]

Quote

So now whatever generic we hold, it must implement the interface comparable. So things like ints and string already implement comparable?

That's right.

Comparable objects don't have to be comparable to themselves only. Then can be made comparable to their super types or anything else.

public class BST<T extends Comparable<T>> {

That implies the type is comparable to itself only. That's too restrictive.

public class BST<T extends Comparable<? super T>> {

That implies the type could be compared to an Object or any super type of T.

I can't think of an example where you'd be comparing two elements of a generic collection that are of a different type. Lower bounds have other purposes too, like writing into generic collections.

See tutorial on lower bounds. Your probably better off not using the super version.

Quote

I am looking at some examples in my course notes and I am wondering what the the variable key is for in the example....

So your tree is really a map: a data structure with key-value pairs. It could serve as an inefficient implementation of Java's TreeMap<K,V>. Have you ever used a hash table? That's a map. You search for a key and you get its value.

This post has been edited by blackcompe: 01 November 2011 - 01:18 PM

[Ap0C552]

So what exactly is the key in this example?

How is represented?

Its so much easier to understand with actual examples.

Why should my node hold any of value then the value itself?

Is it like saying we would order all these nodes according to their key , and their value is just some in significant value they contain that is completely irrelevant in the ordering?

This post has been edited by Ap0C552: 01 November 2011 - 02:59 PM

[blackcompe]

A BST doesn't have to hold key-value pairs. In my snippet it just holds values and you give it a value to search for. Your getting too bogged down into details. What exactly is your assignment? A requirements spec would be nice. What is your tree supposed to hold? Just because your course notes have one thing doesn't mean your code has to have it.

[Ap0C552]

I am not working on an assignment.....just studying.

I just wanted to understand that specific code.

So basically in that specific code the node has a value to which it will be ordered by, and a value that is just held, but has nothing to do with the ordering. If this is correct, there is nothing more I need to worry about Just clarifying this.

Thanks

[blackcompe]

Quote

So basically in that specific code the node has a value to which it will be ordered by, and a value that is just held, but has nothing to do with the ordering.

Yes, in my snippet, the value encompassed in the node determines where the node is placed into the tree. If my tree was a map, where I'm using key-values pair, then the key determines where the node is placed. The value just tags along. The key would implement Comparable.

Here's how a map would look. Check out the main method.

public class Main {

	public static void main( String[] args ) {
		
		//This is a map
		
		BST<Integer, Student> studRecs = new BST<>();
		studRecs.put( 109823, new Student( "Mike Jones" ) );
		studRecs.put( 109824, new Student( "John Smith" ) );
		
		Student stu = studRecs.get( 109823 );
		
		//This is basic binary search tree (from my snippet)
		
		BST<Student> t = new BST<>();
		t.insert( new Student( "Mike Jones" ) );
		t.insert( new Student( "John Smith" ) );
		
		Student res = t.search( new Student( "John Smith" ) );
		
	}

}

class BST<K extends Comparable<K>, V> {

	private Node<K, V>	root;

	void put( K key, V value ) {
		if(root == null) 
			root = new Node<>( key, value );
		else
			put( root, key, value );
	}

	//We're comparing keys, not values
	
	void put( Node<K, V> root, K key, V value ) {
		if ( key.compareTo( root.key ) <= 0 ) { //go left
			if ( root.left == null ) {
				root.left = new Node<>( key, value );
			} else {
				put( root.left, key, value );
			}
		} else if ( key.compareTo( root.key ) > 0 ) { //go right
			if ( root.right == null ) {
				root.right = new Node<>( key, value );
			} else {
				put( root.right, key, value );
			}
		}
	}
	
	V get(K key) {
		return null;
	}

	class Node<K, V> {

		K	key;
		V	value;
		Node<K, V>	left, right;

		Node( K key, V value ) {
			this.key = key;
			this.value = value;
		}
	}
}

class Student {

	private String	name;

	Student( String name ) {
		this.name = name;
	}
}

Here are two examples: BST map and a Basic BST. Use a map when you need to map a key to a value.

This post has been edited by blackcompe: 01 November 2011 - 05:27 PM

[Ap0C552]

Thanks for the help!