[toc]

# K-D Tree 是啥

k-D Tree (KDT , k-Dimension Tree) 是一种可以 高效处理 [k] 维空间信息 的数据结构。

# KD Tree 的思想

1. 不断划分当前的点，选择一个 合适的维度 把空间划分，三维每次划分出四部分，二维每次划分出 2 部分
2. 合适的维度 ，尽量保证两边数据量相差最小 (尽量保证树的平衡性)
3. 合适的分割点 ，尽量选择对应的分割快内的中位数那个点

后插入与删除如何操作呢？

插入时，规定一个平衡因子 α, 如果某一个根节点下的节点数量大于这个 α 时，就执行局部重构
删除时，规定一个平衡因子 α, 将对应的删除节点标记为 dirty ，而不去删除，但是如果同样破坏了平衡因子 α, 执行重构