DS Project

This repository was created for Data Structures course (Fall 2021 held at SBU - instructed by Dr.Abin) project called BankFinder.

Bank Finder Using Data Structures

Implementing KD-Tree and Trie-Tree Data Structures in a example application

About The Project

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 R print 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.

(back to top)

related linkes

K-dimensional tree in wikipedia

Trie tree in wikipedia