四叉树删除

Question

我正在编写一个四叉树的删除方法。

现在，当您删除节点中的某个项目时，您需要检查其兄弟节点，以查看是否需要将节点折叠并合并为一个节点。

关于检查兄弟节点，我应该存储一个指向父节点的指针，还是有更好的递归方式来实现？

谢谢

- darksky

---

我猜这是一个高度专业化的学科，所以可能没有很多人有经验。而且很多事情取决于您选择的数据结构。但是我观察到您可能需要遍历树来定位要删除的节点，因此在遍历时可以传递父指针，而不需要在每个节点中存储父指针。 - Hot Licks

Answer 1

对于四叉树的删除，您需要执行以下操作：

1. 查找对象所在的叶子节点，然后从该列表中删除它（包含叶子节点的节点）
2. 检查删除叶子节点是否导致该节点为空，如果是，则删除该节点本身。
3. 检查周围的节点是否为空，如果是，则通过“取消细分”将此节点合并到父节点中（这可能会递归地变得棘手）。技巧就是只需检查相邻节点是否有内容。如果没有，可以安全地丢弃整个象限并向上移动一级。递归执行此操作将使树折叠回包含叶子节点的相邻节点所在的位置。

完成步骤1后，您基本上已经完成了。如果要节省内存并保持树的效率，则应执行步骤2和3。

是的，您应该保留父节点引用以使反向遍历高效。

- martyman