TreeNode (Interval Tree 1.0.0 API)

java.lang.Object
- com.lodborg.intervaltree.TreeNode<T>

Type Parameters:

T - The type for the start and end point of the interval

All Implemented Interfaces:

Iterable<Interval<T>>
```
public class TreeNode<T extends Comparable<? super T>>
extends Object
implements Iterable<Interval<T>>
```
A representation of a single node in the IntervalTree.
Since the Interval Tree is practically a binary search tree, every node is identified by a unique key - the center (called middlepoint) of the first interval that triggers the creation of this node. The key is immutable and can't be changed during the lifespan of this node. It can however move up or down in the tree as a result of balancing rotations, similarly to a normal balanced search tree. Unlike a traditional binary search tree, every node in the interval tree can store multiple intervals. The invariant is, that each node stores only intervals that contain its middlepoint.

There are several invariants that the TreeNode needs to keep. First, the subtrees rooted in each node are always kept balanced. Second, each node must contain at least one interval, otherwise the node must be removed from the tree to keep it as small as possible. Balancing is done by traditional binary search tree rotations.

Given an interval that needs to be found, inserted or removed from the tree, an augmented binary search algorithm is performed in the following fashion. For each visited node, check if the middlepoint of this node is contained in the query interval. If so, then this node is the position where the query interval must be stored. Otherwise, visit the left child, if the interval is entirely to the left of the middlepoint, or visit the right child otherwise.

Since intervals may contain middlepoints from multiple nodes in the tree, there are multiple valid locations where an interval may be stored based on the above augmented binary search algorithm. However, to ensure the optimal time complexity of the add, remove and contains operations, we define the base position of an interval (or base) as the node closest to root within the set of nodes, where the interval may be stored. To be able to guarantee the correctness of the algorithm, this invariant must be preserved after each tree operation. This is especially important, when tree rotations are performed. Whenever a node is promoted closer to the root as a result of a rotation, the promoted node must assimilate all intervals from the node demoted by the rotation. This ensures that whenever the binary search algorithm encounters a node, which is a valid location for a given interval, this node will be the base of the interval.

Since each node can store multiple intervals, we need an efficient way to perform intersecting queries (given a query in the form of a point or an interval, find all intervals intersecting the query). The TreeNode can't simply keep an ArrayList of all intervals stored in it, because it will have to linearly check each interval in the List. This can degrade the performance of the tree, especially in cases where a single node contains all intervals. Intervals have to be stored in an ordered way. Each node keeps its intervals in two TreeSets at the same time - one containing the intervals by their start points in ascending order and the other by the end points in descending order. Whenever we have to provide a set of all intervals contained within this node, that intersect a query point, we check if the query is left or right of the middlepoint of the node. If it is left, we iterate through the TreeSet ordered by the start points until we reach an interval completely to the right of the query. Analogously, if the query is to the right of the middlepoint, we iterate through the set ordered by the end points until we reach an interval that's completely to the left of the query. This allows us to only iterate through these intervals, that we will actually return as a result of the query.

Field Summary

Fields
Modifier and Type	Field and Description
`protected NavigableSet<Interval<T>>`	`decreasing` A set containing all `Interval`s stored in this node, ordered by their starting points.
`protected int`	`height` The height of the node.
`protected NavigableSet<Interval<T>>`	`increasing` A set containing all `Interval`s stored in this node, ordered by their end points.
`protected TreeNode<T>`	`left` A pointer to the left child of the current node.
`protected T`	`midpoint` The midpoint of the initial interval added to the node.
`protected TreeNode<T>`	`right` A pointer to the right child of the current node.

Constructor Summary

Constructors
Constructor and Description

TreeNode(Interval<T> interval)
Instantiates a new node in an IntervalTree.

Constructors
Constructor and Description
`TreeNode(Interval<T> interval)` Instantiates a new node in an `IntervalTree`.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`static <T extends Comparable<? super T>> TreeNode<T>`	`addInterval(IntervalTree<T> tree, TreeNode<T> root, Interval<T> interval)` Adds a new interval to the subtree rooted at a `TreeNode`.
`int`	`height()` Returns the height of the subtree, rooted at the current node.
`com.lodborg.intervaltree.TreeNode.TreeNodeIterator`	`iterator()` An iterator over all intervals stored in subtree rooted at the current node.
`static <T extends Comparable<? super T>> Set<Interval<T>>`	`query(TreeNode<T> root, T point, Set<Interval<T>> res)` A helper function for the `IntervalTree.query(Comparable)` method.
`static <T extends Comparable<? super T>> TreeNode<T>`	`removeInterval(IntervalTree<T> tree, TreeNode<T> root, Interval<T> interval)` A helper function for the `IntervalTree.remove(Interval)` method.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable
forEach, spliterator

- Field Detail
  - decreasing
```
protected NavigableSet<Interval<T extends Comparable<? super T>>> decreasing
```
    A set containing all Intervals stored in this node, ordered by their starting points.
    
    See Also:
    
    Interval.sweepLeftToRight
  - increasing
```
protected NavigableSet<Interval<T extends Comparable<? super T>>> increasing
```
    A set containing all Intervals stored in this node, ordered by their end points.
    
    See Also:
    
    Interval.sweepRightToLeft
  - left
```
protected TreeNode<T extends Comparable<? super T>> left
```
    A pointer to the left child of the current node. The left child must have a midpoint, smaller than the midpoint of the current node. More formally, left.midpoint.compareTo(this.midpoint) < 0 must evaluate to true.
  - right
```
protected TreeNode<T extends Comparable<? super T>> right
```
    A pointer to the right child of the current node. The right child must have a midpoint, larger than the midpoint of the current node. More formally, right.midpoint.compareTo(this.midpoint) > 0 must evaluate to true.
  - midpoint
```
protected final T extends Comparable<? super T> midpoint
```
    The midpoint of the initial interval added to the node. It is an immutable value and can not be changed, even if the initial interval has been removed from the node.
  - height
```
protected int height
```
    The height of the node.
- Constructor Detail
  - TreeNode
```
public TreeNode(Interval<T> interval)
```
    Instantiates a new node in an IntervalTree.
    
    Parameters:
    
    interval - The initial interval stored in the node. The middlepoint of the node will be set based on this interval.
- Method Detail
  - addInterval
```
public static <T extends Comparable<? super T>> TreeNode<T> addInterval(IntervalTree<T> tree,
                                                                        TreeNode<T> root,
                                                                        Interval<T> interval)
```
    Adds a new interval to the subtree rooted at a TreeNode.
    
    Type Parameters:
    
    T - The type of the start and end points of the interval.
    
    Parameters:
    
    tree - The IntervalTree containing the subtree. Used primarily for housekeeping, such as adjusting the size of the tree, if needed.
    
    root - The root of the subtree, to which we are adding a new interval.
    
    interval - The Interval that we are adding.
    
    Returns:
    
    The new root of the subtree. It may be different than the current root, if the subtree had to be rebalanced after the operation.
  - height
```
public int height()
```
    Returns the height of the subtree, rooted at the current node.
    
    Returns:
    
    The height of the subtree, rooted ad the current node. It will be 1, if the node is a leaf.
  - query
```
public static <T extends Comparable<? super T>> Set<Interval<T>> query(TreeNode<T> root,
                                                                       T point,
                                                                       Set<Interval<T>> res)
```
    A helper function for the IntervalTree.query(Comparable) method. It searches recursively for all intervals stored in the subtree rooted at the current node, that intersect a target point.
    
    Type Parameters:
    
    T - The type of the start and end points of the intervals, as well as the query point.
    
    Parameters:
    
    root - The root of the currently traversed subtree. May be null.
    
    point - The query point.
    
    res - The set used to store all intervals to be returned.
    
    Returns:
    
    The set of all intervals from the current subtree, containing the query.
  - removeInterval
```
public static <T extends Comparable<? super T>> TreeNode<T> removeInterval(IntervalTree<T> tree,
                                                                           TreeNode<T> root,
                                                                           Interval<T> interval)
```
    A helper function for the IntervalTree.remove(Interval) method. It searches recursively for the base node of a target interval and removes the interval from the base node, if it is stored there. This is a more efficient way to remove an interval from the tree, since it doesn't iterate through all intervals, but performs a binary search in O(logn).
    
    Type Parameters:
    
    T - The type of the start and end points of the intervals, as well as the query point.
    
    Parameters:
    
    tree - The IntervalTree containing the subtree. Used primarily for housekeeping, such as adjusting the size of the tree, if needed.
    
    root - The root of the currently traversed subtree. May be null.
    
    interval - The target interval to be removed.
    
    Returns:
    
    The new root of the subtree, rooted at the current node, after the interval has been removed. This could be null if the interval was the last one stored at the subtree.
  - iterator
```
public com.lodborg.intervaltree.TreeNode.TreeNodeIterator iterator()
```
    An iterator over all intervals stored in subtree rooted at the current node. Traversal is done via classic iterative in-order tree traversal where each iteration is in amortized O(1) time. The iterator requires O(logn) space - at each point of the traversal we keep a stack of the currently traversed branch of the tree.
    
    Specified by:
    
    iterator in interface Iterable<Interval<T extends Comparable<? super T>>>

Class TreeNode<T extends Comparable<? super T>>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Field Detail

decreasing

increasing

left

right

midpoint

height

Constructor Detail

TreeNode

Method Detail

addInterval

height

query

removeInterval

iterator