K-D Tree

An implementation of KD-Trees written in Go, by Rishit Chaudhary.

Supported Operations

1. Efficiently find the nearest neighbor for a given node
2. Find the node with the minimum value in a particular dimension
3. Add a node to the KD-Tree
4. Delete a node from the KD-Tree
5. Stringify the KD-Tree to visualize it
6. Encode the tree into bytes
7. Decode the tree from bytes

Note: I have used FlatBuffers to encode and decode the KD-Tree.

Tests

The tests cover all API usages and are a great place to start to understand how to use them.

References

I've listed below all the references I've used to learn about KD-Trees working on this project.

1. KD-Tree Nearest Neighbor Data Structure by Stable Sort
   1. Linked Java Implementation
2. Good KD Tree Visualization Fall 2019
   1. Alternate Link
3. Good KD Tree Visualization Spring 2019
4. K-D Tree: build and search for the nearest neighbor by Algokodabra
5. K-d Trees - Computerphile
6. Advanced Data Structures: K-D Trees by Niema Moshiri
7. Advanced Data Structures: KDT Grid Representation by Niema Moshiri
8. Advanced Data Structures: KDT Insertion Order and Balance by Niema Moshiri
9. Node Deletion in KD-Tree
   1. The last example in this video lecture has an error. I've described and corrected this in my test case.