KD树的构建(递归
2023-12-26 04:41:36
1.简介
KD树(K-Dimensional Tree)是一种二叉树,用于在k维空间中对数据进行分割和组织。它具有以下特点:
2.基本知识点:
- KD树是一种二叉树,每个节点代表一个k维向量。
- 每个节点的左子树和右子树分别表示比当前节点小和大的数据。
- KD树的构建过程是通过递归的方式进行的,每次选择一个维度作为切分维度,以该维度的中值作为节点,将数据集切分成两部分。
- 在查询时,通过比较目标向量和节点的切分维度的值,可以确定搜索路径。
3.与平衡二叉树的不同之处:
- 平衡二叉树(如AVL树、红黑树)的主要目的是保持树的左右子树的高度差不超过1,从而提供快速的插入、删除和搜索操作。
- KD树并不一定是平衡的,因为它的构建过程是基于数据集的切分,而不是固定的旋转操作。
- KD树的构建过程是通过选择切分维度和切分值来进行的,因此它可能会导致树的不平衡。
- 不平衡的KD树可能导致搜索操作的效率下降,因为搜索路径可能会非常长。
4.改动的代码:
主要代码和平衡二叉树相似,可以见我上次的文章:平衡二叉树链接
在上述提供的代码中,我们对原始的平衡二叉树构建函数进行了一些修改。具体的修改包括:
- 添加了一个新的参数loop_num,用于记录循环轮数。
- 修改了递归调用的参数,将loop_num增加1传递给下一次递归,确保每次递归时切分维度正确更新。
- 数据全部都换为了高纬度的向量。
这些改动使得构建的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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!