我正在嘗試實作 AVL 樹作為實踐。對于插入和洗掉操作，我的實作首先執行正常的 BST 插入和洗掉，然后沿著父鏈向上檢查并修復任何不平衡的子樹。但是，當不平衡節點的子節點的平衡因子為 0 時，我不確定如何在 zig-zig 和 zig-zag 情況之間做出決定。我想在這種情況下我可以選擇其中一個，但這不是洗掉作業。
假設樹看起來像這樣，我想洗掉 78，
重新平衡方法會走到 70（根），發現它不平衡，那么問題來了：因為 44 的平衡因子為 0，我應該在 70-44-33 上執行 Zig-zig 案例，還是 Zig - 70-44-48 上的 zag 案例？
后者將無法平衡樹。向左旋轉 44 度，然后向右旋轉 70 度會產生以下結果：
另一方面，之字形案例（右旋轉 70 度左右）是正確的方法： 
uj5u.com熱心網友回復：
對 AVL 樹使用“zig zag”術語是不尋常的。該術語對于 Splay 樹（也是平衡樹）更常見，其目的是通過旋轉將特定節點冒泡到頂部。在 AVL 樹中沒有這樣的目的。AVL 樹的術語包括簡單旋轉（從左到右或反之亦然）和雙旋轉（兩個簡單旋轉的組合）。
當洗掉一個節點后，您在樹中向上移動，并發現平衡違規時，這意味著該節點中臨時更新的平衡因子是 -2 或 2。
如果重側的子節點具有相反符號的平衡因子（因此，當其不平衡的父代為 -2 時為 1；或當其不平衡的父代為 2 時為 -1），則需要雙重旋轉。在所有其他情況下，都需要簡單的旋轉。
內重孫的情況，需要雙輪轉，描述如下（復制自
在您的示例中，節點 44 的平衡因子為 0，因此不需要雙重旋轉，您應該只從左到右旋轉根。如果我們想象同一棵樹，但沒有節點 31 和 34（使 33 成為葉子），那么 44 處的平衡因子將為 1（與 70 處的 -2 的符號相反），并且需要雙重旋轉。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/346255.html