右右(RR)旋轉

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

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

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

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

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

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


上一篇: 平衡搜索樹(AVL樹) 下一篇: B樹