笙亿网络策划

DSA Kd Trees 怎么实现？数据结构与算法中的 Kd-Tree 构建和查询方法有哪些？

约 49 分钟读完 41 阅
文章导读
Previous Quiz Next K-D 是一种多维二叉搜索树。它被定义为用于存储多键记录的数据结构。该结构已被实现用于解决统计学和数据分析中的多种“几何”问题。
📋 目录
  1. 壹 K-D 树的特性
  2. 贰 K-D 树上的操作
  3. 叁 K-D 树的构建
  4. 肆 K-D 树中的删除操作
  5. 伍 K-D 树上的搜索操作
  6. 陆 K-D 树的时序复杂度
  7. 柒 K-D 树的应用
  8. 捌 结论
A A

数据结构中的 K 维 (K-D) 树

Previous
Quiz
Next

K-D 是一种多维二叉搜索树。它被定义为用于存储多键记录的数据结构。该结构已被实现用于解决统计学和数据分析中的多种“几何”问题。

k-d 树（k 维树的简称）被定义为一种空间划分数据结构，用于组织k 维空间中的点。k-d 树数据结构被应用于多种场景，例如涉及多维搜索键的搜索（例如范围搜索和最近邻搜索）。k-d 树被视为二叉空间划分树的一种特殊情况。

K-D 树的特性

以下是 k-d 树的特性：

  • k-d 树的深度为 O(log n)，其中 n 是点的数量。
  • 树中的每个节点包含一个 k 维点以及指向左右子节点的指针。
  • 树每个层级的轴选择遵循轴的循环顺序。
  • 每个层级的轴选择会影响树在搜索速度方面的性能。

K-D 树上的操作

以下是可以在 k-d 树上执行的操作：

  • Insert(x)：将点 x 插入 k-d 树。
  • Delete(x)：从 k-d 树中删除点 x。
  • Search(x)：在 k-d 树中搜索点 x。

K-D 树的构建

K-D 树的构建通过使用递归分区来完成。构建 K-D 树的步骤如下：

  • 选择分割平面的轴。
  • 选择中位数作为 pivot 元素。
  • 将点分割成两个集合：一个集合包含小于中位数的点，另一个集合包含大于中位数的点。
  • 对左右子树重复上述步骤。

现在，让我们编写构建 K-D 树的代码：

构建 K-D 树和插入操作的代码

我们通过执行 insert operation 来构建 K-D 树。

以下是在 C、C++、Java 和 Python 中构建 K-D 树的示例代码：

C C++ Java Python 
#include <stdio.h>
#include <stdlib.h>

// 用于表示 k-d 树节点的结构
struct Node {
   int point[2];
   struct Node *left, *right;
};

// 创建新节点函数
struct Node* newNode(int arr[]) {
   struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
   temp->point[0] = arr[0];
   temp->point[1] = arr[1];
   temp->left = temp->right = NULL;
   return temp;
}

// 插入新节点函数
struct Node* insertNode(struct Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return newNode(point);

   unsigned cd = depth % 2;

   if (point[cd] < (root->point[cd]))
      root->left = insertNode(root->left, point, depth + 1);
   else
      root->right = insertNode(root->right, point, depth + 1);

   return root;
}

// 构建 k-d 树函数
struct Node* constructKdTree(int points[][2], int n) {
   struct Node* root = NULL;
   for (int i = 0; i < n; i++)
      root = insertNode(root, points[i], 0);
   return root;
}

// 打印 k-d 树函数（前序遍历）
void printKdTree(struct Node* root) {
   if (root == NULL)
      return;
   printf("(%d, %d)\n", root->point[0], root->point[1]);
   printKdTree(root->left);
   printKdTree(root->right);
}

// 主函数
int main() {
   int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
   int n = sizeof(points) / sizeof(points[0]);
   struct Node* root = constructKdTree(points, n);
   printKdTree(root);
   return 0;
}

输出

(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)

// C++ 程序用于构建 k-d 树
#include <iostream>
using namespace std;

// 用于表示 k-d 树节点的结构
struct Node {
   int point[2];
   Node *left, *right;
};

// 创建新节点函数
Node* newNode(int arr[]) {
   Node* temp = new Node;
   temp->point[0] = arr[0];
   temp->point[1] = arr[1];
   temp->left = temp->right = NULL;
   return temp;
};

// 插入新节点函数
Node* insertNode(Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return newNode(point);

   unsigned cd = depth % 2;

   if (point[cd] < (root->point[cd]))
      root->left = insertNode(root->left, point, depth + 1);
   else
      root->right = insertNode(root->right, point, depth + 1);

   return root;
}

// 构建 k-d 树函数
Node* constructKdTree(int points[][2], int n) {
   Node* root = NULL;
   for (int i = 0; i < n; i++)
      root = insertNode(root, points[i], 0);
   return root;
}

// 打印 k-d 树函数
void printKdTree(Node* root) {
   if (root == NULL)
      return;
   cout << "(" << root->point[0] << ", " << root->point[1] << ")" << endl;
   printKdTree(root->left);
   printKdTree(root->right);
}

// 主函数
int main() {
   int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
   int n = sizeof(points) / sizeof(points[0]);
   Node* root = constructKdTree(points, n);
   printKdTree(root);
   return 0;
}

输出

以下是上述代码的输出：

(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)

// Java 程序用于构建 k-d 树
class Node {
   int[] point;
   Node left, right;
   Node(int[] point) {
      this.point = point;
      this.left = this.right = null;
   }
}

public class KdTree {
   Node root;

   Node insertNode(Node root, int[] point, int depth) {
      if (root == null)
         return new Node(point);

      int cd = depth % 2;

      if (point[cd] < root.point[cd])
         root.left = insertNode(root.left, point, depth + 1);
      else
         root.right = insertNode(root.right, point, depth + 1);

      return root;
   }

   Node constructKdTree(int[][] points) {
      for (int i = 0; i < points.length; i++)
         root = insertNode(root, points[i], 0);
      return root;
   }

   void printKdTree(Node root) {
      if (root == null)
         return;
      System.out.println("(" + root.point[0] + ", " + root.point[1] + ")");
      printKdTree(root.left);
      printKdTree(root.right);
   }

   public static void main(String[] args) {
      int[][] points = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
      KdTree tree = new KdTree();
      tree.constructKdTree(points);
      tree.printKdTree(tree.root);
   }
}

输出

以下是上述代码的输出：

(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)

# Python 程序用于构建 k-d 树
class Node:
   def __init__(self, point):
      self.point = point
      self.left = None
      self.right = None

def insertNode(root, point, depth):
    if root is None:
        return Node(point)
    
    cd = depth % 2
    
    if point[cd] < root.point[cd]:
        root.left = insertNode(root.left, point, depth + 1)
    else:
        root.right = insertNode(root.right, point, depth + 1)
    
    return root

def constructKdTree(points):
    root = None
    for point in points:
        root = insertNode(root, point, 0)
    return root

def printKdTree(root):
    if root is None:
        return
    print("(", root.point[0], ", ", root.point[1], ")")
    printKdTree(root.left)
    printKdTree(root.right)

points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]]
root = constructKdTree(points)
printKdTree(root)

输出

以下是上述代码的输出：

(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)

K-D 树中的删除操作

k-d 树中的删除操作通过以下步骤执行：

  • 找到要删除的节点。
  • 如果该节点是叶子节点，直接删除。
  • 如果该节点只有一个子节点，用其子节点替换该节点。
  • 如果该节点有两个子节点，找到该节点的中序后继，用中序后继替换该节点，然后删除中序后继。

从 K-D 树中删除节点的代码

以下是从 k-d 树中删除节点的 C、C++、Java 和 Python 示例代码：

C C++ Java Python 
// 从 k-d 树中删除节点的 C 程序
#include <stdio.h>
#include <stdlib.h>

// 表示 k-d 树节点的结构体
struct Node {
   int point[2];
   struct Node *left, *right;
};

// 创建新节点函数
struct Node* newNode(int arr[]) {
   struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
   temp->point[0] = arr[0];
   temp->point[1] = arr[1];
   temp->left = temp->right = NULL;
   return temp;
}

// 插入新节点函数
struct Node* insertNode(struct Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return newNode(point);

   unsigned cd = depth % 2;

   if (point[cd] < root->point[cd])
      root->left = insertNode(root->left, point, depth + 1);
   else
      root->right = insertNode(root->right, point, depth + 1);

   return root;
}

// 在 k-d 树中查找最小值节点函数
struct Node* minValueNode(struct Node* root, int d, unsigned depth) {
   if (root == NULL)
      return NULL;

   unsigned cd = depth % 2;

   if (cd == d) {
      if (root->left == NULL)
         return root;
      return minValueNode(root->left, d, depth + 1);
   }

   struct Node* left = minValueNode(root->left, d, depth + 1);
   struct Node* right = minValueNode(root->right, d, depth + 1);

   struct Node* min = root;
   if (left != NULL && left->point[d] < min->point[d])
      min = left;
   if (right != NULL && right->point[d] < min->point[d])
      min = right;

   return min;
}

// 从 k-d 树中删除节点函数
struct Node* deleteNode(struct Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return NULL;

   unsigned cd = depth % 2;

   if (root->point[0] == point[0] && root->point[1] == point[1]) {
      if (root->right != NULL) {
         struct Node* min = minValueNode(root->right, cd, depth + 1);
         root->point[0] = min->point[0];
         root->point[1] = min->point[1];
         root->right = deleteNode(root->right, min->point, depth + 1);
      } else if (root->left != NULL) {
         struct Node* min = minValueNode(root->left, cd, depth + 1);
         root->point[0] = min->point[0];
         root->point[1] = min->point[1];
         root->right = deleteNode(root->left, min->point, depth + 1);
         root->left = NULL;
      } else {
         free(root);
         return NULL;
      }
   } else if (point[cd] < root->point[cd]) {
      root->left = deleteNode(root->left, point, depth + 1);
   } else {
      root->right = deleteNode(root->right, point, depth + 1);
   }

   return root;
}

// 构建 k-d 树函数
struct Node* constructKdTree(int points[][2], int n) {
   struct Node* root = NULL;
   for (int i = 0; i < n; i++)
      root = insertNode(root, points[i], 0);
   return root;
}

// 打印 k-d 树（前序遍历）
void printKdTree(struct Node* root) {
   if (root == NULL)
      return;
   printf("(%d, %d)\n", root->point[0], root->point[1]);
   printKdTree(root->left);
   printKdTree(root->right);
}

// 主函数
int main() {
   int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
   int n = sizeof(points) / sizeof(points[0]);
   struct Node* root = constructKdTree(points, n);
   
   printf("删除前的 K-D 树:\n");
   printKdTree(root);

   int deletePoint[] = {13, 15}; // 删除 (13, 15)
   root = deleteNode(root, deletePoint, 0);

   printf("删除后的 K-D 树:\n");
   printKdTree(root);

   return 0;
}

输出

删除前的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)
删除后的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(6, 12)
(9, 1)
(10, 19)

// 从 k-d 树中删除节点的 C++ 程序
#include <iostream>
using namespace std;

// 表示 k-d 树节点的结构体
struct Node {
   int point[2];
   Node *left, *right;
};

// 创建新节点函数
Node* newNode(int arr[]) {
   Node* temp = new Node;
   temp->point[0] = arr[0];
   temp->point[1] = arr[1];
   temp->left = temp->right = NULL;
   return temp;
}

// 插入新节点函数
Node* insertNode(Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return newNode(point);

   unsigned cd = depth % 2;

   if (point[cd] < (root->point[cd]))
      root->left = insertNode(root->left, point, depth + 1);
   else
      root->right = insertNode(root->right, point, depth + 1);

   return root;
}

// 查找最小值节点函数
Node* minValueNode(Node* root, int d, unsigned depth) {
   if (root == NULL)
      return NULL;

   unsigned cd = depth % 2;

   if (cd == d) {
      if (root->left == NULL)
         return root;
      return minValueNode(root->left, d, depth + 1);
   }

   Node* left = minValueNode(root->left, d, depth + 1);
   Node* right = minValueNode(root->right, d, depth + 1);

   Node* min = root;
   if (left != NULL && left->point[d] < min->point[d])
      min = left;
   if (right != NULL && right->point[d] < min->point[d])
      min = right;

   return min;
}

// 删除节点函数
Node* deleteNode(Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return NULL;

   unsigned cd = depth % 2;

   if (root->point[0] == point[0] && root->point[1] == point[1]) {
      if (root->right != NULL) {
         Node* min = minValueNode(root->right, cd, depth + 1);
         root->point[0] = min->point[0];
         root->point[1] = min->point[1];
         root->right = deleteNode(root->right, min->point, depth + 1);
      } else if (root->left != NULL) {
         Node* min = minValueNode(root->left, cd, depth + 1);
         root->point[0] = min->point[0];
         root->point[1] = min->point[1];
         root->right = deleteNode(root->left, min->point, depth + 1);
         root->left = NULL;
      } else
         return NULL;
   } else if (point[cd] < root->point[cd])
      root->left = deleteNode(root->left, point, depth + 1);
   else
      root->right = deleteNode(root->right, point, depth + 1);

   return root;
}

// 构建 k-d 树函数
Node* constructKdTree(int points[][2], int n) {
   Node* root = NULL;
   for (int i = 0; i < n; i++)
      root = insertNode(root, points[i], 0);
   return root;
}

// 打印 k-d 树函数
void printKdTree(Node* root) {
   if (root == NULL)
      return;
   cout << "(" << root->point[0] << ", " << root->point[1] << ")" << endl;
   printKdTree(root->left);
   printKdTree(root->right);
}

// 主函数
int main() {
   int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
   int n = sizeof(points) / sizeof(points[0]);
   Node* root = constructKdTree(points, n);
   cout << "删除前的 K-D 树:" << endl;
   printKdTree(root);
   root = deleteNode(root, points[2], 0);
   cout << "删除后的 K-D 树:" << endl;
   printKdTree(root);
   return 0;
}

输出

以上代码的输出如下：

删除前的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)
删除后的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(6, 12)
(9, 1)
(10, 19)

// 从 k-d 树中删除节点的 Java 程序
class Node {
   int[] point;
   Node left, right;
   Node(int[] point) {
      this.point = point;
      this.left = this.right = null;
   }
}

public class KdTree {
   Node root;

   Node insertNode(Node root, int[] point, int depth) {
      if (root == null)
         return new Node(point);

      int cd = depth % 2;

      if (point[cd] < root.point[cd])
         root.left = insertNode(root.left, point, depth + 1);
      else
         root.right = insertNode(root.right, point, depth + 1);

      return root;
   }

   Node minValueNode(Node root, int d, int depth) {
      if (root == null)
         return null;

      int cd = depth % 2;

      if (cd == d) {
         if (root.left == null)
            return root;
         return minValueNode(root.left, d, depth + 1);
      }

      Node left = minValueNode(root.left, d, depth + 1);
      Node right = minValueNode(root.right, d, depth + 1);

      Node min = root;
      if (left != null && left.point[d] < min.point[d])
         min = left;
      if (right != null && right.point[d] < min.point[d])
         min = right;

      return min;
   }

   Node deleteNode(Node root, int[] point, int depth) {
      if (root == null)
         return null;

      int cd = depth % 2;

      if (root.point[0] == point[0] && root.point[1] == point[1]) {
         if (root.right != null) {
            Node min = minValueNode(root.right, cd, depth + 1);
            root.point[0] = min.point[0];
            root.point[1] = min.point[1];
            root.right = deleteNode(root.right, min.point, depth + 1);
         } else if (root.left != null) {
            Node min = minValueNode(root.left, cd, depth + 1);
            root.point[0] = min.point[0];
            root.point[1] = min.point[1];
            root.right = deleteNode(root.left, min.point, depth + 1);
            root.left = null;
         } else
            return null;
      } else if (point[cd] < root.point[cd])
         root.left = deleteNode(root.left, point, depth + 1);
        else
            root.right = deleteNode(root.right, point, depth + 1);

        return root;
    }

    void printKdTree(Node root) {
        if (root == null)
            return;
        System.out.println("(" + root.point[0] + ", " + root.point[1] + ")");
        printKdTree(root.left);
        printKdTree(root.right);
    }

    public static void main(String[] args) {
        int[][] points = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
        KdTree tree = new KdTree();
        for (int[] point : points)
            tree.root = tree.insertNode(tree.root, point, 0);
        System.out.println("删除前的 K-D 树:");
        tree.printKdTree(tree.root);
        tree.root = tree.deleteNode(tree.root, points[2], 0);
        System.out.println("删除后的 K-D 树:");
        tree.printKdTree(tree.root);
    }
}

输出

以上代码的输出如下：

删除前的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)
删除后的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(6, 12)
(9, 1)
(10, 19)

# 从 k-d 树中删除节点的 Python 程序
class Node:
   def __init__(self, point):
      self.point = point
      self.left = None
      self.right = None

def insertNode(root, point, depth):

    if root is None:
        return Node(point)
    
    cd = depth % 2
    
    if point[cd] < root.point[cd]:
        root.left = insertNode(root.left, point, depth + 1)
    else:
        root.right = insertNode(root.right, point, depth + 1)
    
    return root

def minValueNode(root, d, depth):

    if root is None:
        return None
    
    cd = depth % 2
    
    if cd == d:
        if root.left is None:
            return root
        return minValueNode(root.left, d, depth + 1)
    
    left = minValueNode(root.left, d, depth + 1)
    right = minValueNode(root.right, d, depth + 1)
    
    min = root
    if left is not None and left.point[d] < min.point[d]:
        min = left
    if right is not None and right.point[d] < min.point[d]:
        min = right
    
    return min

def deleteNode(root, point, depth):

    if root is None:
        return None
    
    cd = depth % 2
    
    if root.point[0] == point[0] and root.point[1] == point[1]:
        if root.right is not None:
            min = minValueNode(root.right, cd, depth + 1)
            root.point[0] = min.point[0]
            root.point[1] = min.point[1]
            root.right = deleteNode(root.right, min.point, depth + 1)
        elif root.left is not None:
            min = minValueNode(root.left, cd, depth + 1)
            root.point[0] = min.point[0]
            root.point[1] = min.point[1]
            root.right = deleteNode(root.left, min.point, depth + 1)
            root.left = None
        else:
            return None
    elif point[cd] < root.point[cd]:
        root.left = deleteNode(root.left, point, depth + 1)
    else:
        root.right = deleteNode(root.right, point, depth + 1)
    
    return root

def printKdTree(root):
    if root is None:
        return
    print("(", root.point[0], ", ", root.point[1], ")")
    printKdTree(root.left)
    printKdTree(root.right)

points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]]
root = None
for point in points:
    root = insertNode(root, point, 0)
print("删除前的 K-D 树:")
printKdTree(root)
root = deleteNode(root, points[2], 0)
print("删除后的 K-D 树:")
printKdTree(root)

输出

以上代码的输出如下：

删除前的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(13, 15)
(6, 12)
(9, 1)
(10, 19)
删除后的 K-D 树:
(3, 6)
(2, 7)
(17, 15)
(6, 12)
(9, 1)
(10, 19)

K-D 树上的搜索操作

k-d 树中的搜索操作通过以下步骤执行：

  • 从根节点开始。
  • 如果点等于根节点，则返回根节点。
  • 如果点小于根节点，则在左子树中搜索。
  • 如果点大于根节点，则在右子树中搜索。

K-D 树中搜索节点的代码

以下是在 C、C++、Java 和 Python 中搜索 k-d 树中节点的示例代码：

C C++ Java Python 
#include <stdio.h>
#include <stdlib.h>

// 用于表示 k-d 树节点的结构
struct Node {
   int point[2];
   struct Node *left, *right;
};

// 创建新节点的功能
struct Node* newNode(int arr[]) {
   struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
   temp->point[0] = arr[0];
   temp->point[1] = arr[1];
   temp->left = temp->right = NULL;
   return temp;
}

// 插入新节点的功能
struct Node* insertNode(struct Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return newNode(point);

   unsigned cd = depth % 2;

   if (point[cd] < root->point[cd])
      root->left = insertNode(root->left, point, depth + 1);
   else
      root->right = insertNode(root->right, point, depth + 1);

   return root;
}

// 在 k-d 树中搜索节点的功能
struct Node* searchNode(struct Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return NULL;

   if (root->point[0] == point[0] && root->point[1] == point[1])
      return root;

   unsigned cd = depth % 2;

   if (point[cd] < root->point[cd])
      return searchNode(root->left, point, depth + 1);
   return searchNode(root->right, point, depth + 1);
}

// 构建 k-d 树的功能
struct Node* constructKdTree(int points[][2], int n) {
   struct Node* root = NULL;
   for (int i = 0; i < n; i++)
      root = insertNode(root, points[i], 0);
   return root;
}


// 释放 k-d 树分配内存的功能
void freeKdTree(struct Node* root) {
   if (root == NULL)
      return;
   freeKdTree(root->left);
   freeKdTree(root->right);
   free(root);
}

// 主函数
int main() {
   int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
   int n = sizeof(points) / sizeof(points[0]);
   struct Node* root = constructKdTree(points, n);


   int searchPoint[] = {13, 15}; // 搜索 (13, 15)
   struct Node* node = searchNode(root, searchPoint, 0);

   if (node != NULL)
      printf("Node found: (%d, %d)\n", node->point[0], node->point[1]);
   else
      printf("Node not found\n");

   // 释放分配的内存
   freeKdTree(root);

   return 0;
}

输出

Node found: (13, 15)

// C++ 程序，用于在 k-d 树中搜索节点
#include <iostream>
using namespace std;

// 用于表示 k-d 树节点的结构
struct Node {
   int point[2];
   Node *left, *right;
};

// 创建新节点的功能
Node* newNode(int arr[]) {
   Node* temp = new Node;
   temp->point[0] = arr[0];
   temp->point[1] = arr[1];
   temp->left = temp->right = NULL;
   return temp;
};

// 插入新节点的功能
Node* insertNode(Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return newNode(point);

   unsigned cd = depth % 2;

   if (point[cd] < (root->point[cd]))
      root->left = insertNode(root->left, point, depth + 1);
   else
      root->right = insertNode(root->right, point, depth + 1);

   return root;
}

// 搜索节点的功能
Node* searchNode(Node* root, int point[], unsigned depth) {
   if (root == NULL)
      return NULL;

   unsigned cd = depth % 2;

   if (root->point[0] == point[0] && root->point[1] == point[1])
      return root;

   if (point[cd] < root->point[cd])
      return searchNode(root->left, point, depth + 1);
   return searchNode(root->right, point, depth + 1);
}

// 构建 k-d 树的功能

Node* constructKdTree(int points[][2], int n) {
   Node* root = NULL;
   for (int i = 0; i < n; i++)
      root = insertNode(root, points[i], 0);
   return root;
}

// 打印 k-d 树的功能
void printKdTree(Node* root) {
   if (root == NULL)
      return;
   cout << "(" << root->point[0] << ", " << root->point[1] << ")" << endl;
   printKdTree(root->left);
   printKdTree(root->right);
}

// 主函数

int main() {
   int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
   int n = sizeof(points) / sizeof(points[0]);
   Node* root = constructKdTree(points, n);
   Node* node = searchNode(root, points[2], 0);
   if (node != NULL)
      cout << "Node found: (" << node->point[0] << ", " << node->point[1] << ")" << endl;
   else
      cout << "Node not found" << endl;
   return 0;
}

输出

以上代码的输出如下：

Node found: (13, 15)

// Java 程序，用于在 k-d 树中搜索节点
class Node {
   int[] point;
   Node left, right;
   Node(int[] point) {
      this.point = point;
      this.left = this.right = null;
   }
}

public class KdTree {
   Node root;

   Node insertNode(Node root, int[] point, int depth) {
      if (root == null)
         return new Node(point);

      int cd = depth % 2;

      if (point[cd] < root.point[cd])
         root.left = insertNode(root.left, point, depth + 1);
      else
         root.right = insertNode(root.right, point, depth + 1);

      return root;
   }

   Node searchNode(Node root, int[] point, int depth) {
      if (root == null)
         return null;

      int cd = depth % 2;

      if (root.point[0] == point[0] && root.point[1] == point[1])
         return root;

      if (point[cd] < root.point[cd])
         return searchNode(root.left, point, depth + 1);
      return searchNode(root.right, point, depth + 1);
   }

   void printKdTree(Node root) {
      if (root == null)
         return;
      System.out.println("(" + root.point[0] + ", " + root.point[1] + ")");
      printKdTree(root.left);
      printKdTree(root.right);
   }

   public static void main(String[] args) {
      int[][] points = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
      KdTree tree = new KdTree();
      for (int[] point : points)
         tree.root = tree.insertNode(tree.root, point, 0);
      Node node = tree.searchNode(tree.root, points[2], 0);
      if (node != null)
         System.out.println("Node found: (" + node.point[0] + ", " + node.point[1] + ")");
      else
         System.out.println("Node not found");
   }
}

输出

以上代码的输出如下：

Node found: (13, 15)

# Python 程序，用于在 k-d 树中搜索节点

class Node:
   def __init__(self, point):
      self.point = point
      self.left = None
      self.right = None

def insertNode(root, point, depth):
    if root is None:
        return Node(point)
    
    cd = depth % 2
    
    if point[cd] < root.point[cd]:
        root.left = insertNode(root.left, point, depth + 1)
    else:
        root.right = insertNode(root.right, point, depth + 1)
    
    return root

def searchNode(root, point, depth):
    if root is None:
        return None
    
    cd = depth % 2
    
    if root.point[0] == point[0] and root.point[1] == point[1]:
        return root
    
    if point[cd] < root.point[cd]:
        return searchNode(root.left, point, depth + 1)
    return searchNode(root.right, point, depth + 1)

def printKdTree(root):
    if root is None:
        return
    print("(", root.point[0], ", ", root.point[1], ")")
    printKdTree(root.left)
    printKdTree(root.right)

points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]]
root = None
for point in points:
    root = insertNode(root, point, 0)
node = searchNode(root, points[2], 0)
if node is not None:
    print("Node found: (", node.point[0], ", ", node.point[1], ")")
else:
    print("Node not found")

输出

以上代码的输出如下：

Node found: (13, 15)

K-D 树的时序复杂度

k-d 树的各种操作的时序复杂度如下所示：

  • 插入： 在 k-d 树中插入一个节点的时序复杂度为 O(log n)，其中 n 是树中的节点数。
  • 删除： O(log n)。
  • 搜索： O(log n)。

K-D 树的应用

k-d 树用于以下应用：

  • 最近邻搜索： k-d 树用于在 k 维空间中找到给定点的最近邻。
  • 范围搜索： k-d 树用于找到查询点给定范围内的所有点。
  • 近似最近邻搜索： k-d 树用于在 k 维空间中找到给定点的近似最近邻。
  • 图像处理： k-d 树在图像处理中用于找到相似图像。

结论

在本章中，我们讨论了 k-d 树，这是一种用于存储 k 维点的**数据结构**。我们讨论了 k-d 树的构建、对 k-d 树的操作，以及 k-d 树的时序复杂度。我们还提供了用 C、C++、Java 和 Python 构建、插入、删除和搜索 k-d 树中节点的示例代码。