Design and Implementation: 2-D BST of Coordinates

A data structure that enables the storage and search of points in two-dimensional space. It is implemeneted as a binary tree, where the nodes are partitioned based on their coordinates. The partitioning is done based on a comparator that alternates between comparing the x- and y-coordinates of the points on each level.

Getting Started

To use the Coordinate Tree class in your own code, follow these steps:

1. Clone the project from GitHub.
2. Import the Coordinate Tree package.
3. Create a new instance of the Coordinate Tree class.
4. Insert points into the tree using the 'insert' method.
5. Search for points using the 'search' method.
6. Search for points within a range using the 'searchRange' method.

TwoDTree Class

Class Variables

TreeNode root: The root of the 2D tree

Methods

TwoDTree()
The default constructor initializes an empty TwoDTree.

TwoDTree(ArrayList points)
The parameterized constructor initializes a TwoDTree with a list of points.

• Parameters:
  • points: A list of points to be inserted into the TwoDTree.

insert(Point point)
Inserts a point into the TwoDTree.

• Parameters:
  • point: The point to be inserted into the tree.

search(Point point)
Searches for a point in the tree.

• Parameters:
  • point: The point to be searched for in the tree.
• Returns:
  • true if the point is found, false otherwise.

searchRange(Point point1, Point point2)
Searches for all points within a given range.

• Parameters:
  • point1: One corner of the range.
  • point2: The opposite corner of the range.
• Returns:
  • An ArrayList of all points within the given range.

Tree Node (Inner-Class)

The TreeNode class represents a node in the TwoDTree.

Class Variables

Point point: The point stored in this object.
TreeNode leftSubtree: The left subtree.
TreeNode rightSubtree: The right subtree.
Comparator currentLevelComparator: A comparator to make decisions on this level.
Comparator childLevelComparator: A comparator to make decisions on the child level.

Methods

TreeNode(Point point, Comparator meComp, Comparator childComp)
Constructs a new TreeNode with the given point and comparators.

• Parameters:
  • point: The point to be stored in the node.
  • meComp: The comparator used to make decisions on this level.
  • childComp: The comparator used to make decisions on the child level.

insert(Point point)
Inserts a point into the subtree, rooted at this node.

• Parameters:
  • point: The point to be inserted.

search(Point point)
Search for a point in the tree.

• Parameters:
  • point: The point to be inserted.
• Returns:
  • true if the point is found, false otherwise.

searchRange(Point point1, Point point2)
Search for the points within a given range of the tree.

• Parameters:
  • point1: The first point defining the search range.
  • point2: The second point defining the search range.
• Returns:
  • An ArrayList of Points within the search range.

searchRange(Point lowerLeft, Point upperRight, ArrayList results)
Helper method for recursively searching for points within a given range in the tree.

• Parameters:
  • lowerLeft: The lower left point defining the search range.
  • upperRight: The upper right point defining the search range.
  • results: The ArrayList of Points to add the POints found within the search range.
• Returns:
  • An ArrayList of Points within the search range.

XComparator Class

The XComparator class implements the Comparator interface, overrides the compare method, and returns an instance of XComparator.

Class Variables

XComparator xComparator: Creates an instance of XComparator.

Methods

compare(Point point1, Point point2)
Overrides the compare method of the Comparator interface to compare two points based on their x-coordinates.

• Parameters:
  • point1: the first point to compare.
  • point2: the second point to compare.
• Returns:
  • a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

getInstance()
Returns the singleton instance of XComparator.

• Returns:
  • the singleton instance of XComparator.

YComparator Class

The XComparator class implements the Comparator interface, overrides the compare method, and returns an instance of YComparator.

Class Variables

YComparator yComparator: Creates an instance of YComparator.

Methods

compare(Point point1, Point point2)
Overrides the compare method of the Comparator interface to compare two points based on their y-coordinates.

• Parameters:
  • point1: the first point to compare.
  • point2: the second point to compare.
• Returns:
  • a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

getInstance()
Returns the singleton instance of YComparator.

• Returns:
  • the singleton instance of YComparator.