blogspot.software_and_algorithms.stern_library.data_structure

Class DynamicIntervalTree.Node<U extends Comparable<U>,T extends Interval<U>>

java.lang.Object

blogspot.software_and_algorithms.stern_library.data_structure.RedBlackTree.Node<T>

blogspot.software_and_algorithms.stern_library.data_structure.DynamicIntervalTree.Node<U,T>

Enclosing class:

DynamicIntervalTree<U extends Comparable<U>,T extends Interval<U>>

protected static class DynamicIntervalTree.Node<U extends Comparable<U>,T extends Interval<U>>
extends RedBlackTree.Node<T>

A node for a dynamic interval tree is a red-black tree node augmented to store the maximum high and minimum low endpoints among intervals stored within the subtree rooted at the node.

Nested Class Summary

Nested classes/interfaces inherited from class blogspot.software_and_algorithms.stern_library.data_structure.RedBlackTree.Node

RedBlackTree.Node.NodeColor

Constructor Summary

Constructors

Constructor and Description
Node(T interval) Construct a new node associated with the specified interval.

Method Summary

Modifier and Type	Method and Description
protected void	computeSubtreeSpan() Compute the maximum high and minimum low endpoints among intervals stored within the subtree rooted at this node and correct values up the tree.
DynamicIntervalTree.Node<U,T>	getLeft() Get the left child.
DynamicIntervalTree.Node<U,T>	getParent() Get the parent.
DynamicIntervalTree.Node<U,T>	getRight() Get the right child.
U	getSubtreeSpanHigh()
U	getSubtreeSpanLow()
boolean	isClosedOnSubtreeSpanHigh()
boolean	isClosedOnSubtreeSpanLow()

Methods inherited from class blogspot.software_and_algorithms.stern_library.data_structure.RedBlackTree.Node

getColor, getValue, isLeaf, setColor, setLeft, setParent, setRight, setValue

Methods inherited from class java.lang.Object

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

Constructor Detail

Node

public Node(T interval)

Construct a new node associated with the specified interval.

Parameters:

interval - the interval with which this node is associated.

Method Detail

computeSubtreeSpan

protected void computeSubtreeSpan()

Compute the maximum high and minimum low endpoints among intervals stored within the subtree rooted at this node and correct values up the tree.

getLeft

public DynamicIntervalTree.Node<U,T> getLeft()

Get the left child.

Overrides:

getLeft in class RedBlackTree.Node<T extends Interval<U>>

Returns:

the left child, possibly null.

getParent

public DynamicIntervalTree.Node<U,T> getParent()

Get the parent.

Overrides:

getParent in class RedBlackTree.Node<T extends Interval<U>>

Returns:

the parent, possibly null.

getRight

public DynamicIntervalTree.Node<U,T> getRight()

Get the right child.

Overrides:

getRight in class RedBlackTree.Node<T extends Interval<U>>

Returns:

the right child, possibly null.

getSubtreeSpanHigh

public U getSubtreeSpanHigh()

getSubtreeSpanLow

public U getSubtreeSpanLow()

isClosedOnSubtreeSpanHigh

public boolean isClosedOnSubtreeSpanHigh()

isClosedOnSubtreeSpanLow

public boolean isClosedOnSubtreeSpanLow()