algorithm - 使用 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 次删除。

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

希望这可以帮助！

Answer 2

让我从一个严肃的笑话开始：如果您将 BST 的根设置为空，您实际上会删除树中的所有节点（垃圾收集器将使空间可用）。虽然措辞是特定于 Java 的，但这个想法也适用于其他编程语言。我提到这一点是为了以防你参加工作面试或参加考试。

否则，您所要做的就是使用DSW algorithm. 基本上将树变成主干，然后像删除linked list. 空间 O(1) 和时间 O(n)。你应该在任何教科书或网上找到关于 DSW 的讨论。

基本上 DSW 用于平衡 BST。但是对于您的情况，一旦您获得主干，而不是平衡，您就像删除链表一样删除。

Answer 3

算法 1，O(n)时间和O(1)空间：立即删除节点，除非它有两个孩子。否则到达最左边的节点反转“左”链接以确保所有节点都可以访问 - 最左边的节点成为新的根：

void delete_tree(Node *node) {
    Node *p, *left, *right;

    for (p = node; p; ) {
        left = p->left;
        right = p->right;
        if (left && right) {
            Node *prev_p = nullptr;
            do {
                p->left = prev_p;
                prev_p = p;
                p = left;
            } while ((left = p->left) != nullptr);
            p->left = p->right;
            p->right = prev_p;       //need it on the right to avoid loop
        } else {
            delete p;
            p = (left) ? left : right;
        }
    }
}

算法 2，O(n)时间和O(1)空间：深度优先遍历节点，将子链接替换为父链接。每个节点在向上的过程中被删除：

void delete_tree(Node *node) {
    Node *p, *left, *right;
    Node *upper = nullptr;

    for (p = node; p; ) {
        left = p->left;
        right = p->right;
        if (left && left != upper) {
            p->left = upper;
            upper = p;
            p = left;
        } else if (right && right != upper) {
            p->right = upper;
            upper = p;
            p = right;
        } else {
            delete p;
            p = upper;
            if (p)
                upper = (p->left) ? p->left : p->right;
        }
    }
}

Answer 4

我对上面所有需要复杂操作的答案感到惊讶。

通过简单地将所有递归调用替换为搜索节点并跟踪当前节点的父节点的循环，可以使用 O(1) 额外存储从 BST 中删除节点。使用递归更简单，因为递归调用会自动将搜索节点的所有祖先存储在堆栈中。但是，不必存储所有祖先。只需要存储搜索到的节点和它的父节点，这样搜索到的节点就可以被取消链接。存储所有的祖先，简直就是浪费空间。

Python 3 中的解决方案如下。不要被看似递归的调用delete--- 这里的最大递归深度是 2 所迷惑，因为第二次调用 delete 保证会导致删除基本情况（包含搜索值的根节点）。

class Tree(object):
    def __init__(self, x):
        self.value = x
        self.left = None
        self.right = None


def remove_rightmost(parent, parent_left, child):
    while child.right is not None:
        parent = child
        parent_left = False
        child = child.right
    if parent_left:
        parent.left = child.left
    else:
        parent.right = child.left
    return child.value


def delete(t, q):
    if t is None:
        return None

    if t.value == q:
        if t.left is None:
            return t.right
        else:
            rightmost_value = remove_rightmost(t, True, t.left)
            t.value = rightmost_value
            return t

    rv = t
    while t is not None and t.value != q:
        parent = t
        if q < t.value:
            t = t.left
            parent_left = True
        else:
            t = t.right
            parent_left = False

    if t is None:
        return rv

    if parent_left:
        parent.left = delete(t, q)
    else:
        parent.right = delete(t, q)

    return rv


def deleteFromBST(t, queries):
    for q in queries:
        t = delete(t, q)
    return t