admin管理员组

文章数量:1621657

文章目录

  • 确定k维空间的分割线，画k-d树
    • 每个节点中主要包含的数据结构
      • 1. Split域的计算
      • 2. Node-data的计算
  • 在建立的k-d树上如何进行最邻近查找的算法

K-d tree：是一种分割k维数据空间的数据结构，主要应用于多维空间 关键数据的搜索。

确定k维空间的分割线，画k-d树

k-d树是一个二叉树，每个节点表示一个空间范围；

每个节点中主要包含的数据结构

(1) Node-data：一组数据的中值点；
(2) Range：该节点所代表的空间范围；
(3) Split：垂直于分割超平面的方向轴序号；
(4) Left：左子树
(5) Right：右子树
(6) Parent：父节点

1. Split域的计算

计算每维（x\y\z轴）数据的方差，挑选出最大值，即该维就是split域的值。
初始化split={0,1,2,3,……}0代表x轴，1代表y轴，2代表z轴。

2. Node-data的计算

点集中按split域的值（哪个轴）排序，位于正中间的数据点即为该值；
通过该点并垂直于split的值做超平面；
此时范围空间分为左子空间和右子空间，接下来继续对左子空间和右子空间的数据点重复根节点的操作。
例：（2，3）（8，1）（5，4）（4，7）（9，6）（7，2）
（1）Split的初始值为{0，1}，因为该数据是二维数据。
计算方差：
x轴：

  • 均值（2+8+5+4+9+7）/6=5.83
  • 方差
    [ ( 2 − 5.83 ) 2 + ( 8 − 5.83 ) 2 + ( 5 − 5.83 ) 2 + ( 4 − 5.83 ) 2 + ( 9 − 5.83 ) 2 + ( 7 − 5.83 ) 2 ] / 6 = 10.79 [(2-5.83)^2 +(8-5.83)^2+(5-5.83)^2+(4-5.83)^2+(9-5.83)^2+(7-5.83)^2] / 6=10.79 [(2−5.83)2+(8−5.83)2+(5−5.83)2+(4−5.83)2+(9

本文标签： tree

版权声明：本文标题：K-D Tree初学 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1728851024a1176681.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。