在 Avl 树上,当您删除一个有 2 个子节点的节点时。我知道您可以用它的后继(右子树上的最小值)或它的前导(左子树上的最大值)替换它。
我的问题是:在标准中,我要与节点交换哪个子树? 继任者还是前任?
谢谢! :)
最佳答案
只要您之后进行了所有必要的重新平衡,您就可以使用其中任何一种 - 算法以任何一种方式运行。
如果您想变得非常聪明,您可以根据之后需要最少的重新平衡来选择其中一个。不过,这比总是选择下一个更大或下一个更小的 key 要复杂得多。
关于c++ - 哪个子树在 Avl 树删除中具有更高的优先级,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12699103/