java search
Loading
Help improve Java Search

Tuesday, July 29, 2008

Binary Search Tree in Java with Generics

This post is more about generics than the actual implementation of the binary search tree. I tried to implement some of the suggestions in the developerworks articles titled "Java theory and practice: Going wild with generics". The Binary Search Tree of this example uses the first two suggestions. The rest are equally helpful though.
  1. A generic factory method that allows you to avoid redundantly specifying type parameters
    public static<T extends Comparable<? super T>> BinarySearchTree<T> createTestTree() 
    Can be used as shown below.
    BinarySearchTree<Test> tree = BinarySearchTree.createTestTree();
  2. By using bounded wildcards, we can now construct a tree with both the super and sub-class type objects.
    public class BinarySearchTree<T extends Comparable<? super T>> 
  3. The get-put principle
    Use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you do both.
  4. Wildcard capture: Use a generic method as a capture helper to workaround compiler's limitations dealing with wildcards. (refer to the article "Java theory and practice: Going wild with generics, Part 1")
Following is the complete source code
package trees;

import java.util.NoSuchElementException;

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

private Entry<T> root;

public BinarySearchTree() {
root = null;
}

public static<T extends Comparable<? super T>> BinarySearchTree<T> createTestTree() {
return new BinarySearchTree<T>();
}

public void insert(T value) {
root = insert(value, root);
}


public void remove(T value) {
root = remove(value, root);
}

public boolean contains(T value) {
return valueOf(find(value, root)) != null;
}

private T valueOf(Entry<T> entry) {
return entry == null ? null : entry.element;
}

private Entry<T> insert(T value, Entry<T> entry) {
if (entry == null)
entry = new Entry<T>(value);
else if (value.compareTo(entry.element) < 0)
entry.left = insert(value, entry.left);
else if (value.compareTo(entry.element) > 0)
entry.right = insert(value, entry.right);
else
throw new RuntimeException("Duplicate Entry : " + value.toString());
return entry;
}

private Entry<T> remove(T value, Entry<T> entry) {
if (entry == null)
throw new NoSuchElementException("Entry not found : " + value.toString());
if (value.compareTo(entry.element) < 0)
entry.left = remove(value, entry.left);
else if (value.compareTo(entry.element) > 0)
entry.right = remove(value, entry.right);
else {
// Entry found.
if (entry.left != null && entry.right != null) {

// Replace with in-order successor (the left-most child of the right subtree)
entry.element = findMin(entry.right).element;
entry.right = removeInorderSuccessor(entry.right);

// Replace with in-order predecessor (the right-most child of the left subtree)
// entry.element = findMax(entry.left).element;
// entry.left = removeInorderPredecessor(entry.left);
} else
entry = (entry.left != null) ? entry.left : entry.right;
}
return entry;
}

private Entry<T> removeInorderSuccessor(Entry<T> entry) {
if (entry == null)
throw new NoSuchElementException();
else if (entry.left != null) {
entry.left = removeInorderSuccessor(entry.left);
return entry;
} else
return entry.right;
}

private Entry<T> removeInorderPredecessor(Entry<T> entry) {
if (entry == null)
throw new NoSuchElementException();
else if (entry.right != null) {
entry.right = removeInorderPredecessor(entry.right);
return entry;
} else
return entry.left;
}

private Entry<T> findMin(Entry<T> entry) {
if (entry != null)
while (entry.left != null)
entry = entry.left;

return entry;
}

private Entry<T> findMax(Entry<T> entry) {
if (entry != null)
while (entry.right != null)
entry = entry.right;

return entry;
}

private Entry<T> find(T value, Entry<T> entry) {
while (entry != null) {
if (value.compareTo(entry.element) < 0)
entry = entry.left;
else if (value.compareTo(entry.element) > 0)
entry = entry.right;
else
return entry;
}

return null;
}

private void printInOrder(Entry<T> entry) {
if (entry != null) {
printInOrder(entry.left);
System.out.println(entry.element);
printInOrder(entry.right);
}
}

public void printInOrder() {
printInOrder(root);
}

private static class Entry<T extends Comparable<? super T>> {
T element;
Entry<T> left;
Entry<T> right;

Entry(T theElement) {
element = theElement;
left = right = null;
}
}

private static class Test implements Comparable<Test> {
private String value;

public Test(String value) {
this.value = value;
}

public String toString() {
return value;
}

@Override
public int compareTo(Test o) {
return this.value.compareTo(o.toString());
}
}

private static class Test1 extends Test {
public Test1(String value) {
super(value);
}
}

public static void main(String[] args) {
BinarySearchTree<Test> tree = BinarySearchTree.createTestTree();
int size = 20;

for (int i = 0; i <= size; i++) {
tree.insert(new Test1(String.valueOf(i)));
}

tree.insert(new Test1("100"));
tree.remove(new Test1("10"));
tree.remove(new Test1(String.valueOf(15)));
tree.remove(new Test1(String.valueOf(20)));
tree.printInOrder();
System.out.println("Contains (10) : " + tree.contains(new Test1("10")));
System.out.println("Contains (11) : " + tree.contains(new Test1(String.valueOf(11))));
}

}
References

2 comments: