KD树-对不平衡KD树的最近邻居搜索

Question

我仍然对kd树有些困惑。

因此，大多数在线教程都说，从点列表中，我们通过每次（递归）选择中位数作为根节点来构造树。但是，对于我正在上学的pset，我们没有给出几点建议。一次给我们一点，并告诉我们这棵树“不需要平衡”。

很好，但是相信我确实需要一种算法来确定我最近的邻居时树中的中值节点。但是，如果树不平衡，我不确定该怎么做。

基本上，我对使用不平衡的kdtree进行此操作的整个过程感到困惑。（我在c上班）。

谢谢

Answer 1

您收到的第一个节点是根。然后相应地插入。

---

我产生了数字0..9的随机排序

3, 2, 6, 1, 7, 8, 0, 9, 5, 4

让我们依次插入它们：

3：

+---+
| 3 |
+---+

2：

    +---+
    | 3 |
    +---+
   /
+---+
| 2 |
+---+

6：

    +---+
    | 3 |
    +---+
   /     \
+---+   +---+
| 2 |   | 6 |
+---+   +---+

1：

        +---+
        | 3 |
        +---+
       /     \
    +---+   +---+
    | 2 |   | 6 |
    +---+   +---+
   /
+---+
| 1 |
+---+

...：

             +---+
             | 3 |
             +---+
        ____/     \____
       /               \
    +---+             +---+
    | 2 |             | 6 |
    +---+             +---+
   /                 /     \
+---+             +---+   +---+
| 1 |             | 5 |   | 7 |
+---+             +---+   +---+
                 /             \
              +---+           +---+
              | 5 |           | 8 |
              +---+           +---+
                                   \
                                  +---+
                                  | 9 |
                                  +---+

由于我们不平衡，所以它比需要的高度高。但是，情况可能更糟。如果最初对节点进行了排序，那么我们将最终得到一条直线（实际上是一个链表）。