package BST;
import exceptions.DuplicateItemException;
// Here I implement a very basic binary search tree, which
// checks for duplicate items. The tree is not balanced,
// so it is possible for an instance of this class to
// degenerate into a linked list (thus rendering any
// operations that would normally be logarithmic in regards
// to time would be linear.
public class BST<E>
{
// Node is a statically-nested class. As such, it doesn't
// have access to any other member of the enclosing class,
// BST.
@SuppressWarnings("unchecked")
private static class Node<Comparable>
{
public Node left;
public Node right;
public Comparable data;
public Node(Comparable data, Node left, Node right)
{
this.left = null;
this.right = null;
this.data = data;
}
}
private Node<Comparable> root;
private int count;
public BST()
{
root = null;
count = 0;
}
public boolean isEmpty()
{
return root == null;
}
// This contains() method only delegates work
// to the recusrive contains() method.
public boolean contains (Comparable data)
{
return contains(root, data);
}
@SuppressWarnings("unchecked")
private boolean contains (Node ref, Comparable data)
{
if (ref == null)
return false;
else if (data.compareTo(ref.data) == 0)
return true;
else if (data.compareTo(ref.data) < 0)
return contains (ref.left, data);
else if (data.compareTo(ref.data) > 0)
return contains (ref.right, data);
else
return false;
}
// This add() method only delegates the work of
// actually inserting an item to the insert()
// method.
@SuppressWarnings("unchecked")
public void add (Comparable data) throws DuplicateItemException
{
root = insert(root, data);
}
private Node insert (Node current, Comparable data) throws DuplicateItemException
{
if(current == null)
current = new Node(data, null, null);
else if (data.compareTo(current.data) < 0)
current.left = insert (current.left, data);
else if (data.compareTo(current.data) > 0)
current.right = insert (current.right, data);
else if (data.compareTo(current.data) == 0)
throw new DuplicateItemException (data.toString());
count++;
return current;
}
// This method just delegates the work of
// traversing the tree to the print()
// method.
public void printAll()
{
print(root);
}
// This method does an in-order traversal
// of the tree in order to print the value
// of each node.
private Node print (Node current)
{
if (current == null)
return current;
else
{
print (current.left);
System.out.println(current.data);
print (current.right);
return current;
}
}
@SuppressWarnings("unchecked")
public void remove(Comparable data)
{
root = remove (root, data);
}
@SuppressWarnings("unchecked")
private Node remove (Node current, Comparable data)
{
if (data.compareTo(current.data) == 0)
{
// Node has a right subtree, but no left subtree.
if (current.left == null && current.right != null)
{
Comparable childData = (Comparable) current.right.data;
current.data = childData;
current.right = null;
}
// Node has a left subtree, but no right subtree.
else if (current.left != null && current.right == null)
{
Comparable childData = (Comparable) current.left.data;
current.data = childData;
current.left = null;
}
// Node is a leaf node.
else if (current.left == null && current.right == null)
current = null;
// Node has both a left & right subtree.
else
{
Node successor = findInorderSuccessor(current.right);
current.data = successor.data;
current.right = successor.right;
}
count--;
return current;
}
else
{
if (data.compareTo(current.data) > 0)
{
current.right = remove (current.right, data);
return current;
}
else
{
current.left = remove (current.left, data);
return current;
}
}
}
@SuppressWarnings("unchecked")
private Node findInorderSuccessor(Node current)
{
while (current.left != null)
current = current.left;
return current;
}
}
Refactorings
No refactoring yet !
orangelight.myopenid.com
January 18, 2012, January 18, 2012 23:27, permalink
No rating.
Login to rate!
Thanks for your input. All my warnings are gone now. However, I'd just like to clarify one thing, what exactly the following line means:
public class BST<E extends Comparable<? super E>>
To me, this reads as "BST of type E, and E is a "subtype" of Comparable, and in this case Comparable is of type E or some subtype thereof". Does that make any sense at all?
orangelight.myopenid.com
January 18, 2012, January 18, 2012 23:28, permalink
No rating.
Login to rate!
Thanks for your input. All my warnings are gone now. However, I'd just like to clarify one thing, what exactly the following line means:
public class BST<E extends Comparable<? super E>>
To me, this reads as "BST of type E, and E is a "subtype" of Comparable, and in this case Comparable is of type E or some subtype thereof". Does that make any sense at all?
spoon
January 18, 2012, January 18, 2012 20:51, permalink
No rating.
Login to rate!
You are not using Generics correctly. Basically, E should be the type of the the data, and E should be Comparable to itself. Node needs to be parameterized with E.
package BST;
import exceptions.DuplicateItemException;
// Here I implement a very basic binary search tree, which
// checks for duplicate items. The tree is not balanced,
// so it is possible for an instance of this class to
// degenerate into a linked list (thus rendering any
// operations that would normally be logarithmic in regards
// to time would be linear.
public class BST<E extends Comparable<? super E>>
{
// Node is a statically-nested class. As such, it doesn't
// have access to any other member of the enclosing class,
// BST.
private static class Node<E>
{
public Node<E> left;
public Node<E> right;
public E data;
public Node(E data, Node<E> left, Node<E> right)
{
this.left = null;
this.right = null;
this.data = data;
}
}
private Node<E> root;
private int count;
public boolean isEmpty()
{
return root == null;
}
// This contains() method only delegates work
// to the recusrive contains() method.
public boolean contains (E data)
{
return contains(root, data);
}
private boolean contains (Node<E> ref, E data)
{
if (ref == null)
return false;
else if (data.compareTo(ref.data) == 0)
return true;
else if (data.compareTo(ref.data) < 0)
return contains (ref.left, data);
else if (data.compareTo(ref.data) > 0)
return contains (ref.right, data);
else
return false;
}
// This add() method only delegates the work of
// actually inserting an item to the insert()
// method.
public void add (E data) throws DuplicateItemException
{
root = insert(root, data);
}
private Node<E> insert (Node<E> current, E data) throws DuplicateItemException
{
if(current == null)
current = new Node<E>(data, null, null);
else if (data.compareTo(current.data) < 0)
current.left = insert (current.left, data);
else if (data.compareTo(current.data) > 0)
current.right = insert (current.right, data);
else if (data.compareTo(current.data) == 0)
throw new DuplicateItemException (data.toString());
count++;
return current;
}
// This method just delegates the work of
// traversing the tree to the print()
// method.
public void printAll()
{
print(root);
}
// This method does an in-order traversal
// of the tree in order to print the value
// of each node.
private void print (Node<E> current)
{
if (current != null)
{
print (current.left);
System.out.println(current.data);
print (current.right);
}
}
public void remove(E data)
{
root = remove (root, data);
}
private Node<E> remove (Node<E> current, E data)
{
if (data.compareTo(current.data) == 0)
{
// Node has a right subtree, but no left subtree.
if (current.left == null && current.right != null)
{
E childData = current.right.data;
current.data = childData;
current.right = null;
}
// Node has a left subtree, but no right subtree.
else if (current.left != null && current.right == null)
{
E childData = current.left.data;
current.data = childData;
current.left = null;
}
// Node is a leaf node.
else if (current.left == null && current.right == null)
current = null;
// Node has both a left & right subtree.
else
{
Node<E> successor = findInorderSuccessor(current.right);
current.data = successor.data;
current.right = successor.right;
}
count--;
return current;
}
else
{
if (data.compareTo(current.data) > 0)
{
current.right = remove (current.right, data);
return current;
}
else
{
current.left = remove (current.left, data);
return current;
}
}
}
private Node<E> findInorderSuccessor(Node<E> current)
{
while (current.left != null)
current = current.left;
return current;
}
}
Ants
January 19, 2012, January 19, 2012 02:26, permalink
No rating.
Login to rate!
I think there is a bug in the remove method.
Given a tree:
5
/ \
3 8
/ \ / \
1 4 6 9
\ \
2 7
Attempting to delete 5, I see that the in order successor will be 6. So we end up with the following tree:
6
/ \
3 7
/ \
1 4
\
2
8 and 9 just got orphaned.
Ants
January 19, 2012, January 19, 2012 03:27, permalink
No rating.
Login to rate!
Let's try this again, but in the code field where whitespace maybe significant:
I think there is a bug in the remove method.
Given a tree:
5
/ \
3 8
/ \ / \
1 4 6 9
\ \
2 7
Attempting to delete 5, I see that the in order successor will be 6. So we end up with the following tree:
6
/ \
3 7
/ \
1 4
\
2
8 and 9 just got orphaned.
hi,
so i'm still a new programmer (a few months of messing around with Java), and to practice I tried to write a binary search tree. It's my first one, so it can't be that good. I figured i should show my code to those who are better than I am. Any input would be great. I noticed I kept getting a warning for all the times where i used Comparable. I just suppressed them but idk if maybe there's a better way to go about solving that problem.
thanks