tree - 四叉树分裂操作

Question

我无法理解四叉树拆分操作。假设一个节点可以容纳的最大项目数是 2；当我们添加第三个元素时，我们创建了四个子节点。问题是，父节点是否保留其 2 项，而导致溢出的一项插入到子节点中，还是所有三个节点都插入子节点中？

Answer 1

所有三个节点都被插入到一个子节点中。只有叶子节点可以在树中保存一些数据。

这可以与例如 kd-tree 有所不同，其中空间分区更面向数据而不是固定空间分区，从而节省内存。另一方面，固定空间分区更容易处理，甚至可以预先计算以实现更快的访问。