Implementing a Range Tree 
In
General 
1D
Integer Point Example 
Input: A set of data points. 
jdsl.core.api.ObjectIterator 

Task:
Internally store the data. 
jdsl.core.ref.ArraySequence You might need to convert manually between container types (only once though): ObjectIterator oi; ArraySequence s = new ArraySequence(); while(oi.hasNext()) { s.insertLast(oi.nextObject()); } 

Input: An ordering for those data
points. 
jdsl.core.api.Comparator 
jdsl.core.ref.IntegerComparator 
Task: Sort the points. 
jdsl.core.algo.sorts.ArrayQuickSort Use the JDSL algorithms to sort your data (this is why we internally store our data as a jdsl.core.api.Sequence): IntegerComparator comp; ArrayQuickSort quickSort = new ArrayQuickSort(); quickSort.sort(s, comp); 

Underlying data structure: A
balanced binary tree. 
jdsl.core.api.BinaryTree 
jdsl.core.ref.NodeBinaryTree 
Task: Build the data structure recursively 
Place the middle point at the root of the tree. Recursively build the left and right children of this node with the first half and the second half of this sequence. The leaves will be marked as empty. See, for example, a balanced binary tree being built in the RangeSearch example.  
Input: A query range. 
(Note: 2D objects are defined already in JDSL, for example jdsl.geomobj.api.Rectangle2D defines a 2D range.)  Two points marking the minimum
and maximum values of the range. 
Task: Perform the query. 
Search the tree for the leftmost
and rightmost points in the range and then return the points inside
this range by querying the ArraySequence. 

Always remember to:

This page was last updated on  