|
JUtil | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.cscott.jutil.BinaryTree
net.cscott.jutil.RedBlackTree
public class RedBlackTree
A RedBlackTree
is a BinaryTree
that uses
red-black properties to maintain a balanced form.
Nested Class Summary | |
---|---|
protected class |
RedBlackTree.RBNode
A RedBlackTree.RBNode is an element of this tree. |
Nested classes/interfaces inherited from class net.cscott.jutil.BinaryTree |
---|
BinaryTree.Node |
Field Summary |
---|
Fields inherited from class net.cscott.jutil.BinaryTree |
---|
comp, NIL |
Constructor Summary | |
---|---|
RedBlackTree()
|
|
RedBlackTree(Comparator c)
|
Method Summary | |
---|---|
protected void |
deleteNode(BinaryTree.Node z)
Splices z out from this. |
protected void |
insertNode(BinaryTree.Node x)
Inserts z into some appropriate position in this . |
protected void |
leftRotate(BinaryTree.Node x)
Pivots around the edge (x,x.right). |
static void |
main(String[] args)
|
protected BinaryTree.Node |
makeNode(Object o)
Factory method for RedBlackTree.RBNode . |
protected void |
rbDeleteFixup(BinaryTree.Node x)
Post delete fixup routine. |
protected void |
rightRotate(BinaryTree.Node x)
Pivots around the edge (x,x.left). |
protected void |
swapPositions(BinaryTree.Node a,
BinaryTree.Node b)
Switches the positions of a and b
within this . |
Methods inherited from class net.cscott.jutil.BinaryTree |
---|
add, contains, dump, dump, maximum, maximum, minimum, minimum, remove, root, search, setLeft, setParent, setRight, setRoot, successor, test |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public RedBlackTree()
public RedBlackTree(Comparator c)
Method Detail |
---|
protected BinaryTree.Node makeNode(Object o)
RedBlackTree.RBNode
. Every construction of a
RedBlackTree.RBNode
takes place through this method; thus
subclasses of RedBlackTree
can associate new data
with their own nodes by extending the RedBlackTree.RBNode
class
and overriding this method.
makeNode
in class BinaryTree
protected void insertNode(BinaryTree.Node x)
BinaryTree
this
.
requires: (z.left == z.right == NIL)
modifies: this, z
From CLR, pg 251.
insertNode
in class BinaryTree
protected void swapPositions(BinaryTree.Node a, BinaryTree.Node b)
BinaryTree
a
and b
within this
. Subclasses are expected to swap any
data derived from the positions as well.
swapPositions
in class BinaryTree
protected void deleteNode(BinaryTree.Node z)
BinaryTree
z
out from this.
Based on CLR, pg 253.
modifies: this, z
deleteNode
in class BinaryTree
protected void rbDeleteFixup(BinaryTree.Node x)
protected void leftRotate(BinaryTree.Node x)
protected void rightRotate(BinaryTree.Node x)
public static void main(String[] args)
|
JUtil | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |