KD树的构建(递归

2023-12-26 04:41:36

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.效果:

在这里插入图片描述

小结:

关注我给大家分享更多有趣的知识,以下是个人公众号,提供 ||代码兼职|| ||代码问题求解||
由于本号流量还不足以发表推广,搜我的公众号即可:
在这里插入图片描述

文章来源:https://blog.csdn.net/m0_72249799/article/details/135211353
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。