/k-dimensional-trees

Primary LanguageJava

k-dimension-trees

This project involves the implementation of a geometric application using binary search trees, specifically 2D trees, to manage and analyze crime data from Pittsburgh during the 1990s. The primary goal is to create a 2D tree structure that stores crime records and supports various tree traversal and query operations.

Key Skills and Technologies:

  • Java Programming: Development of multiple Java classes (TwoDTree.java, Queue.java, Stack.java, ListOfCrimes.java, Neighbor.java, TwoDTreeDriver.java) to manage the 2D tree, implement traversals, and handle user interaction.
  • Data Structures: In-depth use of binary search trees, linked lists, queues, and stacks.
  • Algorithms: Implementation of tree traversal algorithms (pre-order, in-order, post-order, level-order, and reverse level-order) and range search algorithms.
  • Geospatial Data Analysis: Calculation of distances using the Pythagorean theorem and handling of geospatial coordinates for GIS applications.
  • Big Theta Analysis: Performance analysis of tree traversal methods.
  • File I/O: Reading and parsing CSV files to load crime data into the tree.
  • KML (Keyhole Markup Language): Generation of KML files to visualize crime data in Google Earth.

Achievements:

  • Successfully constructed a 2D tree to store over 27,000 crime records, allowing efficient querying and manipulation of spatial data.
  • Developed methods to perform various tree traversals and visualized the data structure effectively.
  • Implemented a range search function to find and display crimes within a specified rectangle, aiding in spatial analysis.
  • Created a nearest neighbor search algorithm to locate the closest crime to a given point.
  • Generated KML files to represent crime data for visualization in Google Earth, enhancing the understanding of crime patterns.
  • Conducted runtime analysis to ensure the efficiency of tree traversal operations, providing insights into the performance of the implemented algorithms.

This project provided a comprehensive understanding of binary search trees and their applications in managing and analyzing large datasets, particularly in a geospatial context.