net.cscott.jutil
Class RedBlackTree

java.lang.Object
  net.cscott.jutil.BinaryTree
      net.cscott.jutil.RedBlackTree

Direct Known Subclasses:

IntervalTree

public class RedBlackTree
extends BinaryTree

A RedBlackTree is a BinaryTree that uses red-black properties to maintain a balanced form.

See Also:

"CLR section 14, (page 263)."

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

RedBlackTree

public RedBlackTree()

RedBlackTree

public RedBlackTree(Comparator c)

Method Detail

makeNode

protected BinaryTree.Node makeNode(Object o)

Factory method for 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.

Overrides:

makeNode in class BinaryTree

insertNode

protected void insertNode(BinaryTree.Node x)

Description copied from class: BinaryTree

Inserts z into some appropriate position in this. requires: (z.left == z.right == NIL) modifies: this, z From CLR, pg 251.

Overrides:

insertNode in class BinaryTree

swapPositions

protected void swapPositions(BinaryTree.Node a,
                             BinaryTree.Node b)

Description copied from class: BinaryTree

Switches the positions of a and b within this. Subclasses are expected to swap any data derived from the positions as well.

Overrides:

swapPositions in class BinaryTree

deleteNode

protected void deleteNode(BinaryTree.Node z)

Description copied from class: BinaryTree

Splices z out from this. Based on CLR, pg 253. modifies: this, z

Overrides:

deleteNode in class BinaryTree

rbDeleteFixup

protected void rbDeleteFixup(BinaryTree.Node x)

Post delete fixup routine.

See Also:

"CLR, pg. 274"

leftRotate

protected void leftRotate(BinaryTree.Node x)

Pivots around the edge (x,x.right). Assumes x.right != null.

rightRotate

protected void rightRotate(BinaryTree.Node x)

Pivots around the edge (x,x.left). Assumes x.left != NIL.

main

public static void main(String[] args)