java - 四叉树删除

Question

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

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

为了检查 sibling ，我应该存储一个指向父节点的指针，还是有更好的递归方式来做到这一点？

谢谢

Answer 1

要在四叉树中删除，您基本上需要执行以下操作:

1. 找到对象的叶子，然后将其从该列表中删除(包含叶子的节点)
2. 检查叶子的移除是否使节点为空，如果是，则移除节点本身。
3. 检查周围的节点是否也为空，如果是，则通过“取消分割”将此节点折叠到父节点中(这可能会递归地变得棘手)。诀窍是只检查相邻节点中是否有任何东西。如果没有，你可以安全地扔掉整个象限并提升一个级别。递归地执行此操作会将树折叠回具有叶子的相邻节点所在的位置。

完成第 1 步后，您就基本完成了。如果你想节省内存并保持树的效率，那么你应该执行步骤 2 和 3。

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