Class BinaryTree

java.lang.Object
  |
  +--BinaryTree

public class BinaryTree

extends java.lang.Object

This class supports insertion and deletion of elements in a simple binary tree (e.g., the tree is not a balanced tree like an AVL tree or a red-black tree). Relative to a particular node, nodes on the left are less than the node and nodes on the right are greater.

The Java class library includes the java.util.TreeMap class which is a balanced Red-Black tree which is recommended over this code. As with this class, the TreeMap class supports both insertion and deletion.

This class is not intended as a replacement for the TreeMap class. It was written to some degree as an excercise and demonstration. It uses a classic binary tree algorthm for both insert and delete. In contrast to the TreeMap algorithm, which uses left, right and parent references, this class uses only left and right references. As a result, this algorithm mirrors similar binary tree algorithms that might be implemented in C, C++, Pascal, or Modula-X.

This code is an interesting example of the problems that can be encountered in Java, where only pass-by-value is supported. The classic tree delete algorithm, which depends on pass by reference becomes much more awkward. A reference object is used in this code, which supports indirection. Since all references are made through the reference object, the code is more difficult to write and to understand that it would be for a language like C++ which supports reference arguments.

This object is not synchronized, so it is not safe for multi-threaded use.

Nested Class Summary

private class	BinaryTree.Node A binary tree node, where the associated data item is a generic Object.
private class	BinaryTree.NodeReference A container for a reference

Field Summary

private java.util.Comparator	mCompare Object used to compare Objects in the tree
private int	mNodeCount Number of nodes in the binary tree
private BinaryTree.NodeReference	root root of the binary tree

Constructor Summary

BinaryTree(java.util.Comparator compareObj)
The constructor is initialized with an instance of the Comparator interface, which supports the compare() method which is used to compare objects in the tree with a search key.

Method Summary

private java.lang.Object	delete(BinaryTree.NodeReference root, java.lang.Object key) This function searches a binary tree for "key" and deletes the item from the tree if it found.
java.lang.Object	delete(java.lang.Object key) Search the tree for an object which compares equal to key.
java.lang.Object	insert(java.lang.Object newObj) Insert an object in the tree if it is not already present.
java.lang.Object	search(java.lang.Object key) Search for an object in the tree that compares equal to key.
private java.lang.Object	searchAndInsert(BinaryTree.NodeReference root, java.lang.Object key, boolean insert) Recursive tree search and insert.
int	size() Return the number of data items (Objects) in the tree
private java.lang.String	spaces(int count) Return a string consisting of count spaces.
java.lang.Object[]	toArray() Return an ordered array of tree objects, where Object values (as determined by the Comparator object used to initialize the BinaryTree constructor) increase with the array indices (e.g., the smallest value is at index 0, the largest value is at index n.
private void	toArray(BinaryTree.Node root, java.util.Vector vec) Recursively traverse the tree (using inorder tranversal) and insert the Objects from the tree into a Vector.
java.lang.String	toString() Return a String which contains the tree represented in "landscape" form, running down the page.
private void	toString(BinaryTree.NodeReference root, java.io.PrintStream ps, int indent) Recursively build up a "landscape" display for the tree (e.g., a tree running down the page).
private BinaryTree.Node	unlink(BinaryTree.NodeReference root) When a value is removed from an ordered binary tree and the value has two children, it will be replaced by the next value in the right sub-branch which is greater.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

root

private BinaryTree.NodeReference root

root of the binary tree

mNodeCount

private int mNodeCount

Number of nodes in the binary tree

mCompare

private java.util.Comparator mCompare

Object used to compare Objects in the tree

Constructor Detail

BinaryTree

public BinaryTree(java.util.Comparator compareObj)

The constructor is initialized with an instance of the Comparator interface, which supports the compare() method which is used to compare objects in the tree with a search key. The equals() method of the Comparator interface is not used and should return false.

Method Detail

unlink

private BinaryTree.Node unlink(BinaryTree.NodeReference root)

When a value is removed from an ordered binary tree and the value has two children, it will be replaced by the next value in the right sub-branch which is greater. This value will be the last (leaf) value in the left branch of the right branch sub-tree. The right sub-tree node is the argument to this function.

The unlink function walks down a sub-tree's left branch until it gets to the end (the leaf node). It removes the value at the end of the branch and returns it (so it can be inserted into the "hole" left by the deleted value). If the value at the end of the left branch has a right branch child, this value replaces the terminal left branch node.

Returns:

either the Node referenced by root (if root has no left branch) or the Node at the end of the left branch.

delete

private java.lang.Object delete(BinaryTree.NodeReference root,
                                java.lang.Object key)

This function searches a binary tree for "key" and deletes the item from the tree if it found. The ordering of the tree is maintained (see below). If "key" is found, the Object will be returned. If "key" is not found, the function returns null.

When the node is found in the tree there are three possible cases:

1. The node is a leaf node (no children). In this case the node can simply be unlinked from the tree and returned.
2. The node has one child. In this case, the node is replaced by its child node.
3. The node has two children. In this case the node is replaced by the least value from the right branch. This value is found by taking the right branch, and then walking down the left branch (see the unlink function, above). The value found this way should be the next greatest value in the tree.

searchAndInsert

private java.lang.Object searchAndInsert(BinaryTree.NodeReference root,
                                         java.lang.Object key,
                                         boolean insert)

Recursive tree search and insert.

The tree is constructed of unique items. If an item is already present in the tree, key will not be inserted, even though insert may be true.

Parameters:

root - the root of the current subtree.

key - this object contains the key value being searched for.

insert - if this flag is true, key will be inserted into the tree if it is not already present.

Returns:

if an object in the tree that matches key is found, return a reference to this object. Otherwise return null.

spaces

private java.lang.String spaces(int count)

Return a string consisting of count spaces.

toString

private void toString(BinaryTree.NodeReference root,
                      java.io.PrintStream ps,
                      int indent)

Recursively build up a "landscape" display for the tree (e.g., a tree running down the page). When one of the children of a node is null (but not both) a null is added so that it is possible to see whether a child is a left or right child.

toString

public java.lang.String toString()

Return a String which contains the tree represented in "landscape" form, running down the page. The tree children are indented from the parents to show the tree structure.

Overrides:

toString in class java.lang.Object

toArray

private void toArray(BinaryTree.Node root,
                     java.util.Vector vec)

Recursively traverse the tree (using inorder tranversal) and insert the Objects from the tree into a Vector.

toArray

public java.lang.Object[] toArray()

Return an ordered array of tree objects, where Object values (as determined by the Comparator object used to initialize the BinaryTree constructor) increase with the array indices (e.g., the smallest value is at index 0, the largest value is at index n.

insert

public java.lang.Object insert(java.lang.Object newObj)

Insert an object in the tree if it is not already present.

Returns:

if the object is not found in the tree, return null. Otherwise return the object in the tree.

search

public java.lang.Object search(java.lang.Object key)

Search for an object in the tree that compares equal to key.

Returns:

If the object is found in the tree, return a reference to the object. Otherwise return null.

delete

public java.lang.Object delete(java.lang.Object key)

Search the tree for an object which compares equal to key. If the object is found, delete it.

size

public int size()

Return the number of data items (Objects) in the tree