1. AVL定義
AVL樹是一種改進版的搜索二叉樹。對于一般的搜索二叉樹而言，如果數(shù)據(jù)恰好是按照從小到大的順序或者從大到小的順序插入的，那么搜索二叉樹就對退化成鏈表，這個時候查找，插入和刪除的時間都會上升到O(n)，而這對于海量數(shù)據(jù)而言，是我們無法忍受的。即使是一顆由完全隨機的數(shù)據(jù)構造成的搜索二叉樹，從統(tǒng)計角度去分析，在進行若甘次的插入和刪除操作，這個搜索二叉樹的高度也不能令人滿意。這個時候大家就希望能有一種二叉樹解決上述問題。這個時候就出現(xiàn)平衡搜索二叉樹，它的基本原理就是在插入和刪除的時候，根據(jù)情況進行調整，以降低二叉樹的高度。平衡搜索二叉樹典型代表就是AVL樹和紅黑樹。
AVL樹：任何一個節(jié)點的左子支高度與右子支高度之差的絕對值不超過1。需要我們注意的是，AVL樹定義不是說從根節(jié)點到葉子節(jié)點的最短距離比最長短距離大1。
上圖就是一顆AVL樹，從根節(jié)點到葉子節(jié)點的最短距離是5，最長距離是9。
2. AVL插入操作
AVL樹的插入操作首先會按照普通搜索二叉樹的插入操作進行，當插入一個數(shù)據(jù)后，我們會沿著插入數(shù)據(jù)時所經(jīng)過的的節(jié)點回溯，回溯的過程中會判回溯路徑中的每個節(jié)點的左子支高度與右子支高度之差的絕對值是否超過1，如果超過1我們就進行調整，調整的目的是使得該節(jié)點滿足AVL樹的定義。調整的情況可以分為以下四旋轉操作，旋轉操作可以降低樹的高度，同時不改變搜索二叉樹的性質（即任何一個節(jié)點左子支中的全部節(jié)點小于該節(jié)點，右子支的全部節(jié)點大于該節(jié)點）。
2.1 情況1，節(jié)點D左子支比右子支高度大2，且插入的節(jié)點位于D的左孩子節(jié)點的左子支上
2.2 情況2，節(jié)點D右子支比左子支高度大2，且插入的節(jié)點位于節(jié)點D右孩子節(jié)點的右子支上
2.3 情況3，節(jié)點D左子支比右子支高度大2，且插入的節(jié)點位于節(jié)點D左孩子節(jié)點的右子支上
