Add KD Trees

[czgdp1807]

Description of the problem

K dimensional trees is a quite important data structure for storing high dimensional data. This issue aims at adding the same. The task is planned to be completed in two phases, first we will add static k-d trees and in the second phase we will add, dynamic k-d trees.

API Design and Class Hierarchy Overview

Static k-d trees - These trees will be built on a given data and once built, it will not be possible to modify it. The class name for such trees is, StaticKDTree. It will support the following operations:

1. __new__ - Meant for building the tree.
2. nearest_neighbour
3. find_min
4. find_max
5. search

Dynamic k-d trees - These trees will be built on a given data and it will be possible to modify the tree. The class name for such trees is, DynamicKDTree. In addition to the operations supported by static k-d trees, the following operations will be supported,

1. insert
2. delete
3. balance

Example of the problem

References/Other comments

[1] https://en.wikipedia.org/wiki/K-d_tree [2] https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf

[nikipr1999]

Please assign this issue to me for rgsoc20

[czgdp1807]

@nikipr1999 Though for RGSoC, 2020 making contributions isn't necessary till 31st March as the official coding period starts from July. Till then submit your application on RGSoC website. You can discuss the API design of KD Trees if you have some improvements to suggest over the one given in the description of this issue. I have also created a PR which you continue if you want to. See, #48

[kichloo]

@czgdp1807 Can you pl restore the gssoc label as there are 10 more days now for RGSOC but it can be contributed by GSSOC. Pl assign me this! I will complete asap.

[czgdp1807]

Hi @kichloo You can start working on this issue. You can continue, https://github.com/codezonediitj/pydatastructs/pull/48 Please see our issue policy for getting to know how to work on issues.

[subhangi2731]

can you please assign it to me?