算法平衡K-D树与O（kn log n）

Question

我尝试使用O（kn log n）实现平衡的K-D树，我使用预先排序的K数组（每个索引的排序数组）得到O（kn log n），并使用中位数得到平衡树。

我面临的问题是，大多数某个级别的中值，例如x轴的中位数，可能会在另一个后续级别再次选择，例如y轴。

我试图通过使用选择的x值作为枢轴将y排序数组划分为两个数组来解决这个问题，但这种方式不会产生平衡树。

知道如何用O（kn log n）获得K-D平衡树吗？

编辑

来自wiki qazxsw poi的行情

用于构建平衡k-d树的替代算法在构建树之前预先分配数据。然后，它们在树木构造期间保持预分类的顺序，因此消除了在每个细分水平找到中值的昂贵步骤。两个这样的算法构建平衡的k-d树以对三角形进行排序，以便改善三维计算机图形的光线跟踪的执行时间。这些算法在构建k-d树之前预先分配n个三角形，然后在最佳情况下在O（n log n）时间内构建树。[5] [6]构建平衡k-d树以对点进行排序的算法具有最坏情况下的复杂度O（kn log n）。[7]在构建树之前，该算法使用诸如Heapsort或Mergesort之类的O（n log n）排序来预先分析k个维度中的每个k个点。然后它在树构造期间维持这些k预分类的顺序，从而避免在每个细分级别找到中值。

有人可以提供上面提供的算法吗？

编辑

想出了一种方法，但如果中位数的特定轴有任何重复值，它就不起作用。

例如

x1 = [（0,7），（1,3），（3,0），（3,1），（6,2）] y1 = [（3,0），（3,1），（6 ，2），（1,3），（0,7）]

x轴的中位数是3.因此，当我们想要分割数组y11和y12时，我们必须使用>和<来左右分布y数组，将pivot作为分隔符。

如果特定轴上的中位数a重复，则无法保证其中一个是正确的

考虑x轴上的分区，完成上面的第一步分区示例后，x1阵列上没有问题：

https://en.wikipedia.org/wiki/K-d_tree

这将导致y11 = [（2,1），（1,3），（0,7）] y12 = [（6,2）]

知道如何处理这种情况吗？或者是否还有其他预分类kd树预分类算法O（kn log n）？

Answer 1

详细说明我的评论（可能是

median=(3,0)
The pivot = 3 // is it's the median of x axis
y11[],y12[] 
for(i = 0 ; i < x1.size;i++)
  if(y1[i].getX()<pivot)
    y11.add(y1[i])
  else 
    if(y1[i].getX()>pivot)
     y12.add(y1[i])

）：

在构建KD树时预先排序的关键思想是在拆分期间保持顺序。开销看起来很高，重新排序（和k选择）的比较基准似乎是有序的。 一些原理证明Java源代码：

Anony-Mousse's answer

（没有在SE上找到合适的答案/实施而没有投入太多的精力。输出对你的例子来说是不可信的，对于更长的一个，我不得不重新格式化以相信它。 代码看起来很丑陋，很可能因为它是：如果如此倾向于重新阅读关于

package net.*.coder.greybeard.sandbox;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/** finger exercise pre-sorting & split for KD-tree construction
 *  (re. https://stackoverflow.com/q/35225509/3789665) */
public class KDPreSort {
 /** K-dimensional key, dimensions fixed
  *   by number of coordinates in construction */
    static class KKey {
        public static KKey[] NONE = {};
        final Comparable[]coordinates;
        public KKey(Comparable ...coordinates) {
            this.coordinates = coordinates;
        }
    /** @return {@code Comparator<KKey>} for coordinate {@code n}*/
        static Comparator<KKey> comparator(int n) { // could be cached
            return new Comparator<KDPreSort.KKey>() { @Override
                    public int compare(KKey l, KKey r) {
                        return l.coordinates[n]
                            .compareTo(r.coordinates[n]);
                    }
                };
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(
                Arrays.deepToString(coordinates));
            sb.setCharAt(0, '(');
            sb.setCharAt(sb.length()-1, ')');
            return sb.toString();
        }
    }

 // static boolean trimLists = true; // introduced when ArrayList was used in interface

/** @return two arrays of {@code KKey}s: comparing smaller than
 *    or equal to {@code pivot} (according to {@code comp)},
 *    and greater than pivot -
 *    in the same order as in {@code keys}. */
    static KKey[][] split(KKey[] keys, KKey pivot, Comparator<KKey> comp) {
        int length = keys.length;
        ArrayList<KKey>
            se = new ArrayList<>(length),
            g = new ArrayList<>(length);
        for (KKey k: keys) {
        // pick List to add to
            List<KKey>d = comp.compare(k, pivot) <= 0 ? se : g;
            d.add(k);
        }
//      if (trimLists) { se.trimToSize(); g.trimToSize(); }
        return new KKey[][] { se.toArray(KKey.NONE), g.toArray(KKey.NONE) };
    }
 /** @return two arrays of <em>k</em> arrays of {@code KKey}s:
  *  comparing smaller than or equal to {@code pivot}
  *   (according to {@code comp)}, and greater than pivot,
  *  in the same order as in {@code keysByCoordinate}. */
    static KKey[][][]
        splits(KKey[][] keysByCoordinate, KKey pivot, Comparator<KKey> comp) {
        final int length = keysByCoordinate.length;
        KKey[][]
            se = new KKey[length][],
            g = new KKey[length][],
            splits;
        for (int i = 0 ; i < length ; i++) {
            splits = split(keysByCoordinate[i], pivot, comp);
            se[i] = splits[0];
            g[i] = splits[1];
        }
        return new KKey[][][] { se, g };
    }
 // demo
    public static void main(String[] args) {
    // from https://stackoverflow.com/q/17021379/3789665
        Integer [][]coPairs = {// {0, 7}, {1, 3}, {3, 0}, {3, 1}, {6, 2},
                {12, 21}, {13, 27}, {19, 5}, {39, 5}, {49, 63}, {43, 45}, {41, 22}, {27, 7}, {20, 12}, {32, 11}, {24, 56},
            };
        KKey[] someKeys = new KKey[coPairs.length];
        for (int i = 0; i < coPairs.length; i++) {
            someKeys[i] = new KKey(coPairs[i]);
        }
    //presort
        Arrays.sort(someKeys, KKey.comparator(0));
        List<KKey> x = new ArrayList<>(Arrays.asList(someKeys));
        System.out.println("by x: " + x);
        KKey pivot = someKeys[someKeys.length/2];
        Arrays.sort(someKeys, KKey.comparator(1));
        System.out.println("by y: " + Arrays.deepToString(someKeys));
    // split by x
        KKey[][] allOrdered = new KKey[][] { x.toArray(KKey.NONE), someKeys },
            xSplits[] = splits(allOrdered, pivot, KKey.comparator(0));
        for (KKey[][] c: xSplits)
            System.out.println("split by x of " + pivot + ": "
                + Arrays.deepToString(c));
    // split "higher x" by y
        pivot = xSplits[1][1][xSplits[1][1].length/2];
        KKey[][] ySplits[] = splits(xSplits[1], pivot, KKey.comparator(1));
        for (KKey[][] c: ySplits)
            System.out.println("split by y of " + pivot + ": "
                + Arrays.deepToString(c));
    }
}

，请访问licence of code posted on SE。）（考虑有投票，接受和授予赏金，并重新访问Anony-Mousse的答案。）

Answer 2

拆分数据时，需要保留排序顺序。

例如。使用我们构建的数据Code Review

(x,y)

如果我们现在在x处拆分，我们需要通过

x1 = [ (0, 7), (1, 3), (3, 0), (4, 2), (6, 1) ]
y1 = [ (3, 0), (6, 1), (3, 2), (1, 3), (0, 7) ]

处的记录过滤这两个集合。

即拆分两个列表，删除x=3,y=0，所有带(3,0)的项目都转到第一个列表，所有用x<3转到第二个（订单不变）：

x>3

重点是按x值过滤每个排序列表，同时保持排序顺序（因此在每个O（log n）级别中都是O（n * k））。如果仅使用x1，并从x1重建y11和y12，则需要再次排序。必要时，它就像你用x排序一次，y一次排序。除了我们没有再次排序，只选择。

我不认为这在实践中好得多。排序比额外的内存便宜。