AccordionTreeDrawer
Class ColorTree

java.lang.Object
  |
  +--AccordionTreeDrawer.ColorTree

public class ColorTree

extends java.lang.Object

A class representing a two-dimensional orthogonal range tree. RangeTree is a class that can answer range query in time (log n)^2. It implements the data structure of 2D range tree. Nodes of this tree are objects of type RangeNode.

Author:

Yunhong Zhou

See Also:

RangeNode, Tree2Tree, AccordionDrawer.Tree, AccordionDrawer.TreeNode

Field Summary

(package private) int	element
(package private) ColorNode	root

Constructor Summary

ColorTree(RangeList list)
Constructor: calls RangeTreeBuild to build the tree

Method Summary

(package private) ColorNode	build1D(RangeInTree[] A, int start, int end) builds a 1D range tree using points from A[start] to A[end].
RangeInTree	findSplitRangeNode(ColorNode v, RangeInTree range) Find a RangeInSequence
ColorNode	getRoot()
boolean	isEmpty()
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

root

ColorNode root

element

int element

Constructor Detail

ColorTree

public ColorTree(RangeList list)

Constructor: calls RangeTreeBuild to build the tree

Method Detail

isEmpty

public boolean isEmpty()

getRoot

public ColorNode getRoot()

Returns:

root

build1D

ColorNode build1D(RangeInTree[] A,
                  int start,
                  int end)

builds a 1D range tree using points from A[start] to A[end]. Assume the A is sorted by Y coordinate. This will set the elemnt of the leaf(Y coordinate).

Parameters:

A - a list of points

start - the start position from array A

end - the end position from array A

findSplitRangeNode

public RangeInTree findSplitRangeNode(ColorNode v,
                                      RangeInTree range)

Find a RangeInSequence

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object