AVL（Adelson-Velskii和Landis）樹是帶有平衡條件的二叉查找樹。
一棵AVL樹是其每個節點的左子樹和右子樹的高度最多差1的二叉查找樹。（空子樹的高度定義為-1）
AVL樹的每一個節點（在其節點結構中）保留高度資訊。
在高度為h的AVL樹中，最少節點數S（h）由S（h）=S（h-1）+S（h-2）+1給出。對于h=0，S（h）=1；h=1，S（h）=2。可以看出函數S（h）與斐波那契數密切相關。
向一個AVL樹種插入一個節點可能破壞AVL樹的特性，如果發生這種情況，那麼就要把性質恢複以後才認為這一步插入完成。事實上，這總可以通過對樹進行簡單的修正來做到，我們稱其為旋轉（rotation）。
在插入以後，隻有那些從插入點到根節點的路徑上的節點的平衡可能被改變，因為隻有這些節點的子樹可能發生變化。當我們沿着這條路徑上行到根并更新平衡資訊時，我們可以找到一個節點，它的新平衡破壞了AVL條件（沿着此路徑上行遇到的第一個不平衡的節點，也就是距離插入節點最近的那個不平衡節點，或者說是最深的那個不平衡節點）。
我們把必須重新平衡的節點叫做A。高度不平衡時，A節點的兩棵子樹的高度必定差2。容易看出，這種不平衡可能出現在下面四種情況中：
1. 對A的左兒子的左子樹進行一次插入。（左-左）——外部
2. 對A的左兒子的右子樹進行一次插入。（左-右）——内部
3. 對A的右兒子的左子樹進行一次插入。（右-左）——内部
4. 對A的右兒子的右子樹進行一次插入。（右-右）——外部
情形1和4是關于A節點的鏡像對稱，而2和3也是關于A節點的鏡像對稱。是以，理論上隻有兩種情況，當然從程式設計的角度來看還是四種情形。
第一種情況是插入發生在“外部”的情況（左-左或右-右），該情況通過對樹的一次單旋轉（single rotation）而完成調整。
第二種情況是插入發生在“内部”的情況（左-右或右-左），該情況通過稍微複雜的雙旋轉（double rotation）來處理。
針對“左-左”、“右-右”式插入新節點而導緻的不平衡使用單旋轉即可恢複平衡，具體操作如下（我們依然假設插入後必須重新平衡的節點為A，并假設樹的所有節點處都是靈活可動的）：
如果是“左-左”式插入導緻不平衡（如圖1所示），（我們假設節點A的左兒子節點是B）我們隻需用兩個手指捏住節點B，就這麼往上一提（提到原來A的高度就可以了），想象一下這時是不是已經平衡了不過可能出現這樣的問題：如果旋轉之前節點B有右兒子，那麼旋轉後節點B豈不是會有兩個右兒子了，因為旋轉後節點A也會成為B的右兒子，這時隻需将B原來的右兒子送給節點A就行了，并且讓它做節點A的左兒子（如圖2所示）。
圖 1
圖 2
如果了解了“左-左”式插入不平衡的單旋轉調整，那麼“右-右”式自然也就掌握了：不同之處隻是現在我們需要兩個手指捏住A的右兒子往上一提就可以了，并且如果旋轉前A的右兒子有左兒子，隻需在旋轉後将此左兒子送給A做A的右兒子即可。
針對“左-右”、“右-左”式插入新節點而導緻的不平衡需要使用雙旋轉才可恢複平衡。
如果是“左-右”式插入導緻的不平衡（如圖3所示），能看懂“左-右”，那麼“右-左”也自然明白了，不再贅述。理論上講，雙旋轉相當于做了兩次單旋轉；實際上就記做直接将孫子替換到我的位置上，然後妥善安排父親和我，這樣更簡單些。
同單旋轉中一樣，也有可能孫子本身還有它自己的兒子，隻需按照二叉查找樹的特性将孫子的兒子安排給父親和爺爺照料（做它們的兒子）就行了。
最後強調一點：我、兒子、孫子都是在從插入點上行到根節點這條路徑上。