AVL樹是高度平衡的而二叉樹。它的特點(diǎn)是：AVL樹中任何節(jié)點(diǎn)的兩個子樹的高度最大差別為1。
如果在AVL樹中進(jìn)行插入或刪除節(jié)點(diǎn)后，可能導(dǎo)致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態(tài)：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面給出它們的示意圖：
image.png
上圖中的4棵樹都是"失去平衡的AVL樹"，從左往右的情況依次是：LL、LR、RL、RR。除了上面的情況之外，還有其它的失去平衡的AVL樹，如下圖：
image.png
針對四種失去的平衡姿態(tài)怎么恢復(fù)平衡
1.LL旋轉(zhuǎn)
image.png
2.RR旋轉(zhuǎn)
image.png
3.LR旋轉(zhuǎn)
image.png
4.RL旋轉(zhuǎn)
image.png
參考
AVL樹(三)之 Java的實現(xiàn)
