如果節點插入節點A的右子樹的右側並且樹變得不平衡,那麼在這種情況下,將執行RR 旋轉,如下圖所示。
在旋轉時,節點B
成為樹的根節點。 關鍵節點A
將向左移動並成為B
的左子節點。
子樹T3
成為A
的右子樹,T1和T2成為節點A
的左右子樹。
範例
將90
插入到圖中所示的AVL樹中。
解決方案:
將90
插入右子樹的右側。 在這種情況下,關鍵節點A
將是85
,這是新節點的最接近的祖先,其平衡因子受到干擾。 因此,需要通過對其應用RR
旋轉來重新平衡樹。
節點B
將是節點90
,它將成為子樹的根節點。 關鍵節點85
將成為其左子節點,以便產生現在是AVL
樹的重新平衡樹。