在二进制SubTree中删除

Question

我正在尝试删除一个节点，该节点在本例中有一个左子节点和一个右子节点。

                 D
                /  \ 
               A    F 
                \
                 B

所以当我尝试删除D时，我应该用B替换它，因为B是左子树中下一个最大的元素。所以我可以用F代替它而不是B？

Answer 1

你可以，但它不会是最优的。您希望您的树总是尽可能平衡，以便插入和删除操作保持在O(log )附近。

Answer 2

首先，只有一个二叉树是未排序的。我假设你的树是一个二进制搜索树。如果您想要的只是保持树的排序，那么对于这个特定的示例，您可以将其替换为F。如果你的树更复杂，你将无法在没有额外操作的情况下做到这一点-例如，你需要对F的孩子做一些事情，如果有的话，这将需要额外的不必要的处理。