Opus5
Class BinarySearchTree

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractTree
                    |
                    +--Opus5.BinaryTree
                          |
                          +--Opus5.BinarySearchTree

All Implemented Interfaces:

Comparable, Container, SearchableContainer, SearchTree, Tree

Direct Known Subclasses:

AVLTree

public class BinarySearchTree

extends BinaryTree

implements SearchTree

A node in a binary search tree.

Version:

$Id: BinarySearchTree.java,v 3.3 1998/07/29 14:24:26 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner classes inherited from class Opus5.AbstractTree

AbstractTree.TreeEnumeration

Fields inherited from class Opus5.BinaryTree

key, left, right

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.SearchTree

copyright

Constructor Summary

BinarySearchTree()

Method Summary

void	attachKey(java.lang.Object object) Attaches the specified object as the key of this node.
protected void	balance() Balances this node.
Comparable	find(Comparable object) Returns the object in this binary search tree that matches the specified object.
Comparable	findMax() Returns the "largest" object in this binary search tree.
Comparable	findMin() Returns the "smallest" object in this binary search tree.
void	insert(Comparable object) Inserts the specified comparable object into this binary search tree.
boolean	isMember(Comparable object) Tests whether the specified comparable object is in this binary search tree.
void	withdraw(Comparable object) Withdraws the specified object from this binary search tree.

Methods inherited from class Opus5.BinaryTree

attachLeft, attachRight, compareTo, depthFirstTraversal, detachKey, detachLeft, detachRight, getDegree, getKey, getLeft, getRight, getSubtree, isEmpty, isLeaf, purge

Methods inherited from class Opus5.AbstractTree

accept, breadthFirstTraversal, getCount, getEnumeration, getHeight

Methods inherited from class Opus5.AbstractContainer

hashCode, isFull, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

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

Methods inherited from interface Opus5.Tree

breadthFirstTraversal, depthFirstTraversal, getDegree, getHeight, getKey, getSubtree, isEmpty, isLeaf

Methods inherited from interface Opus5.Container

accept, getCount, getEnumeration, isFull, purge

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Method Detail

isMember

public boolean isMember(Comparable object)

Tests whether the specified comparable object is in this binary search tree.

Specified by:

isMember in interface SearchableContainer

Parameters:

object - The object for which to look.

Returns:

True if the specified object is in this binary search tree; false otherwise.

find

public Comparable find(Comparable object)

Returns the object in this binary search tree that matches the specified object.

Specified by:

find in interface SearchableContainer

Parameters:

object - The object to match.

Returns:

The object in this binary search tree that matches the specified object; null if not found.

findMin

public Comparable findMin()

Returns the "smallest" object in this binary search tree. The smallest object is the object which is less than all the other objects in this tree.

Specified by:

findMin in interface SearchTree

Returns:

The "smallest" object in this binary search tree; null if this tree is empty.

findMax

public Comparable findMax()

Returns the "largest" object in this binary search tree. The largest object is the object which is greater than all the other objects in this tree.

Specified by:

findMax in interface SearchTree

Returns:

The "largest" object in this binary search tree; null if this tree is empty.

insert

public void insert(Comparable object)

Inserts the specified comparable object into this binary search tree.

Specified by:

insert in interface SearchableContainer

Parameters:

object - The object to be inserted.

Throws:

java.lang.IllegalArgumentException - If there already is a matching object in this tree.

attachKey

public void attachKey(java.lang.Object object)

Attaches the specified object as the key of this node. The node must be initially empty.

Overrides:

attachKey in class BinaryTree

Parameters:

object - The key to attach.

Throws:

InvalidOperationException - If this node is not empty.

balance

protected void balance()

Balances this node. Does nothing in this class.

withdraw

public void withdraw(Comparable object)

Withdraws the specified object from this binary search tree.

Specified by:

withdraw in interface SearchableContainer

Parameters:

object - The object to be withdrawn from this tree.

Throws:

java.lang.IllegalArgumentException - If the specified object is not in this tree.