實作刪除方法

從 AVL 樹中刪除元素與從 BST 中刪除元素相同，只是樹可能需要重新平衡。如同從 BST 中刪除元素一節中討論的，要從二元樹中刪除元素，演算法首先找到包含該元素的節點。令 current 指向二元樹中包含該元素的節點，而 parent 指向 current 節點的父節點。 目前節點可能是父節點的左子節點或右子節點。
刪除元素時會出現兩種情況。

情況1：目前節點沒有左子節點，如下圖(a)所示。要刪除 current 節點，只需將 parent 節點與 current 節點的右子節點連接起來，如下圖 (b) 所示。從 parent 節點到 root 的路徑上的節點高度可能已減少。為了確保樹是平衡的，呼叫

balancePath(parent.element);

情況 2：目前 節點有左子節點。令rightMost 指向包含current 節點左子樹中最大元素的節點，parentOfRightMost指向rightMost 的父節點節點， a)所示。 rightMost 節點不能有右子節點，但可以有左子節點。將current 節點中的元素值替換為rightMost 節點中的元素值，將parentOfRightMost 節點與rightMost 節點，刪除rightMost節點，如下圖(b)。

從

parentOfRightMost 到根的路徑上的節點高度可能會減少。為了確保樹是平衡的，呼叫

balancePath(parentOfRightMost);

以上是實作刪除方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！