什麼是三節點重構AVL樹？

Question

我已經搜索了一下，但沒有發現很多，不知道從哪裏開始。

假設你有一個簡單的AVL樹：

 2 
    /\ 
    1 3 

要刪除一個節點，那麼你必須要恢復AVL財產。當一個人指出在刪除一個值後引起了多少三重結構重組時，這是什麼意思？

Answer 1

如果我記得正確的話，如果AVL樹被更新，在某些情況下，必須執行不同的重新平衡操作來維持樹的不變性，即作爲搜索樹並且是平衡的（具有以對數爲界的高度節點數量）。爲了決定哪種重新平衡操作是必要的，最多需要考慮三個節點。旋轉操作在Wikipedia article中描述。您在問題中提出的例子可能太小，不足以導致此類操作的必要性。