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

Question

删除二叉树中所有节点的标准算法使用沿这些行的节点上的后序遍历:

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

该算法使用O(h)辅助存储空间,其中h是树的高度,因为在递归调用期间存储堆栈帧所需的空间.但是,它在时间O(n)中运行,因为每个节点只访问一次.

是否有算法仅使用O(1)辅助存储空间删除二叉树中的所有节点而不牺牲运行时间？

Answer 1

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

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

           u
          / \
         v   C
        / \
       A   B

此树的右旋转将节点v拉到节点u上方,并生成以下树:

        v
       / \
      A   u
         / \
        B   C

注意,可以在O(1)时间和空间中完成树旋转,只需将树的根更改为v,将u的左子设置为v的前右子,然后将v的右子设置为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的右子节点的旋转,我们将永远不会再触摸节点u,直到我们删除节点v和所有v的左子树.因此,我们可以通过注意树中的每个边缘最多旋转一次来限制将要完成的总旋转次数.因此,最多完成O(n)次旋转,每次旋转花费O(1)时间,并且完成n次删除.这意味着算法在时间O(n)中运行并且仅使用O(1)空间.

如果它有帮助,我有这个算法的C++实现,以及对算法行为的更深入的分析.它还包括算法所有步骤的正确性的正式证明.

希望这可以帮助!