Skip to content

Instantly share code, notes, and snippets.

@zhuang-hao-ming
Last active April 2, 2018 11:26
Show Gist options
  • Save zhuang-hao-ming/01923a5c9f0197aba5669f29ae3bd97b to your computer and use it in GitHub Desktop.
Save zhuang-hao-ming/01923a5c9f0197aba5669f29ae3bd97b to your computer and use it in GitHub Desktop.
kd-tree笔记

kd-tree

一般描述

什么是kd-tree

kd-tree是一种树数据结构, 用来存储多维数据。正如BST(二分搜索树)用值的大小关系来建树,左子节点的值 < 父节点 < 右子节点。 kd-tree也是用值的大小关系来建树,但是由于它处理的是多维数据, 以二维为例, 在根节点根据x值的大小关系来组织, 左子节点x值 < 父节点x值 < 右节点x值, 在下一层, 则换用y值的大小关系来组织, 左子节点y值 < 父节点y值 < 右节点y值,再下一层又换回x值,如此循环。

如何查找

以二维为例, 从根节点开始, 如果x值比根节点大或等于,就在右子树查找, 如果x值比根结点小,就在左子树查找,如果x值和y值都相同,则查找到。

如何插入

以二维为例, 在kd-tree中插入一个节点, 实际上就是查找一个可以插入的位置, 从根节点开始, 如果x值比根节点大,就插入在根的右子树,如果 x值比根节点小, 就插入在左子树。子树的插入方法相同, 直到找到一个null的位置。

如何删除

首先, 使用和查找一样的方法, 确定删除点的位置, 使用以下步骤来删除:

  1. 如果删除点没有子树,直接删除。
  2. 如果删除点有右子树, 在右子树查找到当前维度的最小值, 和节点替换,然后重新删除那个点
  3. 如果删除点有左子树, 在左子树查找当前维度最小值,和节点替换,然后重新删除那个点, 最后把整个左子树移到右边

如何查找x值或y值最小的点

以x值为例, 如果当前节点的分割维度是x, 那么在左子树查找, 如果不是则两个子树都要查找。

最近邻查询

假设查询点为Q, 一开始设定最近距离为infinity, 结果点为null. 从根节点开始, 计算根节点到Q的距离,将它记为最近距离,将节点本身记为结果点。 根据跟节点的分割维度x, 比较Q的x值和分割x的关系, 如果x < 分割x,则优先查找左子树, 否则优先查找右子树。 在优先子树中重复上述操作。计算Q到根节点的距离, 如果更小则更新结果。 在非优先子树中, 需要计算(在父节点)Q到分割轴的距离, 如果这个距离比当前最近距离还大, 那么剪掉这整棵子树,不用查找。

k近邻查询

和最近邻查询一致, 但是对于途中计算到的所有最小距离和候选结果点, 以距离为权重,保存在最小堆中。最后返回最小堆中的前k个,即为结果。

实现相关

如何建立平衡的kd-tree

如果预先已经知道数据点了, 可以建立一棵平衡的kd-tree使得,左右子树的高度差较小。 建立的方法就是, 选择分割值的时候,以中位数作为分割值, 最简单的方法就是对于所有值排列然后选择 中间的值。

随机选择, 中点选择

使用排列然后再选择中值的方法,效率有点低,可以使用一些快速选择方法。

  1. 随机选择:

随机选择是快速排序的一种变体, 快速排序每次分割都会确定一个元素的位置。 随机选择则随机地选择一个元素, 然后确定它的位置, 之后查看这个元素是不是在中点, 如果不是,则查看它是在中点的左边还是右边,如果在中点的左边,则从元素 开始到结尾重新随机选择一个元素确定它的位置,在右边则反之,如此重复,直到确定中点元素的值。

  1. 中点选择:

随机选择虽然在实践上可以得到很好的结果, 但是在理论上的结果不够好。 中点选择, 和随机选择类似, 但是它不是随机的确认一个元素的位置, 而是使得确认的元素尽可能的接近中点。

它首先将元素每5个分成一组, 计算每组的中点, 然后将得到的中点,又每5个分成一组, 计算中点, 如此重复,直到得到一个中点元素, 这个值就是候选元素值,确定它的位置, 如果它是中点则结束,否则和随机选择类似,在一个小范围内重新确定。

静态kd-tree

从随机选择和中点选择中获得启发, 可以使用这种方法, 在数组内部原地的对元素进行重排, 使得整体的中点是根节点, 左边的中点是左子树根节点, 右边的中点是右子树根节点。以此类推。这种方法没有建立起层次结构。可以节约内存, 但是相应的操作需要改变。

参考链接

  1. 随机选择
  2. 中点选择
  3. 一般介绍1
  4. 一般介绍2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment