KD-Tree“列表中位数”构建

Question

我已经使用"median of list"算法编写了Java中的KD树，用于构建更平衡的树。在使用维基提供的数据时，它似乎工作正常，请注意维基百科示例仅使用X，Y值，因此它不会评估Z深度。

维基百科：

point_list = [(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)] 

从my java program：

depth=0 id=(7.0, 2.0, 0.0) 
├── [left] depth=1 id=(5.0, 4.0, 0.0) 
│ ├── [left] depth=2 id=(2.0, 3.0, 0.0) 
│ └── [right] depth=2 id=(4.0, 7.0, 0.0) 
└── [right] depth=1 id=(9.0, 6.0, 0.0) 
    └── [left] depth=2 id=(8.0, 1.0, 0.0) 

但是，当我使用的方法 “列表中位数” 这个数据，它似乎并没有好好工作。

point list = [(1,0,-1), (1,0,-2), (1,0,1), (1,0,2)] 

我得到一棵树是这样的：

depth=0 id=(1.0, 0.0, 1.0) 
├── [left] depth=1 id=(1.0, 0.0, -2.0) 
│ └── [left] depth=2 id=(1.0, 0.0, -1.0) 
└── [right] depth=1 id=(1.0, 0.0, 2.0) 

看起来并不正确，因为（1.0，0.0，2.0）是右边（1.0，0.0，1.0），但它们是基本上相等，因为它们的Y值相等。此外，（1.0，0.0，-1.0）在（1.0，0.0，-2.0）的左边，它应该在右边，因为它的Z值更大。

我认为问题源于具有相等的X和Y值以及只有变量Z值，因此列表的中位数并不能准确地分割列表。

...原代码以下wiki的Python代码...

private static KdNode createNode(List<XYZPoint> list, int k, int depth) { 
    if (list == null || list.size() == 0) return null; 

    int axis = depth % k; 
    if (axis == X_AXIS) Collections.sort(list, X_COMPARATOR); 
    else if (axis == Y_AXIS) Collections.sort(list, Y_COMPARATOR); 
    else Collections.sort(list, Z_COMPARATOR); 

    KdNode node = null; 
    if (list.size() > 0) { 
     int mediaIndex = list.size()/2; 
     node = new KdNode(k, depth, list.get(mediaIndex)); 
     if ((mediaIndex - 1) >= 0) { 
      List<XYZPoint> less = list.subList(0, mediaIndex); 
      if (less.size() > 0) { 
       node.lesser = createNode(less, k, depth + 1); 
       node.lesser.parent = node; 
      } 
     } 
     if ((mediaIndex + 1) <= (list.size() - 1)) { 
      List<XYZPoint> more = list.subList(mediaIndex + 1, list.size()); 
      if (more.size() > 0) { 
       node.greater = createNode(more, k, depth + 1); 
       node.greater.parent = node; 
      } 
     } 
    } 

    return node; 
} 

...根据我的意见的新代码...

private static KdNode createNode(List<XYZPoint> list, int k, int depth) { 
    if (list == null || list.size() == 0) return null; 

    int axis = depth % k; 
    if (axis == X_AXIS) Collections.sort(list, X_COMPARATOR); 
    else if (axis == Y_AXIS) Collections.sort(list, Y_COMPARATOR); 
    else Collections.sort(list, Z_COMPARATOR); 

    KdNode node = null; 
    if (list.size() > 0) { 
     int medianIndex = list.size()/2; 
     node = new KdNode(k, depth, list.get(medianIndex)); 
     List<XYZPoint> less = new ArrayList<XYZPoint>(list.size()-1); 
     List<XYZPoint> more = new ArrayList<XYZPoint>(list.size()-1); 
     //Process list to see where each non-median point lies 
     for (int i=0; i<list.size(); i++) { 
      if (i==medianIndex) continue; 
      XYZPoint p = list.get(i); 
      if (KdNode.compareTo(depth, k, p, node.id)<=0) { 
       less.add(p); 
      } else { 
       more.add(p); 
      } 
     } 
     if (less.size() > 0) { 
      node.lesser = createNode(less, k, depth + 1); 
      node.lesser.parent = node; 
     } 
     if (more.size() > 0) { 
      node.greater = createNode(more, k, depth + 1); 
      node.greater.parent = node; 
     } 
    } 

Answer 1

的问题确实有做相等的坐标，并从您将节点拆分为less和more部分的方式出现。既然你有中值索引，为什么不使用索引进行分割而不是检查坐标？从

if (KdNode.compareTo(depth, k, p, node.id)<=0) { 

线116上只是改变了条件createNode到

if (i<medianIndex) { 

顺便说一句：有更有效的算法，以划分一个列表转换成低，中位数，比排序上。 （上下部分不需要排序！参见例如在C++ stdlib中实现std::nth_element - 对不起，我对Java编程有很大的了解）

Answer 2

我认为这个问题的基本问题是：什么，确切地说，你想用KD树吗？

• 如果您只想使用X和Y距离查找最近点，那么您拥有的算法非常好 - 您会发现至少有四个点中的一个与XY距离相等你的榜样。
• 如果要查找全部 XY距离中的最近点，则仍然保持KD树的构建函数相同，但只需将查找函数中的所有'<'运算符更改为'< ='。如果您正好在查询点处发现KD树点，则仍然需要下降该树的任意子节点，直到找到叶子为止。然后像KD树一样往树上往上走，如果它可能匹配到目前为止找到的最短距离，总是从兄弟树下降。
• 如果您想使用涉及X，Y和Z坐标的距离，您需要使您的树为三维KD树，X，Y和Z层交替（或潜在地用一些聪明的方案来选择下一个要细分的维度）。