arrays - O(kn log n) 的算法平衡 K-D 树

Question

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

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

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

知道如何用 O(kn log n) 得到 K-D 平衡树吗？

编辑

转自维基 https://en.wikipedia.org/wiki/K-d_tree

Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. Two such algorithms build a balanced k-d tree to sort triangles in order to improve the execution time of ray tracing for three-dimensional computer graphics. These algorithms presort n triangles prior to building the k-d tree, then build the tree in O(n log n) time in the best case.[5][6] An algorithm that builds a balanced k-d tree to sort points has a worst-case complexity of O(kn log n).[7] This algorithm presorts n points in each of k dimensions using an O(n log n) sort such as Heapsort or Mergesort prior to building the tree. It then maintains the order of these k presorts during tree construction and thereby avoids finding the median at each level of subdivision.

谁能提供上面提供的这样的算法？

编辑

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

例如

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 数组左右分布，并将枢轴作为分隔符。

如果特定轴上的中位数 a 重复，则不能保证其中之一是正确的

考虑x轴上的分区，完成上面第一步分区的例子后x1数组没有问题:

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])

这将导致 y11 = [(2 ,1) , (1, 3), (0, 7) ] y12 = [ (6,2) ]

知道如何处理这种情况吗？还是有其他预排序kd-tree预排序算法O(kn log n)？

Answer 1

详细说明我的评论(可能还有 Anony-Mousse's answer):

构建 KD 树时预排序的关键思想是在拆分过程中保持顺序。开销看起来相当高，与重新排序(和k-select)的比较基准似乎是有序的。
一些原理验证 Java 源代码:

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));
    }
}

(在没有投入太多精力的情况下，没有在 SE 上找到合适的答案/实现。您的示例的输出没有说服力，较长的示例，我不得不重新格式化才能相信它。
代码看起来很难看，很可能是因为它是:如果愿意，请重新阅读 licence of code posted on SE , 一访Code Review .)(考虑有投票、接受和奖励赏金，并重新访问 Anony-Mousse 的回答。)