前言

前面對map/multimap/set/multiset進行了簡單的介紹，在其文檔介紹中發(fā)現(xiàn)。
這幾個容器有個共同點是：其底層都是按照二叉搜索樹來實現(xiàn)的，但是二叉搜索樹有其自身的缺陷，假如往樹中插入的元素有序或者接近有序，二叉搜索樹就會退化成單支樹，時間復(fù)雜度會退化成O(N)，因此map、set等關(guān)聯(lián)式容器的底層結(jié)構(gòu)是對二叉樹進行了平衡處理，即采用平衡樹來實現(xiàn)。

那這篇文章我們就重點來學(xué)習(xí)一種平衡搜索二叉樹——AVL樹

1. AVL樹的概念

二叉搜索樹雖可以提升查找的效率，但如果數(shù)據(jù)有序或接近有序時二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。

因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：

當(dāng)向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整)，即可降低樹的高度，使整棵搜索樹達到一個相對平衡的狀態(tài)，從而減少平均搜索長度。

那大家思考一個問題：為什么是每個結(jié)點左右子樹高度之差的絕對值不超過1，為什么不能是兩邊一樣高，高度差為0呢？

??，如果能達到左右子樹完全一樣高固然是最好的，但是關(guān)鍵在于有些情況不可能實現(xiàn)兩邊絕對平衡！
比如

兩個結(jié)點、4個結(jié)點的情況，當(dāng)然肯定不止這些。大家看這種情況能實現(xiàn)兩邊完全平衡嗎？
是不行的，無法達到完全平衡。

所以，什么是平衡二叉樹呢？

一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：

1. 它的左右子樹都是AVL樹
2. 左右子樹高度之差(簡稱平衡因子，一般是右子樹-左子樹的高度差，當(dāng)然左-右也可以)的絕對值不超過1（-1/0/1）
   ps：圖中每個結(jié)點旁邊的數(shù)字就是其對應(yīng)的平衡因子
   如果一棵二叉搜索樹是高度平衡的（即滿足任何一個結(jié)點的平衡因子都在[-1, 0, 1]這個范圍內(nèi)），它就是AVL樹。如果它有n個結(jié)點，其高度可保持在$O(lo{g}_{2}n)$，搜索的時間復(fù)雜度O($lo{g}_{2}n)$。

2. AVL樹結(jié)構(gòu)的定義

那我們這里以KV模型的結(jié)構(gòu)來講解，當(dāng)然本質(zhì)都是一樣的

首先我們來寫一下結(jié)點的結(jié)構(gòu)

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K,V>* _right;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;//balance factor（平衡因子）

	AVLTreeNode(const pair<K,V>& kv)
		:_right(nullptr)
		,_left(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

這里我們給結(jié)點增加一個_parent指針指向它的父親結(jié)點，方便我們后續(xù)進行某些操作，當(dāng)然帶來方便的同時我們也需要去維護每個結(jié)點的_parent指針，相應(yīng)也帶來了一些麻煩。
這個后面我們實現(xiàn)的時候大家就會體會到。

然后AVL樹的結(jié)構(gòu)

template <class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	//成員函數(shù)
private:
	Node* _root = nullptr;
};

那然后我們來寫一下插入吧

3. 插入（僅僅是插入過程）

AVL樹就是在二叉搜索樹的基礎(chǔ)上引入了平衡因子來控制樹的相對平衡，因此AVL樹也可以看成是二叉搜索樹。

所以插入的邏輯其實跟搜索二叉樹是一樣的，不同的地方在于平衡二叉樹插入之后如果整棵二叉樹或者其中某些子樹不平衡了我們要對插入的結(jié)點進行調(diào)整使得它重新變的平衡，那這個我們后面單獨講。

由于插入的邏輯我們之前已經(jīng)講過了，所以這里我就直接上代碼了（這里我們選擇非遞歸）

不過需要注意的是我們這里插入新結(jié)點之后還要鏈接_parent指針。

bool insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			parent = cur;
			ccur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}

	cur = new Node(kv);
	if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	//鏈接父親指針
	cur->_parent = parent;
	//更新平衡因子
	//...
	return true;
}

大家看著代碼再過一遍這個插入的過程。

那現(xiàn)在我問大家，AVL樹的插入寫到這里就完了嗎？
??，如果是普通的搜索樹，這就完事了，但是，對于AVL樹來說，還遠遠沒有結(jié)束。

4. 平衡因子的更新

為了實現(xiàn)平衡二叉樹，我們引入了一個新的概念，不知道大家還記不記得是啥？

??，就是我們上面提到的平衡因子。
再來回顧一下什么是平衡因子？
一個結(jié)點的平衡因子就是它的左右子樹的高度差，一般是右子樹減左子樹的高度（我們這里的講解也統(tǒng)一以右子樹-左子樹的高度作為平衡因子）。

4.1 為什么要更新平衡因子？

那大家想一下：我們在AVL樹中插入了一個新結(jié)點之后，會不會影響到樹中結(jié)點的平衡因子？

毋庸置疑，這當(dāng)然是會的！
因為一旦插入了新的結(jié)點，整棵樹的高度或者某些子樹的高度必然會發(fā)生變化，那樹的高度發(fā)生變化，必然會影響與之關(guān)聯(lián)的結(jié)點的平衡因子。

所以，插入了新結(jié)點之后，導(dǎo)致某些樹的高度發(fā)生變化，我們要更新平衡因子。

??，那平衡因子會變化，這沒啥說的，但是為啥變化了我就得更新呢？不更新行不行？

答案是不行。
為什么呢？
因為上面我們說了，如果一棵二叉搜索樹是AVL樹，那么它必須滿足任何一個結(jié)點的平衡因子都在[-1, 0, 1]這個范圍內(nèi)。
而現(xiàn)在插入新結(jié)點會導(dǎo)致平衡因子變化，那么更新之后，某些結(jié)點的平衡因子可能就不在[-1, 0, 1]這個正常范圍內(nèi)了。
那他就不是一棵AVL樹了，所以我們才要更新平衡因子，以此來判斷這個樹還是否是一棵AVL樹。
如果不是了，即有結(jié)點的平衡因子不在正常范圍內(nèi)了，那這棵樹的平衡就受到影響了，那我們就需要對新插入的結(jié)點進行調(diào)整，使他變回AVL樹。
當(dāng)然如果插入之后平衡沒有受到影響，就不需要調(diào)整了。

那調(diào)整結(jié)點的事，我們后面再說，現(xiàn)在先談一談，插入新結(jié)點后，如何更新平衡因子！

4.2 如何更新平衡因子？

那首先大家思考一個問題，插入一個新結(jié)點之后，可能會影響到哪些結(jié)點的平衡因子？

是不是影響的肯定是它的祖先啊。
因為新插入的結(jié)點在它祖先的子樹上，那它祖先的子樹高度發(fā)生變化，平衡因子必然也會發(fā)生變化。
但是會影響所有的祖先嗎？
不一定！可能只影響一部分。
比如：

所以具體影響了幾個祖先要根據(jù)具體情況具體分析。

那既然要更新，我就來研究一下更新的規(guī)律：

那這個規(guī)律呢，其實也很容易得出：
因為平衡因子的計算是右子樹高度-左子樹高度嘛。
所以，對于新結(jié)點的父親來說：

1. 如果插入在了右子樹，那么父親的平衡因子就要++
2. 如果插入在了左子樹，那么父親的平衡因子就要- -

即

這時候我們的parent指針的作用就體現(xiàn)出來了

4.3 parent更新后，是否需要繼續(xù)往上更新？

那父親結(jié)點的平衡因子更新完之后，還要不要繼續(xù)往上更新呢？

首先parent肯定要更新，因為插入之后它的子樹的高度變了。
所以大家先想一下，什么情況下parent更新完之后還要繼續(xù)往上更新parent的祖先？
??，是不是取決于parent所在的這棵子樹的高度有沒有發(fā)生變化啊。

1. 如果插入之后parent這棵子樹的高度沒有變化，那就不會影響parent再往上結(jié)點（即parent的祖先）的平衡因子，就不需要往上繼續(xù)更新了
   
2. 如果插入之后parent這棵子樹的高度發(fā)生了變化，那parent的平衡因子更新完成后就需要繼續(xù)往上更新
   

那我們分析一下其實分為這三種情況：

1. 如果parent的平衡因子更新之后為1或-1，則parent這棵樹的高度發(fā)生變化，需要繼續(xù)向上更新

為什么呢？為什么parent的平衡因子變成1或-1，它的高度就變了呢？

我們剛才是不是分析過，插入一個新結(jié)點，它的parent的平衡因子是怎么變化的，是不是要么-1，要么+1啊。
那它現(xiàn)在更新之后變成了1或者-1，能夠說明什么？
是不是說明它更新之前的平衡因子一定是0啊，0的話說明他兩邊高度是平衡的，而現(xiàn)在插入之后變?yōu)?或-1，說明右邊或者左邊高了，因此高度肯定是變化了，那就要繼續(xù)往上更新。
那繼續(xù)往上更新是不是又是同樣的邏輯啊（我們只需將結(jié)點往上走，下次循環(huán)自然會進行同樣的處理，后面代碼實現(xiàn)出來大家會更清晰）。

那可能是-2或者2加一減一之后變成-1或1啊？

不可能，因為AVL樹的平衡因子的范圍都是在[-1, 0, 1]內(nèi)的。

2. parent的平衡因子更新之后為2或-2

如果是2或-2呢？要繼續(xù)往上更新嗎？

??，如果是2或-2，那已經(jīng)不在平衡因子的正常范圍內(nèi)了，那就說明當(dāng)前parent所在的這棵子樹已經(jīng)不平衡了?。。。ㄍǔ０堰@棵樹叫做最小不平衡子樹）
那還往上更新個屁啊，是不是就要去調(diào)整結(jié)點是這棵最小不平衡子樹重變平衡。
那怎么調(diào)整呢，要進行旋轉(zhuǎn)，具體怎么做后面再講。
那旋轉(zhuǎn)之后它的高度其實就恢復(fù)到插入之前了，也就不需要再繼續(xù)往上更新了。

3. parent的平衡因子更新之后為0

那為0的話需要繼續(xù)更新嗎？

為0當(dāng)然就不需要了。
為什么呢？
大家想，更新之后為0的話，是不是說明插入之前它的平衡因子為1或者-1啊，然后我們在左邊插入了一個結(jié)點或者是右邊，然后它的平衡因子就變成了0

那他的高度是不是沒有發(fā)生變化啊，所以不需要繼續(xù)更新，也不需要調(diào)整，插入就結(jié)束了。

4.4 平衡因子更新代碼實現(xiàn)

我們來寫一下代碼：

因為不知道要向上更新幾次，所以肯定是一個循環(huán)。
那循環(huán)什么時候結(jié)束？
通過我們上面的分析，它可能向上更新幾次就停止了，但是不排除有可能一直更新直到根結(jié)點
比如這種情況
所以整個循環(huán)的結(jié)束條件是這樣的

根結(jié)點沒有父親（根結(jié)點的parent為空），所以如果parent不為空，就有可能要一直向上更新。
然后循環(huán)體里面的內(nèi)容就按照我們上面的分析寫就行了

//更新平衡因子
while (parent)
{
	//更新parent的平衡因子
	if (cur == parent->_right)
	{
		parent->_bf++;
	}
	else
	{
		parent->_bf--;
	}
	//判斷是否需要繼續(xù)向上更新，需要就往上走等待下次循環(huán)更新，
	//如果不平衡了就進行處理，不需要處理不需要調(diào)整就break
	if (parent->_bf == 1 || parent->_bf == -1)
	{
		parent = parent->_parent;
		cur = cur->_parent;
	}
	else if(parent->_bf == 2 || parent->_bf == -2)
	{
		//進行旋轉(zhuǎn)調(diào)整
		//...
		break;
	}
	else if (parent->_bf == 0)
	{
		break;
	}
	else
	{
		//非正常情況
		assert(false);
	}
}

那接下來我們就來重點講一下對于不平衡的情況如何進行調(diào)整，即AVL樹的旋轉(zhuǎn)

5. AVL樹的旋轉(zhuǎn)

如果在一棵原本是平衡的AVL樹中插入一個新節(jié)點，可能造成不平衡，此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。

根據(jù)節(jié)點插入位置的不同，AVL樹的旋轉(zhuǎn)分為四種，接下來我們將一 一進行學(xué)習(xí)

5.1 新節(jié)點插入較高右子樹的右側(cè)—右右：左單旋

我們先來學(xué)習(xí)第一種旋轉(zhuǎn)——左單旋。

什么情況要進行左單旋

那什么樣的情況要進行左單旋呢？

就是上圖的這種情況。

大家對照著圖，我們來分析一下：

首先大家可能有疑問

圖里面的a、b、c是啥?。?br> ??，我們這里給的是一個抽象圖，a、b、c分別代表三棵高度為h的AVL子樹，這里的h可以為任何整數(shù)值（所以h取不同的值，這里具體的情況是有很多種的，不過不用擔(dān)心，針對這一類情況，我們的處理是統(tǒng)一的）。

那我們看這個圖

原本30這棵AVL樹（當(dāng)然實際中他也可能是一棵子樹，子樹的話上面就還有結(jié)點）處在平衡的狀態(tài)，右子樹比左子樹高1，然后現(xiàn)在我們在它的右子樹的右側(cè)c這里插入新結(jié)點，然后它的高度變成h+1。
注意我們討論的情況是插入之后它的高度+1，如果高度不變的話也不需要調(diào)整了

還有就是如果插入之后，c的高度雖然+1了，但是c這棵子樹直接變的不平衡了

這兩種情況不是我們現(xiàn)在要討論的。
我們現(xiàn)在討論的情況就是插入之后c的高度變成h+1了，并且平衡因子需要向上更新影響到30，導(dǎo)致30這棵樹不平衡

比如這樣的

那針對這種情況我們要進行左單旋處理（不論這里的高度h對應(yīng)是幾，這種情況都是左單旋處理）。
大家可以自己多畫幾個h為不同高度的圖。

如何進行左單旋

那左單旋處理是怎么做呢？

現(xiàn)在我們插入之后是這樣的

現(xiàn)在30這個結(jié)點的平衡因子是不在正常范圍內(nèi)的，這棵樹是不平衡的，右邊高，所以要對30這棵樹進行左單旋，怎么左單旋呢？
??，其實兩步就搞定了

相當(dāng)于把30往左邊向下旋轉(zhuǎn)，所以叫左單旋。
大家看，進行了左單旋之后，這棵樹是不是就重新變成AVL樹，達到平衡狀態(tài)了啊，樹的高度也降下去了。
為什么這樣旋轉(zhuǎn)，大家看60的左子樹比60小，比30大，所以可以做30的右子樹，然后30整棵樹都比60小，所以可以做60的左子樹。
當(dāng)然降高度是一方面，在使它變平衡的同時是不是也要保持它依舊是一顆搜索二叉樹啊，因為AVL樹就是平衡的搜索二叉樹嘛（大家可以看我們旋轉(zhuǎn)過程選擇的孩子都是滿足搜索樹的大小關(guān)系的）。
大家可以把h換成實際的數(shù)字，畫一個圖，然后進行一下插入、左單旋，再理解一下這個過程。

這是抽象圖的一個完整過程。

左單旋代碼實現(xiàn)

那然后我們來寫一下左單旋的代碼：

旋轉(zhuǎn)的時候傳要旋轉(zhuǎn)的子樹的根結(jié)點即可。
然后我們可以把需要操作到的幾個結(jié)點獲取一下


然后，按照上面講的思路進行旋轉(zhuǎn)就行了

ps：解釋一下為什么起名subR，sub是subtree （子樹）的縮寫
對照著圖，大家看一下這樣寫對不對。

??，這樣寫是有問題的：

第一個問題——沒有處理結(jié)點的_parent指針
我們上面實現(xiàn)的時候給結(jié)點增加了一個指向其父親的指針_parent，方便我們更新平衡因子的時候往上走，但是代價就是需要我們?nèi)ゾS護這個指針。
所以，旋轉(zhuǎn)之后要更新_parent指針

然后呢，還不行
第二個問題——subRL 可能為空
為什么？

看圖，如果h等于0的話subRL是不是就是空啊。

所以加個判斷。
接著，第三個問題——parent上面可能還有結(jié)點（即旋轉(zhuǎn)的是子樹）
我們上面分析的時候說了，我們這里旋轉(zhuǎn)的可能是一整棵樹，也可能是一棵樹中的子樹。
所以如果是子樹的話，上面還有結(jié)點

這樣我們旋轉(zhuǎn)之后上面結(jié)點的指向就不對了
所以我們也要處理一下，判斷它是不是子樹，然后進行不同的處理


最后，還有一個問題——旋轉(zhuǎn)之后要更新一下平衡因子

至此，我們的左單旋才算完成

//左單旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if(subRL)
		subRL->_parent = parent;

	//先保存一下parent->_parent，因為下面會改它
	Node* pparent = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR;

	//若pparent為空則證明旋轉(zhuǎn)的是一整棵樹，因為根結(jié)點的_parent為空
	if (pparent == nullptr)
	{
		//subR是新的根
		_root = subR;
		_root->_parent == nullptr;
	}
	//若pparent不為空，則證明旋轉(zhuǎn)的是子樹，parent上面還有結(jié)點
	else
	{
		//讓pparent指向子樹旋轉(zhuǎn)之后新的根
		if (pparent->_left == parent)
		{
			pparent->_left = subR;
		}
		else
		{
			pparent->_right = subR;
		}
		//同時也讓新的根指向pparent
		subR->_parent = pparent;
	}
	//旋轉(zhuǎn)完更新平衡因子
	parent->_bf = subR->_bf = 0;
}

什么時候調(diào)用左單旋

那我們代碼寫好了，什么時候調(diào)用呢？

我們觀察圖會發(fā)現(xiàn)

如果parent的平衡因子是2，subR（對應(yīng)我們在更新平衡因子的那個循環(huán)里就是cur）的平衡因子是1，此時要進行的就是左單旋

if (parent->_bf == 2 && cur->_bf == 1)
{
	RotateL(parent);
}

5.2 新節(jié)點插入較高左子樹的左側(cè)—左左：右單旋

接著我們看第二種旋轉(zhuǎn)——右單旋

什么情況要進行右單旋

那右單旋又適用于哪些情況呢呢？

同樣的我們這里討論的情況是插入之后a的高度要發(fā)生變化，且會影響到當(dāng)前這棵樹（當(dāng)然它可以是一棵子樹）根結(jié)點的平衡因子，導(dǎo)致整棵樹不平衡，這時我們可以用右單旋解決。

如何進行右單旋

那右單旋又該如何操作呢？

也是兩步

相當(dāng)于把30往右邊向上旋轉(zhuǎn)，所以叫右單旋。
30的右子樹比30大，比60小，所以可以做60的左子樹，然后60整棵樹都比30大，所以可以做30的右子樹。
這樣這棵樹就重新變平衡了，30成為了新的根結(jié)點。

右單旋代碼實現(xiàn)

那我們來寫一下右單旋的代碼

那寫了上面左單旋的代碼，再寫右單旋的話應(yīng)該就比較輕松了，需要注意的點還是那幾個

對照著圖，我們來寫一下，這里我就不做過多解釋了

//右單旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = parent->_right;

	//旋轉(zhuǎn)并更新_parent指針
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	
	//先保存一下parent->_parent，因為下面會改它
	Node* pparent = parent->_parent;

	//旋轉(zhuǎn)并更新_parent指針
	subL->_right = parent;
	parent->_parent = subL;

	//若parent等于_root則證明旋轉(zhuǎn)的是一整棵樹（這也是一種判斷方法）
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		//讓pparent指向子樹旋轉(zhuǎn)之后新的根
		if (parent == pparent->_left)
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
		//同時也讓新的根指向pparent
		subL->_parent = pparent;
	}
	subL->_bf = parent->_bf = 0;
}

什么時候調(diào)用右單旋

那右單旋什么時候調(diào)用呢？

來看圖

??，我們看到如果parent的平衡因子為-2，subL（cur）的平衡因子為-1，要調(diào)用的就是右單旋

5.3 新節(jié)點插入較高左子樹的右側(cè)—左右：先左單旋再右單旋（左右雙旋）

再來看第三種旋轉(zhuǎn)——左右雙旋

什么情況進行左右雙旋

看這張圖

這里給的是在b插入，在c插入當(dāng)然也是左右雙旋，但是插入之后平衡因子的更新會有一些不同，后面會提到。
這還是抽象圖，我們來畫幾個具象圖看一下

如何進行左右雙旋

首先要知道對于這種情況，我們?nèi)绻贿M行左或者右的單旋是解決不了問題的

大家看這種情況插入之后根結(jié)點90是-2，-2就表明左邊高嘛。
那左邊高的話如果我們進行右旋可以變平衡嗎？
那對它右旋之后是這樣的

這是不是還不平衡啊，現(xiàn)在變成右邊高了

那要進行雙旋，怎么做呢？

上面已經(jīng)說了針對這種情況要進行的是左右雙旋，那顧名思義就是先進行一個左單旋（對根的左子樹），再進行一個右單旋（對根）

然后就平衡了，其實我們能發(fā)現(xiàn)它就是把60推上去做根，然后60的左右子樹分給30的右子樹和90的左子樹。
為什么不能直接右單旋，因為大家看他原來不是一個單純的左邊高
插入之后類似這樣一個形狀

首先第一步的左單旋相當(dāng)于把它變成單純的左邊高

然后在進行一次右單旋，就平衡了。

左右雙旋代碼實現(xiàn)

那左右雙旋的代碼怎么寫？是不是直接復(fù)用左右單旋的代碼就行了

那就先調(diào)用左旋，再調(diào)用右旋就行了

但是左右雙旋麻煩的地方其實在于平衡因子的調(diào)節(jié)。
我們上面提到插入在b和c它們最后平衡因子更新不同

能看到旋轉(zhuǎn)之后它們的平衡因子更新是不一樣的。
那如何判斷在b插入還是在c插入呢？
??，大家看圖，不同位置的插入，插入之后60這個結(jié)點的平衡因子是不同的。
那除此之外，h為0的時候，其實平衡因子的更新又有所不同
如果h==0的話

它旋轉(zhuǎn)是這樣的

所以，平衡因子的更新這里我們要分三種情況
我們還是記錄一下這三個結(jié)點，方便操作

然后我們補充一下平衡因子更新的代碼，不同情況更新不同的值

//左右雙旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	//更新平衡因子
	if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

什么時候調(diào)用左右雙旋

看圖

else if (parent->_bf == -2 && cur->_bf == 1)
{
	RotateLR(parent);
}

5.4 新節(jié)點插入較高右子樹的左側(cè)—右左：先右單旋再左單旋（右左雙旋）

什么情況進行右左雙旋

那我們來看一下右左雙旋適用于哪些情況？

當(dāng)然插入到b這棵樹上也是可以的。
同樣的高度h不同，就會產(chǎn)生很多不同的情況，但是沒關(guān)系，這要是這種情況，我們就可以統(tǒng)一處理

如何進行右左雙旋

那就還是兩次單旋嘛：

這里就是首先進行一次右單旋（對根的右子樹），然后再進行一次左單旋（對根）

最后就平衡了。
其實根上面學(xué)的左右雙旋是同樣的道理：
這樣的情況只旋一次是不能達到平衡的，所以第一次其實是把它變成純粹的右邊高，然后再進行一次左單旋就平衡了。
那最終的結(jié)果就相當(dāng)于把60推上去做根，然后60的左右子樹分別分給30的右子樹和90的左子樹。

右左雙旋代碼實現(xiàn)

那右左單旋的話我們可以是可以直接復(fù)用左單旋和右單旋的，但是，同樣的道理，我們還是需要對雙旋之后的平衡因子分不同的情況進行更新處理：

與左右雙旋一樣，還是三種情況，不同情況平衡因子的更新不同，通過插入之后subRL的平衡因子區(qū)分三種情況

1. 就是我們上面分析的，在c插入
   
2. 在b插入
   
3. h等于0情況下的插入
   

那對應(yīng)的代碼就是

//右左雙旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	//更新平衡因子
	if (bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

什么時候調(diào)用右左雙旋

很容易看出來：

當(dāng)根結(jié)點的平衡因子為2，cur為-1的時候調(diào)用的是右左雙旋

5.5 總結(jié)

假如以pParent為根的子樹不平衡，即pParent的平衡因子為2或者-2，分以下情況考慮

1. pParent的平衡因子為2，說明pParent的右子樹高，設(shè)pParent的右子樹的根為SubR
   當(dāng)SubR的平衡因子為1時，執(zhí)行左單旋
   當(dāng)SubR的平衡因子為-1時，執(zhí)行右左雙旋
2. pParent的平衡因子為-2，說明pParent的左子樹高，設(shè)pParent的左子樹的根為SubL
   當(dāng)SubL的平衡因子為-1是，執(zhí)行右單旋
   當(dāng)SubL的平衡因子為1時，執(zhí)行左右雙旋
   
   旋轉(zhuǎn)完成后，原pParent為根的子樹個高度降低，已經(jīng)平衡，不需要再向上更新。

6. AVL樹的測試

AVL樹是在二叉搜索樹的基礎(chǔ)上加入了平衡性的限制，因此要測試AVL樹，可以分兩步：

6.1 驗證其為二叉搜索樹

我們插入一些數(shù)據(jù)，如果中序遍歷可得到一個有序的序列，就說明為二叉搜索樹

我們定義一棵AVL樹，然后插入一些數(shù)據(jù)中序遍歷一下。
寫一個中序遍歷


然后我們運行一下

??，沒什么問題，是有序的。

6.2 驗證其為平衡樹

那如何驗證它是否平衡呢？

我們可以去計算高度，如果每一個結(jié)點左右子樹的高度差的絕對值不超過1，就證明它是平衡的。
為什么不用平衡因子判斷呢？
首先，不是所有的AVL樹的實現(xiàn)里面都有平衡因子的，只是我們這里采用了平衡因子，這是AVL樹的一種實現(xiàn)方法而已。
其次，我們不敢保證我們自己寫到代碼計算出來的平衡因子一定是正確的。

所以，我們來寫一個通過高度差來判斷是否平衡的函數(shù)

這個比較簡單，我就不過多解釋了

然后我們測試一下

先判斷一下剛才的那棵樹
??，是平衡的。
我們再來看一個比較特殊的場景
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

這個是一個右左雙旋的場景

沒什么問題。
如果我們不調(diào)整的話

那它應(yīng)該就是不平衡了

沒問題。

然后呢，我們還可以做一件事情

6.3 判斷平衡因子的更新是否正確

怎么判斷：

很簡單，計算一下高度差，看他和平衡因子相不相等就行了

再來測試一下

沒有問題，還是平衡。

6.4 大量隨機數(shù)構(gòu)建AVL樹進行測試

上面的測試數(shù)據(jù)量比較小，且不夠隨機

下面我們生成一些隨機數(shù)來構(gòu)建AVL樹，測試一下

10萬個隨機數(shù)，先來試一下

沒有問題，10萬個隨機數(shù)構(gòu)建也沒有出現(xiàn)錯誤的情況，依然是平衡的。
來，100萬個隨機數(shù)

依舊沒問題。

7. 查找

然后AVL樹的查找那就跟搜索二叉樹是一樣的，我們這里就不講了，大家可以看之前搜索二叉樹的文章。

8. AVL樹的刪除(了解)

AVL樹的刪除操作我們不做重點講解，大家了解一下即可，因為這個不是特別重要，面試一般也不會考到。

AVL樹的刪除操作主要分為以下幾個步驟：

1. 執(zhí)行二叉搜索樹的刪除操作
2. 更新平衡因子：如果刪除之后影響到了上面結(jié)點的平衡因子，就要從被刪除節(jié)點的父節(jié)點向上更新受影響的平衡因子。
3. 檢查所有的平衡因子，如果存在不正常的平衡因子，則要對相應(yīng)的樹進行調(diào)整，使它恢復(fù)平衡。
4. 重復(fù)步驟2和步驟3，直至到達根節(jié)點或不需要進一步調(diào)整為止。

9. AVL樹的性能

AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個節(jié)點的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間復(fù)雜度，即$lo{g}_2(N)$。
但是如果要對AVL樹做一些結(jié)構(gòu)修改的操作，性能非常低下。
比如：插入時要維護其絕對平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。
因此：如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個數(shù)為靜態(tài)的(即不會改變)，可以考慮AVL樹，但一個結(jié)構(gòu)經(jīng)常修改，就不太適合。

10. 源碼

10.1 AVLTree.h

#pragma once
#include <assert.h>

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K,V>* _right;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;//balance factor

	AVLTreeNode(const pair<K,V>& kv)
		:_right(nullptr)
		,_left(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

template <class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			//cout << "root:"<<_root->_kv.first << endl;
			return true;
		}
		
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//鏈接父親指針
		cur->_parent = parent;

		//更新平衡因子
		while (parent)
		{
			//更新parent的平衡因子
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
			//判斷是否需要繼續(xù)向上更新，需要就往上走等待下次循環(huán)更新，
			//如果不平衡了就進行處理，不需要處理不需要調(diào)整就break
			if (parent->_bf == 1 || parent->_bf == -1)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if(parent->_bf == 2 || parent->_bf == -2)
			{
				//根據(jù)實際情況進行相應(yīng)的旋轉(zhuǎn)調(diào)整
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				//旋轉(zhuǎn)完結(jié)束，就不需要再往上更新了
				break;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else
			{
				//非正常情況
				assert(false);
			}
		}
		//cout << "root:" << _root->_kv.first << endl;
		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	int TreeHeight()
	{
		return _TreeHeight(_root);
	}
private:
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int rightH = _TreeHeight(root->_right);
		int leftH = _TreeHeight(root->_left);

		if (rightH - leftH != root->_bf)
		{
			cout << root->_kv.first << "結(jié)點平衡因子更新錯誤" << endl;
			return false;
		}

		return abs(rightH - leftH) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
	int _TreeHeight(Node* root)
	{
		if (root == nullptr)
			return 0;
		int RightH = _TreeHeight(root->_left);
		int leftH = _TreeHeight(root->_right);
		return RightH > leftH ? RightH + 1 : leftH + 1;
	}
	//左單旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//旋轉(zhuǎn)并更新_parent指針
		parent->_right = subRL;
		if(subRL)
			subRL->_parent = parent;

		//先保存一下parent->_parent，因為下面會改它
		Node* pparent = parent->_parent;

		//旋轉(zhuǎn)并更新_parent指針
		subR->_left = parent;
		parent->_parent = subR;

		//若pparent為空則證明旋轉(zhuǎn)的是一整棵樹，因為根結(jié)點的_parent為空
		if (pparent == nullptr)
		{
			//subR是新的根
			_root = subR;
			_root->_parent = nullptr;
		}
		//若pparent不為空，則證明旋轉(zhuǎn)的是子樹，parent上面還有結(jié)點
		else
		{
			//讓pparent指向子樹旋轉(zhuǎn)之后新的根
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
			//同時也讓新的根指向pparent
			subR->_parent = pparent;
		}
		//旋轉(zhuǎn)完更新平衡因子
		parent->_bf = subR->_bf = 0;
	}

	//右單旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		//旋轉(zhuǎn)并更新_parent指針
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		
		//先保存一下parent->_parent，因為下面會改它
		Node* pparent = parent->_parent;

		//旋轉(zhuǎn)并更新_parent指針
		subL->_right = parent;
		parent->_parent = subL;

		//若parent等于_root則證明旋轉(zhuǎn)的是一整棵樹（這也是一種判斷方法）
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			//讓pparent指向子樹旋轉(zhuǎn)之后新的根
			if (parent == pparent->_left)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
			//同時也讓新的根指向pparent
			subL->_parent = pparent;
		}
		subL->_bf = parent->_bf = 0;
	}
	//左右雙旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		//更新平衡因子
		if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//右左雙旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		//更新平衡因子
		if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

10.2 Test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "AVLTree.h"
#include <time.h>


void AVLTest1()
{
	//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	//int arr[] = { 1,2,3,4,5,6,7,8,9,1 };
	int arr[] = { 95,47,32,29,7,7,2,50,74,30 };

	AVLTree<int, int> t1;
	for (auto e : arr)
	{
		//cout << e << endl;
		t1.Insert(make_pair(e, e));
		t1.InOrder();
		if (!t1.IsBalance())
		{
			break;
		}
	}
	//t1.InOrder();
	/*if (t1.IsBalance())
	{
		cout << "平衡" << endl;
	}
	else
	{
		cout << "不平衡" << endl;
	}*/
}

void AVLTest2()
{
	srand(time(nullptr));
	const int N = 1000000;
	AVLTree<int, int> t;
	for (int i = 0; i < N; ++i)
	{
		int x = rand();
		t.Insert(make_pair(x, x));
	}
	if (t.IsBalance())
	{
		cout << "平衡" << endl;
	}
	else
	{
		cout << "不平衡" << endl;
	}
}

int main()
{
	AVLTest2();
	return 0;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-654856.html

到了這里，關(guān)于【高階數(shù)據(jù)結(jié)構(gòu)】AVL樹詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！