下圖所示的樹是AVL樹,但是,需要在A
的左子樹的左側插入一個元素。樹可能會因關鍵節點A
的存在而變得不平衡。
平衡因子不在-1
和1
之間的節點稱為關鍵節點。要重新平衡樹,執行LL
旋轉,如下圖所示。
節點B
成為根,A
和T3
作為其左右子節點。 T1
和T2
成為A
的左右子樹。
範例:
將值為12
的節點插入下圖所示的樹中。
解決:12
將被插入25
的左側,因此,它擾亂了AVL樹的平衡。 樹需要通過LL旋轉旋轉來重新平衡。
這裡,關鍵節點100
將移動到其右側,並且其左子樹(B)的根將是樹的新根節點。
B
的右子樹,即T2
(具有根節點75
)將位於節點A
的左側(值為100
)。
通過遵循此過程,樹將被重新平衡,因此,它將是在插入12
之後生成的AVL樹。