brutil
Class BSTree

java.lang.Object
  |
  +--brutil.BSTree

All Implemented Interfaces:

Collection, Map, SortedMap

public class BSTree

extends java.lang.Object

implements SortedMap

Inner Class Summary

class	BSTree.BSTIterator
class	BSTree.Entry

Field Summary

int	level
protected BSTree.Entry	root

Constructor Summary

	BSTree()
protected	BSTree(BSTree.Entry root) Constructor, constructing a tree with one element as its root

Method Summary

void	clear() Clears out the contents of the Collection (optional operation)
boolean	containsKey(java.lang.Object key) Whether or not a specified mapping exists in the tree
protected BSTree.Entry	createEntry(BSTree.Entry parent, java.lang.Object key, java.lang.Object value)
protected java.util.Iterator	createIterator()
int	depth()
protected BSTree.Entry	findEntry(java.lang.Object key)
java.lang.Object	get(java.lang.Object key) Find an Object in the Tree, return the Node where object found or null if object is not found
int	getSize() return the size of the tree
protected void	initMemory()
int	inputDepth()
boolean	isEmpty() Returns true if the Collection contains no elements, false otherwise
java.util.Iterator	iterator() Return a binary search tree \iterator
protected BSTree.Entry	maxEntry(BSTree.Entry e)
java.lang.Object	maxKey() return Node with largest key
protected BSTree.Entry	minEntry(BSTree.Entry e)
java.lang.Object	minKey() return Node with the smallest key
protected BSTree.Entry	nextEntry(java.lang.Object entry)
java.lang.Object	nextKey(java.lang.Object key) Returns the smallest key that is greater than the specified key
protected BSTree.Entry	prevEntry(java.lang.Object entry)
java.lang.Object	prevKey(java.lang.Object key) Returns the greatest key that is smaller than the specified key
java.lang.Object	put(java.lang.Object key, java.lang.Object data) Insert the object accordingly maintaining the binary search tree structure
java.lang.Object	remove(java.lang.Object key) Find the object and delete it from the tree, return true after after deleting succesfully, return false otherwise
void	removeAll() remove all element in the tree
int	size() Default constructor, constructing an empty tree

Methods inherited from class java.lang.Object

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

Field Detail

root

protected BSTree.Entry root

level

public int level

Constructor Detail

BSTree

public BSTree()

BSTree

protected BSTree(BSTree.Entry root)

Constructor, constructing a tree with one element as its root

Parameters:

key - and associate data of a root node

Method Detail

size

public int size()

Default constructor, constructing an empty tree

Specified by:

size in interface Collection

Parameters:

none -

Returns:

new empty tree

isEmpty

public boolean isEmpty()

Description copied from interface: Collection

Returns true if the Collection contains no elements, false otherwise

Specified by:

isEmpty in interface Collection

clear

public void clear()

Description copied from interface: Collection

Clears out the contents of the Collection (optional operation)

Specified by:

clear in interface Collection

initMemory

protected void initMemory()

createEntry

protected BSTree.Entry createEntry(BSTree.Entry parent,
                                   java.lang.Object key,
                                   java.lang.Object value)

get

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

Find an Object in the Tree, return the Node where object found or null if object is not found

Specified by:

get in interface Map

Parameters:

Object - comparable

Returns:

the associate object. Return null if object not found

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object data)

Insert the object accordingly maintaining the binary search tree structure

Specified by:

put in interface Map

Parameters:

key - has to be Object comparable.

Throws:

ClassCastException - if the key is not comparable

remove

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

Find the object and delete it from the tree, return true after after deleting succesfully, return false otherwise

Specified by:

remove in interface Map

Parameters:

Object - comparable

Returns:

The object associate with the key

Throws:

ClassCastException - if key is not comparable

nextKey

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

Returns the smallest key that is greater than the specified key

Specified by:

nextKey in interface SortedMap

Parameters:

Object - comparable

Returns:

key object. return null if the specified key is the greatest or the tree is empty

Throws:

ClassCastException - if key is not comparable

prevKey

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

Returns the greatest key that is smaller than the specified key

Specified by:

prevKey in interface SortedMap

Parameters:

Object - comparable

Returns:

key Object. Return null if the specified key is smallest or the tree is empty

Throws:

ClassCastException - if key is not comparable

nextEntry

protected BSTree.Entry nextEntry(java.lang.Object entry)

prevEntry

protected BSTree.Entry prevEntry(java.lang.Object entry)

minEntry

protected BSTree.Entry minEntry(BSTree.Entry e)

maxEntry

protected BSTree.Entry maxEntry(BSTree.Entry e)

findEntry

protected BSTree.Entry findEntry(java.lang.Object key)

iterator

public java.util.Iterator iterator()

Return a binary search tree \iterator

Specified by:

iterator in interface SortedMap

Returns:

BSTIterator

createIterator

protected java.util.Iterator createIterator()

minKey

public java.lang.Object minKey()

return Node with the smallest key

Specified by:

minKey in interface SortedMap

Returns:

The smallest key. return null if the tree is empty

maxKey

public java.lang.Object maxKey()

return Node with largest key

Specified by:

maxKey in interface SortedMap

Returns:

The greatest key. return null if the tree is empty

containsKey

public boolean containsKey(java.lang.Object key)

Whether or not a specified mapping exists in the tree

Specified by:

containsKey in interface Map

Parameters:

Object - comparable

Returns:

a boolean value. True if the mapping exists, false otherwise.

Throws:

ClassCastException - if key is not comparable

removeAll

public void removeAll()

remove all element in the tree

Returns:

void

getSize

public int getSize()

return the size of the tree

Parameters:

Object - comparable

Returns:

boolean

depth

public int depth()

inputDepth

public int inputDepth()