net.cscott.jutil

Class RedBlackTree

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 `RBNode` is an element of this tree.

Constructor Summary
	RedBlackTree()
	RedBlackTree(Comparator c)

Method Summary
protected void	deleteNode(Node z)
protected void	insertNode(Node x)
protected void	leftRotate(Node x) Pivots around the edge (x,x.right).
static void	main(String[] args)
protected Node	makeNode(Object o) Factory method for `Node`.
protected void	rbDeleteFixup(Node x) Post delete fixup routine.
protected void	rightRotate(Node x) Pivots around the edge (x,x.left).
protected void	swapPositions(Node a, Node b)

Constructor Detail

Method Detail

leftRotate

protected void leftRotate(Node x)

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

Factory method for Node. Every construction of a Node takes place through this method; thus subclasses of RedBlackTree can associate new data with their own nodes by extending the Node class and overriding this method.

rbDeleteFixup

protected void rbDeleteFixup(Node x)

Post delete fixup routine.

rightRotate

protected void rightRotate(Node x)

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

swapPositions

protected void swapPositions(Node a, Node b)