KD树的构建（递归

1.简介

KD树（K-Dimensional Tree）是一种二叉树，用于在k维空间中对数据进行分割和组织。它具有以下特点：

2.基本知识点：

1. KD树是一种二叉树，每个节点代表一个k维向量。
2. 每个节点的左子树和右子树分别表示比当前节点小和大的数据。
3. KD树的构建过程是通过递归的方式进行的，每次选择一个维度作为切分维度，以该维度的中值作为节点，将数据集切分成两部分。
4. 在查询时，通过比较目标向量和节点的切分维度的值，可以确定搜索路径。

3.与平衡二叉树的不同之处：

1. 平衡二叉树（如AVL树、红黑树）的主要目的是保持树的左右子树的高度差不超过1，从而提供快速的插入、删除和搜索操作。
2. KD树并不一定是平衡的，因为它的构建过程是基于数据集的切分，而不是固定的旋转操作。
3. KD树的构建过程是通过选择切分维度和切分值来进行的，因此它可能会导致树的不平衡。
4. 不平衡的KD树可能导致搜索操作的效率下降，因为搜索路径可能会非常长。

4.改动的代码：

主要代码和平衡二叉树相似，可以见我上次的文章：平衡二叉树链接

在上述提供的代码中，我们对原始的平衡二叉树构建函数进行了一些修改。具体的修改包括：

1. 添加了一个新的参数loop_num，用于记录循环轮数。
2. 修改了递归调用的参数，将loop_num增加1传递给下一次递归，确保每次递归时切分维度正确更新。
3. 数据全部都换为了高纬度的向量。

这些改动使得构建的KD树能够按照每个元组的第一个值、第二个值等依次进行排序，并且正确选择切分维度，从而构建出正确的KD树结构。
通过使用KD树，我们可以在高维数据集中高效地进行搜索和查询操作。它在许多应用中都有广泛的应用，例如最近邻搜索、范围搜索等。尽管与平衡二叉树有所不同，但KD树在处理多维数据时提供了更好的性能和效率。

5.代码：

# KD树节点类
class BiTreeNode():
    def __init__(self, data):
        self.lchild = None  # 二叉树左子树
        self.rchild = None  # 二叉树右子树
        self.data = data

# 创建平衡二叉树的函数
def create(list_data, loop_num = -1):
    # 记录循环轮数
    loop_num += 1

    # 排序
    list_data = sorted(list_data, key=lambda x: x[loop_num % 2])

    # 中间节点索引
    mid_index = len(list_data) // 2

    # 创建节点
    node = BiTreeNode(list_data[mid_index])

    # 列表左右分割
    rlist_data = list_data[:mid_index]
    llist_data = list_data[mid_index + 1:]

    # 递归构建左子树和右子树
    if len(rlist_data) > 0:
        node.rchild = create(rlist_data, loop_num)
    if len(llist_data) > 0:
        node.lchild = create(llist_data, loop_num)

    return node  # 返回根节点

if __name__ == "__main__":
    list_data = [(4, 7), (5, 4), (2, 3), (9, 6), (7, 2), (8, 1)]   # 输入数据
    root = create(list_data)    # 默认升序

6.效果：

小结：

关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||代码兼职|| ||代码问题求解||
由于本号流量还不足以发表推广，搜我的公众号即可：