structure
Class RedBlackTree
java.lang.Object
structure.RedBlackTree
public class RedBlackTree
- extends java.lang.Object
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait |
left
protected RedBlackTree left
right
protected RedBlackTree right
parent
protected RedBlackTree parent
value
protected java.lang.Comparable value
isRed
protected boolean isRed
EMPTY
public static final RedBlackTree EMPTY
RedBlackTree
protected RedBlackTree()
- Postcondition:
- construct the EMPTY tree; leaves have EMPTY as children
RedBlackTree
public RedBlackTree(java.lang.Comparable v)
- Precondition:
- v is a non-null Comparable
- Postcondition:
- constructs a single node red-black tree
isRed
protected boolean isRed()
- Postcondition:
- returns whether or not this node is red
isBlack
protected boolean isBlack()
- Postcondition:
- returns whether or not this node is red
setRed
protected void setRed()
- Postcondition:
- sets this node red
setRed
protected void setRed(boolean isRed)
- Postcondition:
- sets this node red or black, depending on boolean isRed
setBlack
protected void setBlack()
- Postcondition:
- sets this node black
value
protected java.lang.Object value()
- Postcondition:
- return the value associated with this node
left
protected RedBlackTree left()
- Postcondition:
- returns the tree rooted at left; may not be valid red-black
right
protected RedBlackTree right()
- Postcondition:
- returns the tree rooted a right; may not be valid red-black
parent
protected RedBlackTree parent()
- Postcondition:
- returns the parent of this tree
setParent
protected void setParent(RedBlackTree newParent)
- Postcondition:
- sets parent of this node - even if EMPTY
setLeft
protected void setLeft(RedBlackTree newLeft)
- Precondition:
- newLeft is a non-null RedBlackTree node, possibly EMPTY
- Postcondition:
- does nothing to the EMPTY node;
else makes newLeft a left child of this,
and this newLeft's parent
setRight
protected void setRight(RedBlackTree newRight)
- Precondition:
- newRight is a non-null RedBlackTree node, possibly EMPTY
- Postcondition:
- does nothing to the EMPTY node;
else makes newRight a right child of this,
and this newRight's parent
isLeftChild
protected boolean isLeftChild()
- Precondition:
- this node not EMPTY or root
- Postcondition:
- returns true iff this child is a left child
isRightChild
protected boolean isRightChild()
- Precondition:
- this node not EMPTY or root
- Postcondition:
- returns true iff this child is a left child
isEmpty
public boolean isEmpty()
- Postcondition:
- returns whether or not this child contains data
isRoot
protected boolean isRoot()
- Postcondition:
- returns whether or not this node has a parent
root
protected RedBlackTree root()
- Precondition:
- this node not EMPTY
- Postcondition:
- returns the root of the tree holding this node
rotateRight
protected void rotateRight()
- Precondition:
- this node has a left subtree
- Postcondition:
- rotates local portion of tree so left child is root
rotateLeft
protected void rotateLeft()
- Precondition:
- this node has a right subtree
- Postcondition:
- rotates local portion of tree so right child is root
add
public RedBlackTree add(java.lang.Comparable c)
- Precondition:
- c is a non-null Comparable value
- Postcondition:
- adds a comparable value to the red-black tree;
returns the modified tree
insert
protected RedBlackTree insert(java.lang.Comparable c)
- Precondition:
- c is a non-null Comparable value
- Postcondition:
- c is inserted into search tree rooted at this
redFixup
public void redFixup()
- Precondition:
- this node is a red node; if parent is red, violates property
- Postcondition:
- red nodes of the tree are adjusted to maintain properties
remove
public RedBlackTree remove(java.lang.Comparable c)
- Precondition:
- c is non-null
- Postcondition:
- the value is removed; resulting tree is returned
blackFixup
protected void blackFixup()
- Precondition:
- a black node has just been removed above this;
this node is the root of a black-height balanced tree, but
the ancestors of this node are shy one black node on this branch
- Postcondition:
- the tree is black-height balanced
contains
public boolean contains(java.lang.Comparable c)
- Precondition:
- c is non-null
- Postcondition:
- returns true iff c is contained within the tree
locate
protected RedBlackTree locate(java.lang.Comparable c)
- Precondition:
- c is non-null
- Postcondition:
- returns a node of this tree that contains c, or null
get
public java.lang.Comparable get(java.lang.Comparable c)
- Precondition:
- c is non-null
- Postcondition:
- returns a c-equivalent value from tree, or null
consistency
public boolean consistency()
- Postcondition:
- returns true if this node is consistently structured
blackHeight
protected int blackHeight()
- Precondition:
- tree is black-height balanced
- Postcondition:
- returns the black height of this subtree
redConsistency
protected boolean redConsistency()
- Postcondition:
- returns true if no red node in subtree has red children
blackConsistency
protected boolean blackConsistency()
- Postcondition:
- returns true if black properties of tree are correct
consistentlyBlackHeight
protected boolean consistentlyBlackHeight(int height)
- Postcondition:
- checks to make sure that the black height of tree is height
wellConnected
public boolean wellConnected(RedBlackTree expectedParent)
print
public void print()
hashCode
public int hashCode()
- Overrides:
hashCode in class java.lang.Object
- Postcondition:
- computes hash code associated with values of tree
toString
public java.lang.String toString()
- Overrides:
toString in class java.lang.Object
- Precondition:
- returns string representation of red-black tree