在Avl樹刪除中哪個子樹具有更高的優先級

Question

在Avl樹上，當您刪除具有2個子節點的節點時..我知道您可以用其後繼者（右側子樹上的最小值）或其替換項前任（左子樹上的最大值）。

我的問題是：在標準中，我與節點交換哪個子樹？ 繼任者還是前任？

謝謝！ :)

Answer 1

只要您事後做了所有必要的重新平衡，您可以使用其中任何一種 - 該算法無論哪種方式。

如果你想要非常聰明，你可以選擇一個基於哪一個需要最少的重新平衡之後。不過，這比選擇下一個更大或更小的按鍵要複雜得多。