AVL樹——深入淺出，一目了然

歡迎轉載，請附出處：

http://blog.csdn.net/as02446418/article/details/47306419

以前總對AVL樹有疑惑，到底什麼時候左旋什麼時候右旋，什麼時候雙旋，雙旋和單旋的情況到底是什麼樣的呢？

看完本篇部落格，相信你也能夠一目了然了。

這裡聲明一下

左旋為：逆進針旋轉。

右旋為：順進針旋轉。

情況：

（1）LL：插入一個新節點到根節點的左子樹（Left）的左子樹（Left），導緻根節點的平衡因子由1變為2

（2）RR：插入一個新節點到根節點的右子樹（Right）的右子樹（Right），導緻根節點的平衡因子由-1變為-2

（3）LR：插入一個新節點到根節點的左子樹（Left）的右子樹（Right），導緻根節點的平衡因子由1變為2

（4）RL：插入一個新節點到根節點的右子樹（Right）的左子樹（Left），導緻根節點的平衡因子由-1變為-2

處理辦法：

（1）LL情況需要根右旋解決，如下圖的情況1和2

（2）RR情況需要根左旋解決，如下圖的情況3和4

（3）LR情況需要左右旋（先左子樹左旋轉，後根部右旋轉）解決，如下圖情況5和6

（4）RL情況需要右左旋（先右子樹右旋轉，後根部左旋轉）解決，如下圖情況7和8

直接上圖。