APIdia Launch Partner

Top Fields Constructors Methods

sun.jvm.hotspot.utilities

public Class RBTree

Class Inheritance

extends Object

java.lang.Object
sun.jvm.hotspot.utilities.RBTree

Known Direct Subclasses

sun.jvm.hotspot.utilities.IntervalTree

Imports

java.io.PrintStream, java.util.Comparator, .Random

Field Summary

Modifier and Type	Field and Description
private Comparator<Object>	comparator
protected static final boolean	DEBUGGING
protected static final boolean	REALLY_VERBOSE
private RBNode	root
protected static final boolean	VERBOSE

Constructor Summary

Access	Constructor and Description
public	RBTree(Comparator<Object> comparator)

Method Summary

Modifier and Type	Method and Description
private void	deleteFixup(RBNode x, RBNode xParent) Restores red-black property to tree after splicing out node during deletion.
public void	deleteNode(RBNode z) FIXME: this does not work properly yet for augmented red-black trees since it doesn't update nodes.
protected Object	getNodeValue(RBNode node)
public RBNode	getRoot()
public void	insertNode(RBNode x)
private boolean	leftRotate(RBNode x) Returns true if updates must continue propagating up the tree
public static void	main(String[] args)
public void	print()
private void	printFromNode(RBNode node, PrintStream tty, int indentDepth) Debugging
public void	printOn(PrintStream tty)
private boolean	rightRotate(RBNode y) Returns true if updates must continue propagating up the tree
private void	treeInsert(RBNode z)
private RBNode	treeMinimum(RBNode x)
private RBNode	treeSuccessor(RBNode x)
protected void	verify() Verify invariants are preserved
private int	verifyFromNode(RBNode node)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

comparator	back to summary
private Comparator<Object> comparator

DEBUGGING	back to summary
protected static final boolean DEBUGGING

REALLY_VERBOSE	back to summary
protected static final boolean REALLY_VERBOSE

root	back to summary
private RBNode root

VERBOSE	back to summary
protected static final boolean VERBOSE

Constructor Detail

RBTree	back to summary
public RBTree(Comparator<Object> comparator)

Method Detail

deleteFixup	back to summary
private void deleteFixup(RBNode x, RBNode xParent) Restores red-black property to tree after splicing out node during deletion. Note that x may be null, which is why xParent must be specified.

deleteNode	back to summary
public void deleteNode(RBNode z) FIXME: this does not work properly yet for augmented red-black trees since it doesn't update nodes. Need to figure out exactly from which points we need to propagate updates upwards.

getNodeValue	back to summary
protected Object getNodeValue(RBNode node)

getRoot	back to summary
public RBNode getRoot()

insertNode	back to summary
public void insertNode(RBNode x)

leftRotate	back to summary
private boolean leftRotate(RBNode x) Returns true if updates must continue propagating up the tree

main	back to summary
public static void main(String[] args)

print	back to summary
public void print()

printFromNode	back to summary
private void printFromNode(RBNode node, PrintStream tty, int indentDepth) Debugging

printOn	back to summary
public void printOn(PrintStream tty)

rightRotate	back to summary
private boolean rightRotate(RBNode y) Returns true if updates must continue propagating up the tree

treeInsert	back to summary
private void treeInsert(RBNode z)

treeMinimum	back to summary
private RBNode treeMinimum(RBNode x)

treeSuccessor	back to summary
private RBNode treeSuccessor(RBNode x)

verify	back to summary
protected void verify() Verify invariants are preserved

verifyFromNode	back to summary
private int verifyFromNode(RBNode node)