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