一、AVL樹(shù)的定義

AVL樹(shù)，全稱 平衡二叉搜索（排序）樹(shù)。

二叉搜索樹(shù)雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹(shù)將退化為單支樹(shù)，查找元素相當(dāng)于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問(wèn)題的方法：當(dāng)向二叉搜索樹(shù)中插入新結(jié)點(diǎn)后，如果能保證每個(gè)結(jié)點(diǎn)的左右子樹(shù)高度之差的絕對(duì)值不超過(guò)1(需要對(duì)樹(shù)中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹(shù)的高度，從而減少平均搜索長(zhǎng)度。

平衡因子（Balance Factor，簡(jiǎn)寫(xiě)為bf）
平衡因子（bf）：結(jié)點(diǎn)的左子樹(shù)的深度減去右子樹(shù)的深度。也可以是右子樹(shù)的深度減去左子樹(shù)的深度。看個(gè)人實(shí)現(xiàn)而異。

即： 結(jié)點(diǎn)的平衡因子 = 左子樹(shù)的高度 - 右子樹(shù)的高度。
或者 節(jié)點(diǎn)的平衡因子 = 右子樹(shù)的高度 - 左子樹(shù)的高度。

AVL樹(shù)本質(zhì)上是一顆二叉查找樹(shù)，但是它又具有以下特點(diǎn)：

• 它的左右子樹(shù)都是AVL樹(shù)
• 左右子樹(shù)高度之差(簡(jiǎn)稱平衡因子)的絕對(duì)值不超過(guò)1(-1/0/1)

這就是一顆AVL樹(shù)

二、AVL樹(shù)的作用

有一顆二叉樹(shù)，他有n個(gè)節(jié)點(diǎn)，如果他是一顆二叉搜索樹(shù)，他形狀多樣，可能會(huì)形成單枝樹(shù)，高度為n,那么在這顆搜索樹(shù)中查找元素的最壞時(shí)間復(fù)雜度為O(n),最好時(shí)間復(fù)雜度是O($lo{g}_{2}n$)。
如果他是一顆AVL樹(shù)，他的高度穩(wěn)定為$lo{g}_{2}n$,查找元素的時(shí)間復(fù)雜度為O($lo{g}_{2}n$)。
由上圖可知，同樣的結(jié)點(diǎn)，由于插入方式不同導(dǎo)致樹(shù)的高度也有所不同。特別是在帶插入結(jié)點(diǎn)個(gè)數(shù)很多且正序的情況下，會(huì)導(dǎo)致二叉樹(shù)的高度是O(N)，而AVL樹(shù)就不會(huì)出現(xiàn)這種情況，樹(shù)的高度始終是O(lgN).高度越小，對(duì)樹(shù)的一些基本操作的時(shí)間復(fù)雜度就會(huì)越小。這也就是我們引入AVL樹(shù)的原因。

三、AVL樹(shù)的插入操作

插入——平衡因子的更新

在插入一個(gè)元素的時(shí)候，必然會(huì)引起平衡因子的變化，所以我們需要在插入的時(shí)候把平衡因子同時(shí)更新，在平衡因子大于1或者小于-1時(shí)，我們則需要進(jìn)行旋轉(zhuǎn)操作，進(jìn)行調(diào)整，使平衡因子再次正常，從而保證這顆二叉樹(shù)一直是一顆AVL樹(shù)。
?
使用平衡因子計(jì)算： 右子樹(shù)高度 - 左子樹(shù)高度

情況一：

在插入元素后，需要更新父節(jié)點(diǎn)的平衡因子，在父節(jié)點(diǎn)的左子樹(shù)插入元素，父節(jié)點(diǎn)的平衡因子-1，在父節(jié)點(diǎn)的左子樹(shù)插入元素，父節(jié)點(diǎn)的平衡因子+1，如果父節(jié)點(diǎn)的平衡因子更新過(guò)后變?yōu)?或者-1，則需繼續(xù)往上更新至根節(jié)點(diǎn)，因?yàn)?或者-1表示該節(jié)點(diǎn)的高度發(fā)生改變，需往上更新。

情況2：

在插入元素后，需要更新父節(jié)點(diǎn)的平衡因子，在父節(jié)點(diǎn)的左子樹(shù)插入元素，父節(jié)點(diǎn)的平衡因子-1，在父節(jié)點(diǎn)的左子樹(shù)插入元素，父節(jié)點(diǎn)的平衡因子+1，如果父節(jié)點(diǎn)的平衡因子更新過(guò)后變?yōu)?，則不需要繼續(xù)向上更新，因?yàn)樽優(yōu)?只能說(shuō)明該樹(shù)高度沒(méi)有變化，只是相對(duì)于原來(lái)變得平衡。

如果在更新平衡因子后，平衡因子不在(-1/0/1)范圍時(shí)，則需旋轉(zhuǎn)操作，下面講解如何進(jìn)行旋轉(zhuǎn)操作

由于插入需要旋轉(zhuǎn)的情況較多，大致可以分為四大類

插入——左單旋

動(dòng)圖演示

情況一
右子樹(shù)高時(shí)，在右子樹(shù)的右側(cè)插入元素，此時(shí)需要左單旋

插入——右單旋

動(dòng)圖演示

情況二、
左子樹(shù)較高時(shí)，在左子樹(shù)的左側(cè)插入元素，此時(shí)需要右單旋

插入——左右雙旋

情況三、左子樹(shù)較高時(shí)，在左子樹(shù)的右側(cè)插入元素，此時(shí)需要左右雙旋，即：先對(duì)30進(jìn)行左單旋，然后再對(duì)90進(jìn)行右單旋

插入——右左雙旋

情況四、右子樹(shù)較高時(shí)，在右子樹(shù)的左側(cè)插入元素，此時(shí)需要右左雙旋，即：先對(duì)90進(jìn)行右單旋，然后再對(duì)30進(jìn)行左單旋

四、ALVL樹(shù)的驗(yàn)證

int _Height(Node* root)
{//用來(lái)計(jì)算二叉樹(shù)的高度if (root == NULL)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;
}bool _IsBalance(Node* root)
{if (root == NULL)return true;int leftH = _Height(root->_left);int rightH = _Height(root->_right);//檢查平衡因子if (rightH - leftH != root->_bf){cout << root->_kv.first << "節(jié)點(diǎn)平衡因子異常" << endl;return false;}//通過(guò)計(jì)算左右子樹(shù)的高度差判斷這顆二叉樹(shù)是否為AVL樹(shù)return abs(leftH - rightH) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);//檢查高度差要檢查二叉樹(shù)中所有節(jié)點(diǎn)的左右子樹(shù)的高度差
}bool IsBalance()
{return _IsBalance(_root);
}

五、AVL樹(shù)的性能

AVL樹(shù)是一棵絕對(duì)平衡的二叉搜索樹(shù)，其要求每個(gè)節(jié)點(diǎn)的左右子樹(shù)高度差的絕對(duì)值都不超過(guò)1，這樣可以保證查詢時(shí)高效的時(shí)間復(fù)雜度，即 $lo{g}_{2}n$ 。

但是如果要對(duì)AVL樹(shù)做一些結(jié)構(gòu)修改的操作，性能非常低下，比如：插入時(shí)要維護(hù)其絕對(duì)平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時(shí)，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。因此：如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個(gè)數(shù)為靜態(tài)的(即不會(huì)改變)，可以考慮AVL樹(shù)，但一個(gè)結(jié)構(gòu)經(jīng)常修改，就不太適合。