diff options
Diffstat (limited to 'meowpp/dsa/KD_Tree.h')
| -rw-r--r-- | meowpp/dsa/KD_Tree.h | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h index 0abc358..2e55d12 100644 --- a/meowpp/dsa/KD_Tree.h +++ b/meowpp/dsa/KD_Tree.h @@ -68,6 +68,48 @@ namespace meow{ void clear(); void reset(size_t _dimension); }; + /********************************************************* + @asciidoc + === meow:: *KD_Tree<Keys, Key, Value>* (C++ class) + .Description + `KD_Tree` is *K-dimension tree*, which is a dictionary(key->value). + Where the type if key is a *K-dimension vector* . + + .Template Request + * `Keys` should has `operator[]` to allow the KD_Tree access the k-dimensions + * `Key` should has `operator*`, `operator+` + + .Support Methods + * N <- numbers of element in the kd-tree + * K <- dimensions + * `Keys` is the tyepname of the vector + * `Key` is the typename of the element in the vector + * `Value` is the typename of value + [options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + |const|root|(size_t number)|size_t|very fast| + ||insert|(Key const& k, Value v)|void|O(1)|Insert a pair (k->v) + || build|()|void|O(KN logN) | Build the data structure(the `insert()` + method will not build the data structure immediately) + |const|query|(Keys const& point, int k)|Value|O(kN ^1-1/k^ ) | + Using Euclidean-Distance to find the k-nearest neighbor from `point` . + And return the corrosponding value + |const|query|(Keys const& point, int k)|std::vector<Value>|O(kN ^1-1/k^ ) | + Using Euclidean-Distance to find all the x-nearest neighbor from `point` , + where x <= k. And return an array of all the corrosponding value. + ||clear|()|O(1)|Clear all data + ||reset|(size_t dimension)|O(1)|Clear all data and then + set the this->dimension be `dimension` + |======================================================================= +NOTE: O(kN ^1-1/k^ ) is reference from wiki. + +`query()` and `rangeQuery()` will run `build()` first if you called `insert()` +before call them. And `build()` is very slow, so you should not use this class +as a dynamic tree + +''' +@asciidoc- + *********************************************************/ } #include "KD_Tree.hpp" |