This repository was created for Data Structures course (Fall 2021 held at SBU - instructed by Dr.Abin) project called BankFinder.
Implementing KD-Tree and Trie-Tree Data Structures in a example application
Imagine we are living in a 2D planar world. There are a few banks in this world that are points in the plane. Each bank has a name and coordinates X and Y.
In this project a few neighborhoods and banks are given and there are some queries regarding the banks.
The program should be capable of:
- Adding a neighborhood: Given a name and coordinates of a rectangle a neighborhood is added.
- Adding a bank: Given the coordinates of the bank and a name the bank should be added if there has not been a bank at that coordinates before.
- Deleting banks: Given a coordinate if there exists a bank the program should delete it.
- Printing all banks that belong to a special neighborhood.
- Given the name of a specific bank print all branches of the banks having the same name.
- Given our current coordinates print the nearest bank available.
- Given our current coordinates and a radius
Rprint all of the banks within the circle - Given our current coordinates and the name of a bank print the nearest branch of that bank available
- Printing the bank with the most number of branches
Building a KD-tree has O(N.log(N)) time complexity and nearest neighbor search has O(log(N)) time complexity.
Used Trie for searching banks by their name which has O(W.L) time complexity where W is the number of the words and L is the average length of the words.
K-dimensional tree in wikipedia
Trie tree in wikipedia