Class BalancedBSTTree

java.lang.Object
  |
  +--BSTTree
        |
        +--BalancedBSTTree

All Implemented Interfaces:

AnimatingTree, AnimationListener, DrawingTree, java.util.EventListener, Tree

public class BalancedBSTTree

extends BSTTree

This class provides the head structure for a BalancedBSTTree. Therefore, it overides all important methods necessary for maintaining a Balanced BST.

The Balance defines methods necessary for a BSTTreeHead, a DrawingBSTTreeHead, and an AnimatingBSTTreeHead. The type is set when the node is constructed but can be changed in the middle using methods found in BSTTree. If a method is called for a type that is higher is level than the type of the tree, the method will be ignored.

Note that this implementation is not synchronized. If multiple threads access this tree concurrently, and at least one of the threads modifies the tree structurally, it must be synchronized externally.

Field Summary

Fields inherited from class BSTTree

ANIMATING_BST_TREE_TYPE, BST_TREE_TYPE, DRAWING_BST_TREE_TYPE

Constructor Summary

BalancedBSTTree()
Constructs a new, null BalancedBSTTreeHead, sorted according to the keys' natural order and insertion occurs automatically to the root.

BalancedBSTTree(int treeType)
Constructs a new, empty BalancedBSTTreeHead according to the type passed.

Method Summary

protected void	insert(BSTTree newTree, int currentLevel) Inserts the given object into the tree, using recursive calls and is called from the Head node.
protected Tree	search(java.lang.Comparable keyFind) Finds a node within a tree using the comparable keyFind.

Methods inherited from class BSTTree

addAnimator, animationEventPerformed, constructAnimatingBSTTree, constructBSTTree, constructDrawingBSTTree, copyBSTTree, drawLeftLink, drawNode, drawNode, drawNode, drawNodeAndLeftLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndRightLink, drawRightLink, drawTree, eraseNodeAndLink, findNode, fixLevel, fixSize, fixTreeType, getAnimator, getChildren, getCurrentGraphics, getCurrentPower2, getCurrentShape, getCurrentTransform, getDrawingLevel, getHead, getInorderCount, getKey, getKeyOriginRectangle, getLeftTree, getLevel, getNodeOriginShape, getParentTree, getPreviousTransform, getRightTree, getScreenBounds, getSectionHeight, getSettings, getTreeType, getTreeTypeString, getValue, inTree, isAnimateDrawing, isAnimatingBSTTree, isDrawingBSTTree, isEmpty, isNodeAnimating, isSettingsSaved, join, makeInorderTree, makeInsertAnimation, makePostorderTree, makePreorderTree, makeSearchAnimation, makeSelectionAnimation, makeTree, partition, remove, restoreLeftSettings, restoreRightSettings, restoreSettings, restoreTransform, rotateLeft, rotateRight, saveLeftSettings, saveRightSettings, saveSettings, select, setAnimateDrawing, setCurrentGraphics, setCurrentPower2, setCurrentTransform, setDrawingLevel, setHead, setInorderCount, setLeaf, setLeftTree, setLevel, setNode, setNodeSettings, setParentTree, setRightTree, setScreenBounds, setSettings, setSize, setTreeSettings, setTreeType, size

Methods inherited from class java.lang.Object

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

Constructor Detail

BalancedBSTTree

public BalancedBSTTree()

Constructs a new, null BalancedBSTTreeHead, sorted according to the keys' natural order and insertion occurs automatically to the root.

Default type is BST_TREE_TYPE.

BalancedBSTTree

public BalancedBSTTree(int treeType)

Constructs a new, empty BalancedBSTTreeHead according to the type passed.

Parameters:

treeType - type of tree that should be implemented.

Method Detail

insert

protected void insert(BSTTree newTree,
                      int currentLevel)
               throws java.lang.ClassCastException

Inserts the given object into the tree, using recursive calls and is called from the Head node. This method is recursive until it finds a subtree that is null and sets the node.

Randomly (according to the probability set in the head) balances each node after passing in an insertion.

Overrides:

insert in class BSTTree

Parameters:

newTree - the tree to be inserted, with key and value already set.

currentLevel - keeps track of the recursive call, and sets the new level if it changes.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the tree.

search

protected Tree search(java.lang.Comparable keyFind)
               throws java.lang.ClassCastException

Finds a node within a tree using the comparable keyFind. Null is returned if the key is not within the tree and the node is returned otherwise. The method is a recursive call.

Overrides:

search in class BSTTree

Parameters:

keyFind - the key which the method is attempting to find.

Returns:

Tree which contains the keyFind as a key or the last examined tree if the keyFind is not present in the entire tree.

java.lang.ClassCastException