kd-tree是一种树数据结构, 用来存储多维数据。正如BST(二分搜索树)用值的大小关系来建树,左子节点的值 < 父节点 < 右子节点。 kd-tree也是用值的大小关系来建树,但是由于它处理的是多维数据, 以二维为例, 在根节点根据x值的大小关系来组织, 左子节点x值 < 父节点x值 < 右节点x值, 在下一层, 则换用y值的大小关系来组织, 左子节点y值 < 父节点y值 < 右节点y值,再下一层又换回x值,如此循环。
以二维为例, 从根节点开始, 如果x值比根节点大或等于,就在右子树查找, 如果x值比根结点小,就在左子树查找,如果x值和y值都相同,则查找到。
以二维为例, 在kd-tree中插入一个节点, 实际上就是查找一个可以插入的位置, 从根节点开始, 如果x值比根节点大,就插入在根的右子树,如果 x值比根节点小, 就插入在左子树。子树的插入方法相同, 直到找到一个null的位置。
首先, 使用和查找一样的方法, 确定删除点的位置, 使用以下步骤来删除:
- 如果删除点没有子树,直接删除。
- 如果删除点有右子树, 在右子树查找到当前维度的最小值, 和节点替换,然后重新删除那个点
- 如果删除点有左子树, 在左子树查找当前维度最小值,和节点替换,然后重新删除那个点, 最后把整个左子树移到右边
以x值为例, 如果当前节点的分割维度是x, 那么在左子树查找, 如果不是则两个子树都要查找。
假设查询点为Q, 一开始设定最近距离为infinity, 结果点为null. 从根节点开始, 计算根节点到Q的距离,将它记为最近距离,将节点本身记为结果点。 根据跟节点的分割维度x, 比较Q的x值和分割x的关系, 如果x < 分割x,则优先查找左子树, 否则优先查找右子树。 在优先子树中重复上述操作。计算Q到根节点的距离, 如果更小则更新结果。 在非优先子树中, 需要计算(在父节点)Q到分割轴的距离, 如果这个距离比当前最近距离还大, 那么剪掉这整棵子树,不用查找。
和最近邻查询一致, 但是对于途中计算到的所有最小距离和候选结果点, 以距离为权重,保存在最小堆中。最后返回最小堆中的前k个,即为结果。
如果预先已经知道数据点了, 可以建立一棵平衡的kd-tree使得,左右子树的高度差较小。 建立的方法就是, 选择分割值的时候,以中位数作为分割值, 最简单的方法就是对于所有值排列然后选择 中间的值。
使用排列然后再选择中值的方法,效率有点低,可以使用一些快速选择方法。
- 随机选择:
随机选择是快速排序的一种变体, 快速排序每次分割都会确定一个元素的位置。 随机选择则随机地选择一个元素, 然后确定它的位置, 之后查看这个元素是不是在中点, 如果不是,则查看它是在中点的左边还是右边,如果在中点的左边,则从元素 开始到结尾重新随机选择一个元素确定它的位置,在右边则反之,如此重复,直到确定中点元素的值。
- 中点选择:
随机选择虽然在实践上可以得到很好的结果, 但是在理论上的结果不够好。 中点选择, 和随机选择类似, 但是它不是随机的确认一个元素的位置, 而是使得确认的元素尽可能的接近中点。
它首先将元素每5个分成一组, 计算每组的中点, 然后将得到的中点,又每5个分成一组, 计算中点, 如此重复,直到得到一个中点元素, 这个值就是候选元素值,确定它的位置, 如果它是中点则结束,否则和随机选择类似,在一个小范围内重新确定。
从随机选择和中点选择中获得启发, 可以使用这种方法, 在数组内部原地的对元素进行重排, 使得整体的中点是根节点, 左边的中点是左子树根节点, 右边的中点是右子树根节点。以此类推。这种方法没有建立起层次结构。可以节约内存, 但是相应的操作需要改变。