edu.berkeley.guir.lib.graphs
Class BinarySearchTree

java.lang.Object
  |
  +--edu.berkeley.guir.lib.graphs.BinaryTree
        |
        +--edu.berkeley.guir.lib.graphs.BinarySearchTree

public class BinarySearchTree

extends BinaryTree

An tree that has at most two children per node ordered such that all values less than the root value will go to the left, and all values greater than the root value will go to the right.

It uses a Comparison object to determine where in the tree an object goes.

This software is distributed under the Berkeley Software License.

 Revisions:  - GUIRLib-v1.0-1.0.0, Nov 25 1997, JH
               Created class
             - GUIRLib-v1.0-1.1.0, Feb 24 2000, JH
               Updated for JDK1.3RC1 to use the Collections
             - GUIRLib-v1.2-1.0.0, Jun 22 2000, JH
               Touched for GUIRLib release
             - GUIRLib-v1.3-1.0.0, Aug 11 2000, JH
               Touched for GUIRLib release
             - GUIRLib-v1.4-1.0.0, Aug 31 2000, JH
               Touched for GUIRLib release
 

Since:

JDK 1.1.4

Version:

GUIRLib-v1.4-1.0.0, Aug 31 2000

Author:

Jason Hong ( jasonh@cs.berkeley.edu)

See Also:

Comparison, NumComparison

Fields inherited from class edu.berkeley.guir.lib.graphs.BinaryTree

data, left, right

Constructor Summary

BinarySearchTree()
Default constructor, creates an empty binary tree.

BinarySearchTree(Object data)
Creates a binary tree with the specified object at the root.

Method Summary

void	add(Object obj) Add an object to this tree starting with the current node as root.
protected Object	data() Get the data at the root of this BinarySearchTree.
boolean	exists(Object obj) See if the specified Object is in the tree or not.
boolean	existsHelper(Object obj, BinarySearchTree root) See if the specified Object is in the specified tree or not.
BinarySearchTree	left() Return the left subtree.
BinarySearchTree	right() Return the right subtree.
static void	setComparison(Comparison aCompare) Set the object that will be used to compare objects in this BinarySearchTree.
protected void	setData(Object obj) Set the data at the root of this BinarySearchTree.
static void	setDuplicateFlag(boolean flag) Allow duplicate values in the tree or not? By default, duplicate values are ignored.
void	setLeft(BinarySearchTree root)
static void	setOverwriteFlag(boolean flag) Overwrite duplicate values in the tree or not? By default, duplicate values are ignored.
void	setRight(BinarySearchTree root)

Methods inherited from class edu.berkeley.guir.lib.graphs.BinaryTree

_data, _left, _right, _setData, _setLeft, _setRight, equals, getNumberOfElements, inOrderTraversal, postOrderTraversal, preOrderTraversal, remove, toString

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Default constructor, creates an empty binary tree.

BinarySearchTree

public BinarySearchTree(Object data)

Creates a binary tree with the specified object at the root.

Parameters:

data - is the value for the root of this BinarySearchTree.

Method Detail

setComparison

public static void setComparison(Comparison aCompare)

Set the object that will be used to compare objects in this BinarySearchTree. To ensure the integrity of the tree, this method can only be called once - subsequent calls will be ignored.

Parameters:

aCompare - is the comparison object.

setOverwriteFlag

public static void setOverwriteFlag(boolean flag)

Overwrite duplicate values in the tree or not? By default, duplicate values are ignored.

Parameters:

flag - is the value to set for Duplicate.

setDuplicateFlag

public static void setDuplicateFlag(boolean flag)

Allow duplicate values in the tree or not? By default, duplicate values are ignored.

Parameters:

flag - is the value to set for Duplicate.

setData

protected void setData(Object obj)

Set the data at the root of this BinarySearchTree.

Parameters:

obj - is the object to add, which may not be null.

add

public void add(Object obj)

Add an object to this tree starting with the current node as root.

Overrides:

add in class BinaryTree

Parameters:

obj - is the object to add, which may not be null.

setLeft

public void setLeft(BinarySearchTree root)

setRight

public void setRight(BinarySearchTree root)

data

protected Object data()

Get the data at the root of this BinarySearchTree.

Returns:

an object stored at this tree's root.

exists

public boolean exists(Object obj)

See if the specified Object is in the tree or not. Depends on the implementation of method equals() for the objects.

Overrides:

exists in class BinaryTree

Parameters:

obj - is the Object to check for in the tree. If obj is null then true will be returned always.

Returns:

true if the Object is in the tree, false otherwise.

existsHelper

public boolean existsHelper(Object obj,
                            BinarySearchTree root)

See if the specified Object is in the specified tree or not. Depends on the implementation of method equals() for the objects.

Parameters:

obj - is the Object to check for in the tree. If obj is null then true will be returned always.

root - is the tree to check in.

Returns:

true if the Object is in the tree, false otherwise.

left

public BinarySearchTree left()

Return the left subtree.

Returns:

the left subtree of the current node.

right

public BinarySearchTree right()

Return the right subtree.

Returns:

the right subtree of the current node.