BinaryTree Class Reference

List of all members.

---

Detailed Description

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.

Public Member Functions
	BinaryTree (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.
String	toString ()
	Return a String which contains the tree represented in "landscape" form, running down the page.
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.
Object	insert (Object newObj)
	Insert an object in the tree if it is not already present.
Object	search (Object key)
	Search for an object in the tree that compares equal to key.
Object	delete (Object key)
	Search the tree for an object which compares equal to key.
int	size ()
	Return the number of data items (Objects) in the tree.
Private Member Functions
Node	unlink (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.
Object	delete (NodeReference root, Object key)
	This function searches a binary tree for "key" and deletes the item from the tree if it found.
Object	searchAndInsert (NodeReference root, Object key, boolean insert)
	Recursive tree search and insert.
String	spaces (int count)
	Return a string consisting of count spaces.
void	toString (NodeReference root, PrintStream ps, int indent)
	Recursively build up a "landscape" display for the tree (e.g., a tree running down the page).
void	toArray (Node root, Vector vec)
	Recursively traverse the tree (using inorder tranversal) and insert the Objects from the tree into a Vector.
Private Attributes
NodeReference	root
	root of the binary tree
int	mNodeCount
	Number of nodes in the binary tree.
Comparator	mCompare
	Object used to compare Objects in the tree.

---

Constructor & Destructor Documentation

BinaryTree.BinaryTree (  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. { root = new NodeReference(); mNodeCount = 0; mCompare = compareObj; } // BinaryTree

---

Member Function Documentation

Object BinaryTree.delete (  Object  key  )

Search the tree for an object which compares equal to key. If the object is found, delete it. { Object foundObj = delete( root, key ); return foundObj; } // delete

Object BinaryTree.delete (  NodeReference  root, Object  key )  [private]

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: The node is a leaf node (no children). In this case the node can simply be unlinked from the tree and returned. The node has one child. In this case, the node is replaced by its child node. 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. { Object retObj = null; if (root.ref != null) { // if (root->key > key) if (mCompare.compare(root.ref.getObj(), key) > 0) { retObj = delete(root.ref.getLeftRef(), key); } else if (mCompare.compare(root.ref.getObj(), key) < 0) { retObj = delete(root.ref.getRightRef(), key); } else { // the keys are equal, remove the node Node node = null; Node new_child = null; int num_children = 0; node = root.ref; retObj = root.ref.getObj(); // Count the children of the node if (root.ref.getLeft() != null) { num_children++; new_child = root.ref.getLeft(); } if (root.ref.getRight() != null) { num_children++; new_child = root.ref.getRight(); } switch (num_children) { case 0: root.ref = null; break; case 1: root.ref = new_child; // Replace the node with its child break; case 2: { Node treeNode = unlink(root.ref.getRightRef()); // Make sure we're not pointing to ourselves if (treeNode != root.ref.getRight()) { treeNode.setRight( root.ref.getRight() ); } // we know that treeNode is not the left node, so set the left // reference treeNode.setLeft( root.ref.getLeft() ); root.ref = treeNode; } break; } // switch mNodeCount--; } // keys are equal } // root != null return retObj; } // delete

Object BinaryTree.insert (  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. { Object foundObj = searchAndInsert( root, newObj, true ); return foundObj; } // insert

Object BinaryTree.search (  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. { Object foundObj = searchAndInsert( root, key, false ); return foundObj; } // search

Object BinaryTree.searchAndInsert (  NodeReference  root, Object  key, boolean  insert )  [private]

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. { Object retObj = null; if (root.ref == null && insert) { root.ref = new Node( key ); mNodeCount++; } else { // if root.ref.getObj() > key if (mCompare.compare(root.ref.getObj(), key) > 0) { searchAndInsert(root.ref.getLeftRef(), key, insert); // search left branch } // if root.ref.getObj() < key else if (mCompare.compare(root.ref.getObj(), key) < 0) { searchAndInsert(root.ref.getRightRef(), key, insert);// search right branch } else { // key == root.ref.getObj() retObj = root.ref.getObj(); } } return retObj; } // searchAndInsert

int BinaryTree.size (   )

Return the number of data items (Objects) in the tree. { return mNodeCount; }

String BinaryTree.spaces (  int  count  )  [private]

Return a string consisting of count spaces. { String result = ""; if (count > 0) { StringBuffer buf = new StringBuffer(); for (int i = 0; i < count; i++) { buf.append(' '); } result = buf.toString(); } return result; } // spaces

Object [] BinaryTree.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. { Vector vec = new Vector(); toArray( root.ref, vec ); return vec.toArray(); }

void BinaryTree.toArray (  Node  root, Vector  vec )  [private]

Recursively traverse the tree (using inorder tranversal) and insert the Objects from the tree into a Vector. { if (root != null) { toArray( root.getLeft(), vec ); vec.add( root.getObj() ); toArray( root.getRight(), vec ); } } // toArray

String BinaryTree.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. { ByteArrayOutputStream bos = new ByteArrayOutputStream(); PrintStream ps = new PrintStream( bos ); toString(root, ps, 0); return bos.toString(); } // toString

void BinaryTree.toString (  NodeReference  root, PrintStream  ps, int  indent )  [private]

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. { ps.print( spaces(indent) ); ps.println( root.ref.getObj().toString() ); if (root.ref.getLeft() != null) { toString( root.ref.getLeftRef(), ps, indent+4 ); } else if (root.ref.getRight() != null) { ps.println( spaces(indent+4) + "null" ); } if (root.ref.getRight() != null) { toString( root.ref.getRightRef(), ps, indent+4 ); } else if (root.ref.getLeft() != null) { ps.println( spaces(indent+4) + "null" ); } } // toString

Node BinaryTree.unlink (  NodeReference  root  )  [private]

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. { Node treeNode = null; NodeReference nodeRef; // move down the left branch, until the object pointed to by the node // reference has a null link. for (nodeRef = root; nodeRef.ref.getLeft() != null; nodeRef = nodeRef.ref.getLeftRef()) { /* nada */; } treeNode = nodeRef.ref; if (nodeRef.ref.getRight() != null) { nodeRef.ref = nodeRef.ref.getRight(); } else { nodeRef.ref = null; } return treeNode; } // unlink

---

Member Data Documentation

Comparator BinaryTree.mCompare [private]

Object used to compare Objects in the tree.

int BinaryTree.mNodeCount [private]

Number of nodes in the binary tree.

NodeReference BinaryTree.root [private]

root of the binary tree

---

The documentation for this class was generated from the following file:

• BinaryTree.java

---