algorithm - 从具有 2 个节点的二叉搜索树中删除一个节点，是否可以使用不同的方法？

Question

我到处都在寻找这个，但只有一种方法:

1. find predecessor (or successor) of node to delete
2. replace node with predecessor (or successor)
3. delete predecessor (or successor)

但我觉得我们也可以这样做:

pulloff the right(or left) element to the node to delete i.e just replace the element to delete with right (or left) element and keep doing it till we encounter the leaf and then delete the leaf. In brief, keep replacing element to delete with its right(or left) element and keep doing it till we reach the leaf , and then delete the leaf.

那么这个方法对吗？

Answer 1

不幸的是CoderAj，Vikhram提供的解决方案是删除BST中节点的正确方法。您的方法听起来不错，但在第一次更换时失败了。

让我们在树上算出你的方法。

                          8
                  5               25
            3          7     23        30
                    6           24  27    35

让我们删除根，即 8
第一步:

                      25             //replaced 8 by 25
              5               25
        3          7     23        30
                6           24  27    35

23 和 24 小于 25，仍然在它的右子树中。

因此，你的最终树看起来像这样

                      25
              5               30
        3          7     23        35
                6           24  27    

它看起来不像二叉搜索树。