scranton.tree
Class BinarySearchTree

java.lang.Object
  scranton.Linear1
      scranton.tree.RecursiveBinaryTreeViaLinear1
          scranton.tree.BinarySearchTree

All Implemented Interfaces:

RecursiveBinaryTree

public class BinarySearchTree

extends RecursiveBinaryTreeViaLinear1

Implements a binary search tree by extending RecursiveBinaryTreeViaLinear1.

Field Summary

(package private) java.util.Comparator

c The comparator that orders the binary search tree

Fields inherited from class scranton.Linear1

data, link

Constructor Summary

BinarySearchTree(java.util.Comparator c)
Constructs an empty binary search tree

BinarySearchTree(java.lang.Object root, BinarySearchTree left, BinarySearchTree right, java.util.Comparator c)
Constructs a non-empty binary search tree

Method Summary

void	clockwiseRotate() Perform a clockwise rotation around "this".
void	counterClockwiseRotate() Perform a counterClockwise rotation around "this".
Linear1	factory() Returns an empty binary search tree
void	graft(BinarySearchTree O) Graft the tree O to the current tree satisfying the search tree order given by the tree's comparator.
void	insert(java.lang.Object O) Accept an object for insertion in the binary search tree, embed it in a tree and call the graft process to insert it.
void	lrPromote() Performs a ccounterClockwise rotation around the left subchild of "this" before performing a clockwise rotation around "this".
void	rlPromote() Performs a clockwise rotation around the right subchild of "this" before performing a counterClockwise rotation around "this".

Methods inherited from class scranton.tree.RecursiveBinaryTreeViaLinear1

getRoot, graft, isEmpty, leftSubtree, prune, rightSubtree, setRoot, sideways, toString

Methods inherited from class scranton.Linear1

getData, getLink, setData, setLink

Methods inherited from class java.lang.Object

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

Field Detail

c

java.util.Comparator c

The comparator that orders the binary search tree

Constructor Detail

BinarySearchTree

public BinarySearchTree(java.util.Comparator c)

Constructs an empty binary search tree

Parameters:

c - The ordering comparator

BinarySearchTree

public BinarySearchTree(java.lang.Object root,
                        BinarySearchTree left,
                        BinarySearchTree right,
                        java.util.Comparator c)

Constructs a non-empty binary search tree

Parameters:

c - The ordering comparator

Method Detail

insert

public void insert(java.lang.Object O)

Accept an object for insertion in the binary search tree, embed it in a tree and call the graft process to insert it.

Parameters:

O - The object to be embedded into the root of a tree and inserted into the binary search tree

graft

public void graft(BinarySearchTree O)

Graft the tree O to the current tree satisfying the search tree order given by the tree's comparator.

Parameters:

O - The tree to be inserted.

factory

public Linear1 factory()

Returns an empty binary search tree

Overrides:

factory in class RecursiveBinaryTreeViaLinear1

Returns:

An empty Binary Search Tree

clockwiseRotate

public void clockwiseRotate()

Perform a clockwise rotation around "this". Preconditon: this.leftSubtree() exists

counterClockwiseRotate

public void counterClockwiseRotate()

Perform a counterClockwise rotation around "this". Preconditon: this.rightSubtree() exists

lrPromote

public void lrPromote()

Performs a ccounterClockwise rotation around the left subchild of "this" before performing a clockwise rotation around "this". Precondition: this.leftSubtree() and this.leftSubtree().rightSubtree() exist.

rlPromote

public void rlPromote()

Performs a clockwise rotation around the right subchild of "this" before performing a counterClockwise rotation around "this". Precondition: this.rightSubtree() and this.rightSubtree().leftSubtree() exist.