goldman.collection.ordered
Class BinarySearchTree.BSTNode

java.lang.Object
  extended by goldman.collection.ordered.AbstractSearchTree.TreeNode
      extended by goldman.collection.ordered.BinarySearchTree.BSTNode
Direct Known Subclasses:
RedBlackTree.RBNode
Enclosing class:
BinarySearchTree<E>

protected class BinarySearchTree.BSTNode
extends AbstractSearchTree.TreeNode


Field Summary
protected  E data
           
protected  BinarySearchTree.BSTNode left
           
protected  BinarySearchTree.BSTNode parent
           
protected  BinarySearchTree.BSTNode right
           
 
Constructor Summary
protected BinarySearchTree.BSTNode(E data)
           
 
Method Summary
protected  int capacity()
           
protected  BinarySearchTree.BSTNode child(int index)
           
protected  E data(int index)
           
protected  BinarySearchTree.BSTNode deleteAndReplaceBy(BinarySearchTree.BSTNode x)
          Replaces T(this) by T(x)
protected  BinarySearchTree.BSTNode grandparent()
          
REQUIRES: it is not called on the root
protected  boolean isFrontier()
           
protected  boolean isLeftChild()
          
REQUIRES: it is not called on the root
protected  BinarySearchTree.BSTNode replaceSubtreeBy(BinarySearchTree.BSTNode x)
          Replaces T(this) by T(x)
protected  BinarySearchTree.BSTNode sameSideChild()
          
REQUIRES: it is not called on the root.
protected  BinarySearchTree.BSTNode setLeft(BinarySearchTree.BSTNode x)
           
protected  BinarySearchTree.BSTNode setRight(BinarySearchTree.BSTNode x)
           
protected  BinarySearchTree.BSTNode sibling()
          
REQUIRES: it is not called on the root
protected  int size()
           
protected  void substituteNode(BinarySearchTree.BSTNode x)
          Replaces the node on which this method is called by x
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

data

protected E data

parent

protected BinarySearchTree.BSTNode parent

left

protected BinarySearchTree.BSTNode left

right

protected BinarySearchTree.BSTNode right
Constructor Detail

BinarySearchTree.BSTNode

protected BinarySearchTree.BSTNode(E data)
Parameters:
data - the element to be held in this node
Method Detail

size

protected final int size()
Specified by:
size in class AbstractSearchTree.TreeNode
Returns:
the number of elements held in this node

capacity

protected final int capacity()
Specified by:
capacity in class AbstractSearchTree.TreeNode
Returns:
the maximum number of elements this node can accommodate.

toString

public String toString()
Overrides:
toString in class Object

isFrontier

protected final boolean isFrontier()
Specified by:
isFrontier in class AbstractSearchTree.TreeNode
Returns:
true if and only if this node is a frontier node

data

protected final E data(int index)
Specified by:
data in class AbstractSearchTree.TreeNode
Parameters:
index - the desired index
Returns:
e_{index}
Throws:
IllegalArgumentException - index is not 0 since a binary search tree only holds a single element in each node
NoSuchElementException - this node is not in use

child

protected final BinarySearchTree.BSTNode child(int index)
Specified by:
child in class AbstractSearchTree.TreeNode
Parameters:
index - the index for the desired child
Returns:
C_{index}
Throws:
IllegalArgumentException - index is not 0 or 1

setLeft

protected final BinarySearchTree.BSTNode setLeft(BinarySearchTree.BSTNode x)
Parameters:
x - a reference to the node that is to become the left child of this node
Returns:
the possibly updated value of x

setRight

protected final BinarySearchTree.BSTNode setRight(BinarySearchTree.BSTNode x)
Parameters:
x - a reference to the node that is to become the right child of this node
Returns:
the possibly updated value of x

isLeftChild

protected final boolean isLeftChild()

REQUIRES: it is not called on the root

Returns:
true if and only if this node is a left child.

grandparent

protected final BinarySearchTree.BSTNode grandparent()

REQUIRES: it is not called on the root

Returns:
the grandparent of the node

sibling

protected final BinarySearchTree.BSTNode sibling()

REQUIRES: it is not called on the root

Returns:
the sibling of this node

sameSideChild

protected final BinarySearchTree.BSTNode sameSideChild()

REQUIRES: it is not called on the root.

Returns:
the left child of this node when it is a left child, and the right child of this node when it is a right child.

replaceSubtreeBy

protected BinarySearchTree.BSTNode replaceSubtreeBy(BinarySearchTree.BSTNode x)
Replaces T(this) by T(x)

Parameters:
x - a reference to a node
REQUIRES: T(left) ≤ x.element ≤ T(right)
Returns:
the possibly updated value of x

deleteAndReplaceBy

protected BinarySearchTree.BSTNode deleteAndReplaceBy(BinarySearchTree.BSTNode x)
Replaces T(this) by T(x)

Parameters:
x - a reference to a node
REQUIRES: T(left) ≤ x.element ≤ T(right)
Returns:
the possibly updated value of x

substituteNode

protected void substituteNode(BinarySearchTree.BSTNode x)
Replaces the node on which this method is called by x

Parameters:
x - a reference to a node
REQUIRES: T(left) ≤ x.element ≤ T(right)