TreeJuxtaposer
Class RangeTree

java.lang.Object
  |
  +--TreeJuxtaposer.RangeTree

public class RangeTree

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

Constructor Summary

RangeTree(TreeJuxtaposer.Point[] A, int dim)
Constructor: calls RangeTreeBuild to build the tree

RangeTree(Tree treeA, Tree treeB, TreeJuxtaposer.Tree2Tree t2t)
constructor: builds a 2D RangeTree data structure.

Method Summary

RangeNode	build2D(TreeJuxtaposer.Point[] A, int start, int end) builds a 2D range tree using points from A[start] to A[end].
int	getElement()
RangeNode	getRoot()
boolean	isEmpty()
static void	mergeSort(TreeJuxtaposer.Point[] A, int dim) This implements a regular merge sort algorithm.
int	query2D(int xlow, int xhigh, int ylow, int yhigh) Query2D returns the total number of points contained in the window [xlow, xhigh] X [ylow, yhigh].

Methods inherited from class java.lang.Object

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

Constructor Detail

RangeTree

public RangeTree(Tree treeA,
                 Tree treeB,
                 TreeJuxtaposer.Tree2Tree t2t)

constructor: builds a 2D RangeTree data structure. Given two trees, in the first step the constructor computes the total number of common nodes for these trees, and in the second step it extracts all the common nodes from these two trees and stores it into a data structure called nodes, and in the third step the constructor calls another function RangeTreeBuild to build the range tree using nodes.

Parameters:

treeA - the first tree

treeB - the second tree

t2t - we're using the function getBestCorrNode of class Tree2Tree

RangeTree

public RangeTree(TreeJuxtaposer.Point[] A,
                 int dim)

Constructor: calls RangeTreeBuild to build the tree

Parameters:

dim - dim = 0 represents a 2D range tree, dim = 1 represents a 1D range tree. This notation is not intuitive.

A - an array of points

Method Detail

isEmpty

public boolean isEmpty()

getRoot

public RangeNode getRoot()

Returns:

root

getElement

public int getElement()

Returns:

element

build2D

public RangeNode build2D(TreeJuxtaposer.Point[] A,
                         int start,
                         int end)

builds a 2D range tree using points from A[start] to A[end]. First build an array for the associated 1D tree, and then sort the array by Y coordinate, and create an associated tree by build1D. Seting children by calling the function recursively.

Parameters:

A - an array of points

start - the start position from the array

end - the end position from the array

query2D

public int query2D(int xlow,
                   int xhigh,
                   int ylow,
                   int yhigh)

Query2D returns the total number of points contained in the window [xlow, xhigh] X [ylow, yhigh]. If find a childless point in [xlow, xhigh], then check its Y coordinate. First check left side of split leaf, then the right side. If left is good, then all the right side is good too. if left is not good, go a little right.

Parameters:

xlow - the leftmost value of x coordinate

xhigh - the rightmost value of x coordinate

ylow - the lowest value of y coordinate

yhigh - the highest value of y coordinate

Returns:

the total number of points contained in the window range

mergeSort

public static void mergeSort(TreeJuxtaposer.Point[] A,
                             int dim)

This implements a regular merge sort algorithm. It is added as a static method, so no additional class is needed.

Parameters:

A - an array to be sorted

dim - the corresponding coordinate that sorting is based on