Algorithm Analysis Project: R-Tree & K-D Tree

This repository contains Python implementations of two spatial data structures: R-Tree and K-D Tree.

We created this for our Algorithm Analysis project to understand how these algorithms work, test their performance, and visualize the results.

Contents

1. R-Tree (/RTree)

• Purpose: Used for indexing spatial objects (rectangles).
• Features:
  • Insertion with node splitting.
  • Range search (finding items in a query box).
  • Visualization using Matplotlib.

2. K-D Tree (/KDTree)

• Purpose: Used for organizing points in 2D space.
• Features:
  • Tree construction using median splitting.
  • K-Nearest Neighbors (k-NN) search.
  • Performance comparison (K-D Tree vs. Brute Force).
  • Visualization of the partitioning.

Requirements

You need Python 3 and the matplotlib library for visualizations.

pip install matplotlib

How to Run

Running R-Tree

1. Navigate to the RTree folder.
2. Run the test script:

   python test.py

3. The script will print the query time and save an image named rtree_visualization.png.

Running K-D Tree

1. Navigate to the KDTree folder.
2. Run the test script:

   python test.py

3. The script will show the speedup compared to brute force search and save an image named kdtree_visualization.png.

Visualization Examples

The code generates images to show how the data is structured:

• R-Tree: Shows the bounding boxes (MBRs) and the query area.
• K-D Tree: Shows the splitting lines and the nearest neighbors found.