algorithm - 使用 O(1) 辅助存储空间删除二叉树中的所有节点？

Question

删除 binary tree 中所有节点的标准算法使用 postorder traversal 沿着这些线在节点上:

if (root is not null) {
   recursively delete left subtree
   recursively delete right subtree
   delete root
}

该算法使用 O(h) 辅助存储空间，其中 h 是树的高度，因为在递归调用期间需要空间来存储堆栈帧。但是，它的运行时间为 O(n)，因为每个节点都恰好访问了一次。

有没有一种算法可以在不牺牲运行时间的情况下仅使用 O(1) 的辅助存储空间来删除​​二叉树中的所有节点？

Answer 1

通过使用基于 tree rotations的算法，使用O(n)和O(1)辅助存储空间确实可以删除二叉树中的所有节点。 .

给定一个具有以下形状的二叉树:

           u
          / \
         v   C
        / \
       A   B

这棵树的右旋转将节点 v 拉到节点 u 的上方，并产生以下树:

        v
       / \
      A   u
         / \
        B   C

请注意，树的旋转可以在 O(1) 时间和空间内完成，只需将树的根更改为 v，将 u 的左 child 设置为 v 的前右 child ，然后将 v 的右 child 设置为 u .

树的旋转在这种情况下很有用，因为向右旋转总是将树的左子树的高度减一。这是有用的，因为一个聪明的观察:如果树的根没有左子节点，删除它是非常容易的。特别是，如果树的形状是这样的:

     v
      \
       A

然后我们可以通过删除节点 v，然后删除其子树 A 中的所有节点来删除树中的所有节点。这导致了一个非常简单的删除树中所有节点的算法:

while (root is not null) {
    if (root has a left child) {
        perform a right rotation
    } else {
        delete the root, and make the root's right child the new root.
    }
}

该算法显然仅使用 O(1) 存储空间，因为它最多需要固定数量的指针来进行旋转或更改根，并且这些指针的空间可以在循环的所有迭代中重复使用。

此外，可以证明该算法的运行时间也是 O(n)。直观地说，可以通过查看给定边可以旋转多少次来了解这一点。首先，请注意，无论何时执行右旋转，从节点到其左子节点的边都会转换为从前一个子节点返回到其父节点的右边。接下来，请注意一旦我们执行了将节点 u 移动到节点 v 的右子节点的旋转，在我们删除节点 v 和 v 的所有左子树之前，我们将永远不会再次接触节点 u。因此，我们可以通过注意树中的每条边最多与其父节点一起旋转一次来限制将要完成的总旋转次数。因此，最多完成 O(n) 次旋转，每次旋转都需要 O(1) 时间，并且正好完成 n 次删除。这意味着该算法的运行时间为 O(n)，并且仅使用 O(1) 的空间。

如果有帮助，我有 a C++ implementation of this algorithm ，以及对算法行为的更深入分析。它还包括算法所有步骤正确性的正式证明。

希望这对您有所帮助!