3、旋轉
在進行插入和删除之前需要先了解AVL樹的旋轉操作。旋轉操作主要包括LL（左左）旋轉、LR（左右）旋轉、RR（右右）旋轉、RL（右左）旋轉，LL旋轉與RR旋轉對稱，LR旋轉與RL旋轉對稱。旋轉操作是在插入結點或删除結點導緻原AVL樹不平衡時進行的。我的了解是當二叉樹失衡的原因出現在“最低失衡根結點左子樹的左子樹”（所謂“最低失衡根結點”，則是從新增結點開始向根部回溯，所遇到的第一個失衡的根節點）時，則使用LL旋轉來調整；當失衡出現在“最低失衡根節點左子樹的右子樹”，則使用LR旋轉調整；RR旋轉，RL旋轉同理。具體的定義和操作可以看skywang12345的的文章：AVL樹(二)之 C++的實作（我的這篇文章就是基于此文章，為了加深印象，在這裡把實作再寫一遍，加一些自己的了解）。
3.1 LL旋轉
如上圖所示，找到“最低失衡根結點”，上圖是結點5，二叉樹失衡的原因是因為結點1的存在，而結點1位于結點5“左子樹的左子樹”，是以要使用LL旋轉來調節，隻需一次旋轉即可達到平衡。具體的方法是：LL旋轉的對象是“最低失衡根結點”，也就是結點5，找到5的左孩子3，将3的右孩子4變成5的左孩子，最後将5變成3的右孩子，調整後的AVL樹如下所示：
具體代碼：
3.2 RR旋轉
RR旋轉與LL旋轉對稱。
如上圖所示，“最低失衡根結點”是結點2，二叉樹的失衡是結點6導緻的，而結點6位于結點2“右子樹的右子樹”，是以要使用RR旋轉來調節，隻需一次旋轉即可達到平衡。方法與LL旋轉類似：RR旋轉的對象是“最低失衡根結點”，這裡是結點2，找到2的右孩子4，将4的左孩子3變成2的右孩子，最後将2變成4的右孩子，旋轉後的結果如下圖所示：
RR旋轉代碼如下：
3.3 LR旋轉
LL旋轉和RR旋轉隻需一次旋轉即可達到平衡，而LR旋轉和RL旋轉需兩次旋轉才能達到平衡。
如上圖所示，“最低失衡根結點”為結點5，二叉樹失衡是因為結點3的存在，結點3位于結點5“左子樹的右子樹”，是以使用LR旋轉來調節。方法：（1）先對最低失衡根結點的左孩子（結點2）進行RR旋轉；（2）再對最低失衡根結點（結點5）進行LL旋轉。下圖示範了調整過程。
LR代碼如下：
3.4 RL旋轉
RL旋轉與LR旋轉對稱，先LL旋轉，在RR旋轉。
分析過程與LR相似。旋轉步驟：（1）先對最低失衡結點右孩子（結點5）LL旋轉；（2）在對最低失衡結點（結點2）RR旋轉。旋轉過程如下：
RL實作代碼：
4、插入結點與删除結點
------------------越是喧嚣的世界，越需要甯靜的思考------------------
合抱之木，生于毫末；九層之台，起于壘土；千裡之行，始于足下。
積土成山，風雨興焉；積水成淵，蛟龍生焉；積善成德，而神明自得，聖心備焉。故不積跬步，無以至千裡；不積小流，無以成江海。骐骥一躍，不能十步；驽馬十駕，功在不舍。锲而舍之，朽木不折；锲而不舍，金石可镂。蚓無爪牙之利，筋骨之強，上食埃土，下飲黃泉，用心一也。蟹六跪而二螯，非蛇鳝之穴無可寄托者，用心躁也。