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