重寫插入方法

將元素插入 AVL 樹與將其插入 BST 相同，只是樹可能需要重新平衡。新元素始終作為葉節點插入。新增節點後，新葉節點祖先的高度可能會增加。插入新節點後，檢查從新葉節點到根節點的路徑上的節點。如果發現不平衡節點，請使用下面程式​​碼中的演算法執行適當的旋轉。

1 平衡路徑(E e) {
2 取得包含元素e的節點到根的路徑，
3如圖26.9所示；
4 對於通往根的路徑中的每個節點 A {
5 更新A的高度；
6 令parentOfA 表示A 的父級，
7 是路徑中的下一個節點，如果 A 是根，則為 null；
8
9 開關 (balanceFactor(A)) {
10 情況-2：如果balanceFactor(A.left) == -1或0
11 執行LL旋轉； //見圖26.2
其他 12 個
13 進行左右旋轉； //見圖26.4
14 休息；
15 情況+2：如果balanceFactor(A.right) == +1或0
16 執行RR輪換； //見圖26.3
其他 17 個
18 進行RL旋轉； //見圖26.5
19 } // 切換結束
20 } // for
結束 21 } // 方法結束

演算法考慮從新葉節點到根的路徑中的每個節點。更新路徑上節點的高度。如果節點是平衡的，則無需執行任何操作。如果節點不平衡，則執行適當的旋轉

以上是重寫插入方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！