binary-search-tree - 二叉子树中的删除

Question

在这种情况下，我试图删除一个具有左右子节点的节点 D。

                 D
                /  \ 
               A    F 
                \
                 B

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

Answer 1

你可以，但它不会是最佳的。您希望您的树始终尽可能平衡，以便插入和删除将保持在 O(log n) 左右

Answer 2

首先，只有一棵二叉树是未排序的。我假设你的树是二叉搜索树。如果您想要的只是保持树排序而不是 yes，则可以在此特定示例中将其替换为 F。如果您的树更复杂，那么您将无法在没有其他操作的情况下执行此操作 - 例如，您需要对 F 的子项（如果存在）执行某些操作，并且需要额外的不必要的处理。