AVL旋轉樹

 執行插入操作可能出現不平衡的情況，當平衡二叉樹。AVL這樹是一種自平衡二叉樹，使二叉樹又一次保持平衡。而且查找、插入和删除操作在平均和最壞情況下時間複雜度都是O(log n)

      AVL樹的旋轉一共同擁有四種情形。注意全部旋轉情況都是環繞着使得二叉樹不平衡的第一個節點展開的。

1. LL型

    平衡二叉樹某一節點的左孩子的左子樹上插入一個新的節點，使得該節點不再平衡。這時僅僅須要把樹向右旋轉一次就可以，如圖所看到的。原A的左孩子B變為父結點，A變為其右孩子，而原B的右子樹變為A的左子樹，注意旋轉之後Brh是A的左子樹（圖上忘在A于Brh之間标實線）

2. RR型

    平衡二叉樹某一節點的右孩子的右子樹上插入一個新的節點，使得該節點不再平衡。這時僅僅須要把樹向左旋轉一次就可以。如圖所看到的，原A右孩子B變為父結點。A變為其左孩子。而原B的左子樹Blh将變為A的右子樹。

3. LR型

      平衡二叉樹某一節點的左孩子的右子樹上插入一個新的節點。使得該節點不再平衡。這時須要旋轉兩次，僅一次的旋轉是不可以使二叉樹再次平衡。

如圖所看到的，在B節點依照RR型向左旋轉一次之後，二叉樹在A節點仍然不能保持平衡，這時還須要再向右旋轉一次。

4. RL型

      平衡二叉樹某一節點的右孩子的左子樹上插入一個新的節點，使得該節點不再平衡。

相同。這時須要旋轉兩次。旋轉方向剛好同LR型相反。

版權聲明：本文部落客原創文章。部落格，未經同意不得轉載。