Package com.github.basking2.sdsai

Class IntervalTree.RBNode

java.lang.Object

com.github.basking2.sdsai.IntervalTree.RBNode

Enclosing class:

IntervalTree<K extends Comparable<K>,V>

public class IntervalTree.RBNode
extends Object

How a tree is represented. The advantages to this internal class are: - Truly empty data structure state.
- We can avoid recursion when "appropriate."
- We can compute and save global info like tree size.

Field Summary

Fields

Modifier and Type	Field	Description
protected Interval<K>	interval	This is effectively the key, though order and indexing is done through Interval.getMin().
protected boolean	isBlack
protected K	key	The Interval.getMin() value used to order and index nodes in the Red Black tree.
protected IntervalTree<K,V>.RBNode	left
protected IntervalTree<K,V>.RBNode	parent
protected IntervalTree<K,V>.RBNode	right
protected V	value	A value associated with the interval.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	RBNode(boolean b)
protected	RBNode(Interval<K> interval, V value, IntervalTree<K,V>.RBNode parent)

Method Summary

Modifier and Type	Method	Description
void	copyData(IntervalTree<K,V>.RBNode that)	Copy data members (not tree structure members) from another RBNode.
void	deleteFixup()
protected void	insertFixup()
protected IntervalTree<K,V>.RBNode	max()
protected IntervalTree<K,V>.RBNode	min()
protected IntervalTree<K,V>.RBNode	predecessor()	Returns the predecessor to a node or RBNULL if there is none.
void	print(String s)
protected void	rotateLeft()	Returns the new "top" of the sub tree.
protected void	rotateRight()	Returns the new "top" of the sub tree.
protected void	setMax(K max)
protected IntervalTree<K,V>.RBNode	successor()	Returns the successor to a node or RBNULL if there is none.
void	updateMax()	Update the max value for this node, considering children that are not RBNULL and the interval.
void	updateMaxAncestry()	Walk up the tree until we are at an RBNULL node and update the max value.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

isBlack

protected boolean isBlack

key

protected K extends Comparable<K> key

The Interval.getMin() value used to order and index nodes in the Red Black tree.

interval

protected Interval<K extends Comparable<K>> interval

This is effectively the key, though order and indexing is done through Interval.getMin().

value

protected V value

A value associated with the interval.

parent

protected IntervalTree<K extends Comparable<K>,V>.RBNode parent

left

protected IntervalTree<K extends Comparable<K>,V>.RBNode left

right

protected IntervalTree<K extends Comparable<K>,V>.RBNode right

Constructor Details

RBNode

protected RBNode(boolean b)

RBNode

protected RBNode(Interval<K> interval,
 V value,
 IntervalTree<K,V>.RBNode parent)

Method Details

copyData

public void copyData(IntervalTree<K,V>.RBNode that)

Copy data members (not tree structure members) from another RBNode. NOTE: This may make the max invalid. The function updateMax() should be called.

Parameters:

that - The node to copy data from.

See Also:

• updateMax()

print

public void print(String s)

min

protected IntervalTree<K,V>.RBNode min()

max

protected IntervalTree<K,V>.RBNode max()

setMax

protected void setMax(K max)

successor

protected IntervalTree<K,V>.RBNode successor()

Returns the successor to a node or RBNULL if there is none.

predecessor

protected IntervalTree<K,V>.RBNode predecessor()

Returns the predecessor to a node or RBNULL if there is none. Reverse of successor function.

rotateRight

protected void rotateRight()

Returns the new "top" of the sub tree.

rotateLeft

protected void rotateLeft()

Returns the new "top" of the sub tree.

insertFixup

protected void insertFixup()

deleteFixup

public void deleteFixup()

updateMax

public void updateMax()

Update the max value for this node, considering children that are not RBNULL and the interval. If this node is also RBNULL, this does nothing.

updateMaxAncestry

public void updateMaxAncestry()

Walk up the tree until we are at an RBNULL node and update the max value.

See Also:

• updateMax()