首页 文章

删除BST中的多个节点会更改生成的树?

提问于
浏览
0

如果我需要删除BST中的多个节点,结果树是否会改变删除顺序?正常的左右顺序将被保留,但我不确定树结构 .

这是一个“phisolophical”问题,我需要对它进行调整或反例 .

2 回答

  • 1

    为了证明删除顺序对最终树没有影响,有必要并且足以证明任何两个删除操作都是通勤的(也就是说,如果它们的顺序颠倒它们会产生相同的效果) .

    删除节点的效果仅限于该节点及其作为根节点的子树 . 因此,如果两个节点是分开的(即两个节点都不在另一个节点之下)那么它们的删除是通勤的 . 因此,唯一感兴趣的案例在另一个子树中有一个节点 .

    在不失一般性的情况下,假设我们使用以下规则:当我们删除具有两个子节点的节点时,我们将其替换为其后继节点 . 我们'll call the higher one A and the lower one B. If B is in A' s左子树,然后删除通勤,因为删除A对A的左子树没有影响,并且删除B在A 's left subtree. So the only case of interest is when B is in A' s右子树之外没有影响 .

    删除A时,已删除对A 's right subtree is the same as if A' s后继者的影响 . 假设B不是A 's successor; we' ll调用A 's successor C. The deletion of A consists of the deletion of C from the right subtree and the replacement of A with C (which commute), so if the deletions of B and C commute, then the deletion of A and B commute. By induction, if any pair of deletions do not commute, then the deletion of A and B where B is A' s后继者不通勤 .

    但删除A及其继任者的确通过检查来减少 . 证明完毕

  • 2

    Deleting 1 and 2 in different order results in two different trees反例:删除1和2的顺序会产生不同的BST . 因为当你想要首先删除2时,你必须在它的右子树中找到下一个元素,即3并将其替换为2,但是当你先删除1然后你要删除2时,现在它只有一个孩子,只是它的孩子取代它,即4 . 因此导致两种不同的树木 .

相关问题