c++ - Avl 树删除中哪个子树的优先级更高

Question

在 Avl 树上，当您删除具有 2 个子节点的节点时。我知道您可以将其替换为其后继节点（右子树上的最小值）或其前身（左子树上的最大值）。

我的问题是：在标准中，我与节点交换到哪个子树？继任者还是前任者？

谢谢！:)

Answer 1

只要您事后进行所有必要的重新平衡，您就可以使用其中任何一种——算法可以通过任何一种方式运行。

如果您想变得非常聪明，您可以根据之后需要最少重新平衡的情况来选择其中一个。不过，这比总是选择下一个更大或更小的键要复杂得多。