右右(RR)旋轉

2019-10-18 00:56:14

如果節點插入節點A的右子樹的右側並且樹變得不平衡,那麼在這種情況下,將執行RR 旋轉,如下圖所示。

在旋轉時,節點B成為樹的根節點。 關鍵節點A將向左移動並成為B的左子節點。

子樹T3成為A的右子樹,T1T2成為節點A的左右子樹。

範例
90插入到圖中所示的AVL樹中。

解決方案:
90插入右子樹的右側。 在這種情況下,關鍵節點A將是85,這是新節點的最接近的祖先,其平衡因子受到干擾。 因此,需要通過對其應用RR旋轉來重新平衡樹。

節點B將是節點90,它將成為子樹的根節點。 關鍵節點85將成為其左子節點,以便產生現在是AVL樹的重新平衡樹。