z***u
发帖数: 105 | 1 用KDTree 在二维平面里来找某个query点附近最近的一点。请问如何处理这种特殊情况？
离query点x的最近的点*3在没有搜到的树杈上。因为从KDTree的root *1下来，会到左
半平面，它不会走到右半部分。
*1
*2 |
------------|
x | *3 |
a********8
发帖数: 1625 | 2 因为从KDTree的root *1下来，会到左
半平面，它不会走到右半部分。
你这步写错了 |
a********8
发帖数: 1625 | 3 第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
,此时不能排除右边。
先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
这样可以达到LogN的时间复杂度 |
z***u
发帖数: 105 | 4 非常感谢 ：）
point
【在 a********8 的大作中提到】
: 第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
: ,此时不能排除右边。
: 先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
: 到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
: 这样可以达到LogN的时间复杂度
|
z***u
发帖数: 105 | 5 有个想法，可不可以把所有的点按找离hyperplane 的距离排序呢？ 比如说每个
hyperplane 有两个map之类。
不知道值不值的这样做，有没有更好的数据结构？
point
【在 a********8 的大作中提到】
: 第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
: ,此时不能排除右边。
: 先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
: 到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
: 这样可以达到LogN的时间复杂度
|
o******h
发帖数: 1142 | 6 kd tree, segment tree, interval tree, 这些各种tree 有啥好的教材,易于面试实现
的？
求推荐
况？
【在 z***u 的大作中提到】
: 用KDTree 在二维平面里来找某个query点附近最近的一点。请问如何处理这种特殊情况？
: 离query点x的最近的点*3在没有搜到的树杈上。因为从KDTree的root *1下来，会到左
: 半平面，它不会走到右半部分。
: *1
: *2 |
: ------------|
: x | *3
|
