C/C++數(shù)據(jù)結(jié)構(gòu)（十一）——平衡二叉樹(shù)（AVL樹(shù)）-創(chuàng)新互聯(lián)

文章目錄

• 1. AVL樹(shù)的概念
• 2. AVL樹(shù)的結(jié)點(diǎn)
• 3. AVL樹(shù)的插入
• • 🍑 更新平衡因子
  • 🍑 插入函數(shù)的實(shí)現(xiàn)
• 4. AVL樹(shù)的旋轉(zhuǎn)
• • 🍑 左單旋
  • 🍑 右單旋
  • 🍑 左右雙旋
  • 🍑 右左雙旋
  • 🍑 總結(jié)
• 6. AVL樹(shù)的刪除
• • 🍑 算法思想
  • 🍑 示例一
  • 🍑 示例二
  • 🍑 代碼實(shí)現(xiàn)
• 7. AVL樹(shù)的遍歷
• 8. AVL樹(shù)的查找
• 9. AVL樹(shù)的高度
• 10. AVL樹(shù)的驗(yàn)證
• • 🍑 數(shù)據(jù)測(cè)試
• 11. AVL樹(shù)優(yōu)缺點(diǎn)分析

成都創(chuàng)新互聯(lián)專(zhuān)注于網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站制作、網(wǎng)站開(kāi)發(fā)。公司秉持“客戶(hù)至上,用心服務(wù)”的宗旨,從客戶(hù)的利益和觀點(diǎn)出發(fā),讓客戶(hù)在網(wǎng)絡(luò)營(yíng)銷(xiāo)中找到自己的駐足之地。尊重和關(guān)懷每一位客戶(hù)，用嚴(yán)謹(jǐn)?shù)膽B(tài)度對(duì)待客戶(hù)，用專(zhuān)業(yè)的服務(wù)創(chuàng)造價(jià)值，成為客戶(hù)值得信賴(lài)的朋友，為客戶(hù)解除后顧之憂。

---

1. AVL樹(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)度。

平衡二叉樹(shù)（Balanced Binary Tree 或 Height-Balanced Tree）又稱(chēng)為 AVL 樹(shù)，其實(shí)就是一顆 平衡的二叉排序樹(shù) ，解決了二叉查找樹(shù)的不平衡問(wèn)題，即斜樹(shù)。

AVL樹(shù)或者是一顆空樹(shù)，或者是具有下列性質(zhì)的二叉搜索樹(shù)：

• 它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)
• 左右子樹(shù)高度之差（簡(jiǎn)稱(chēng)平衡因子）的絕對(duì)值不超過(guò) 1（即：-1，0，1）

舉個(gè)例子，下圖就是一顆典型的 AVL 樹(shù)，每個(gè)節(jié)點(diǎn)旁邊都標(biāo)注了平衡因子：

上面是一顆典型的平衡二叉樹(shù)，首先它是一顆二叉排序樹(shù)，其次每一個(gè)結(jié)點(diǎn)的平衡因子都是 -1，0，1 三個(gè)數(shù)當(dāng)中的一個(gè)。

紅色的數(shù)字為結(jié)點(diǎn)的平衡因子，對(duì)于任意一個(gè)葉子結(jié)點(diǎn)而言，其左右孩子都為空，左子樹(shù)的深度為 0 ，右子樹(shù)的深度為 0 ，所以 AVL樹(shù)當(dāng)中的葉子結(jié)點(diǎn)的平衡因子都是 0 ；

其他結(jié)點(diǎn)的平衡因子同樣通過(guò) 右子樹(shù)深度減去左子樹(shù)深度 可以求得，比如結(jié)點(diǎn) 3 的 左子樹(shù)深度為 2，右子樹(shù)深度為1 ，則平衡因子為 1 ? 2 = ? 1 1 - 2 = -1 1?2=?1。

如果一棵二叉搜索樹(shù)是高度平衡的，它就是 AVL 樹(shù)。如果它有 n 個(gè)結(jié)點(diǎn)，其高度可保持在 O ( l o g n ) O(logn) O(logn)，搜索時(shí)間復(fù)雜度 O ( l o g n O(log n O(logn)。

再來(lái)看看不平衡的情況，如下面這顆樹(shù)：

上圖中就是不平衡的二叉排序樹(shù)，非 AVL樹(shù) 。結(jié)點(diǎn) 5 的平衡因子為 -2，該平衡因子是結(jié)點(diǎn) 5 右子樹(shù)深度 2 減去左子樹(shù)深度 4 所得；

我們要學(xué)習(xí)的就是將這種不平衡的二叉搜索樹(shù)轉(zhuǎn)化為 AVL樹(shù)。

2. AVL樹(shù)的結(jié)點(diǎn)

我們直接按照 KV 模型來(lái)構(gòu)造 AVL 樹(shù)，需要把結(jié)點(diǎn)定義為 三叉鏈結(jié)構(gòu)，并在每個(gè)結(jié)點(diǎn)當(dāng)中引入平衡因子（右子樹(shù)高度-左子樹(shù)高度）。

對(duì)于結(jié)點(diǎn)的構(gòu)造函數(shù)，由于新構(gòu)造結(jié)點(diǎn)的左右子樹(shù)均為空樹(shù)，所以只需要將新構(gòu)造結(jié)點(diǎn)的平衡因子初始設(shè)置為 0 即可。

代碼示例

templatestruct AVLTreeNode
{// 存儲(chǔ)的鍵值對(duì)
	pair_kv;

	// 三叉鏈
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	// 平衡因子(balance factor)
	int _bf; // 右子樹(shù)高度 - 左子樹(shù)高度

	// 構(gòu)造函數(shù)
	AVLTreeNode(const pair& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

3. AVL樹(shù)的插入

對(duì)平衡二叉樹(shù)的插入操作而言，其本質(zhì)上比二叉搜索樹(shù)的插入操作多了一個(gè)平衡操作，解決了二叉搜索樹(shù)插入操作可能出現(xiàn)的斜樹(shù)，不平衡問(wèn)題。

那么 AVL 樹(shù)的插入過(guò)程可以分為兩步：

• 按照二叉搜索樹(shù)的方式，找到待插入的位置，然后將新結(jié)點(diǎn)插入到該位置。
• 調(diào)整節(jié)點(diǎn)的平衡因子，如果出現(xiàn)不平衡，則需要進(jìn)行旋轉(zhuǎn)。

🍑 更新平衡因子

當(dāng) AVL 樹(shù)插入一個(gè)新結(jié)點(diǎn)以后，需要更新插入結(jié)點(diǎn)的祖先的平衡因子，因?yàn)樾陆Y(jié)點(diǎn)（也就是葉子結(jié)點(diǎn)）的平衡因子為 0，但是它影響的是它的父親，它父親的父親…，所以要更新到祖先結(jié)點(diǎn)。

所以我們要從新增結(jié)點(diǎn)開(kāi)始，往上沿著祖先路徑更新，那么更新的規(guī)則如下：

• 如果新增結(jié)點(diǎn)插入在 parent 的右邊，只需要給 parent 的平衡因子+1即可
• 如果新增結(jié)點(diǎn)插入在 parent 的左邊，只需要給 parent 的平衡因子-1即可

為什么呢？因?yàn)槠胶庖蜃拥挠?jì)算方法是：右子樹(shù)高度 - 左子樹(shù)高度，如果插入在右邊，那么最后的結(jié)果肯定是要++，反之，則--。

當(dāng) parent 的平衡因子更新完以后，可能出現(xiàn)三種情況：0，正負(fù) 1，正負(fù) 2。

（1）parent 的平衡因子為 0

如果 parent 的平衡因子為 0，說(shuō)明插入之前 parent 的平衡因子為正負(fù) 1，插入后被調(diào)整成 0，此時(shí)滿足 AVL 樹(shù)的性質(zhì)，則插入成功。

如下圖所示，插入后使得 parent 左右子樹(shù)的高度相等了，此操作并沒(méi)有改變以 parent 為根結(jié)點(diǎn)的子樹(shù)的高度，從而不會(huì)影響 parent 的父結(jié)點(diǎn)的平衡因子，因此無(wú)需繼續(xù)往上更新平衡因子。

（2）如果 parent 的平衡因子為正負(fù) 1

如果 parent 的平衡因子為正負(fù) 1，說(shuō)明插入前 parent 的平衡因子一定為 0，插入后被更新成正負(fù) 1。

如下圖所示，當(dāng)新增一個(gè)結(jié)點(diǎn)以后，parent 的平衡因子從 0 變成了 1，說(shuō)明新結(jié)點(diǎn)的插入使得 parent 的右子樹(shù)增高了，即改變了以 parent 為根結(jié)點(diǎn)的子樹(shù)的高度，從而會(huì)影響 parent 的父結(jié)點(diǎn)的平衡因子，因此需要繼續(xù)往上更新平衡因子。

如下圖所示，當(dāng)新增一個(gè)結(jié)點(diǎn)以后，parent 的平衡因子從 0 變成了 -1，說(shuō)明新結(jié)點(diǎn)的插入使得 parent 的左子樹(shù)增高了，即改變了以 parent 為根結(jié)點(diǎn)的子樹(shù)的高度，從而會(huì)影響 parent 的父結(jié)點(diǎn)的平衡因子，因此需要繼續(xù)往上更新平衡因子。

進(jìn)而引出了下面的第 3 種情況。

（3）如果 parent 的平衡因子為正負(fù) 2

如果 parent 的平衡因子為 -2，此時(shí) parent 結(jié)點(diǎn)的左右子樹(shù)高度之差的絕對(duì)值已經(jīng)超過(guò) 1 了，則 parent 的平衡因子違反平衡樹(shù)的性質(zhì)，那么就停止更新，需要對(duì)其進(jìn)行旋轉(zhuǎn)處。

如果 parent 的平衡因子為 2，此時(shí) parent 結(jié)點(diǎn)的左右子樹(shù)高度之差的絕對(duì)值已經(jīng)超過(guò) 1 了，則 parent 的平衡因子違反平衡樹(shù)的性質(zhì)，那么就停止更新，需要對(duì)其進(jìn)行旋轉(zhuǎn)處。

可以看到，當(dāng) parent 的平衡因子為正負(fù) 2 時(shí)，cur 的平衡因子必定是正負(fù) 1 而不會(huì)是 0。

🍑 插入函數(shù)的實(shí)現(xiàn)

上面我們分析了，如果在更新平衡因子的過(guò)程當(dāng)中，出現(xiàn)了平衡因子為正負(fù) 2 的結(jié)點(diǎn)，此時(shí)需要對(duì) 以該結(jié)點(diǎn)為根結(jié)點(diǎn)的樹(shù) 進(jìn)行旋轉(zhuǎn)處理（待會(huì)兒再講旋轉(zhuǎn)）。

我們定義一個(gè)cur用來(lái)表示 新增結(jié)點(diǎn)，定義一個(gè)parent用來(lái)表示 新增結(jié)點(diǎn)的父親結(jié)點(diǎn)。

那么我們更新平衡因子時(shí)，第一個(gè)要更新的就是 parent 結(jié)點(diǎn)的平衡因子，更新完 parent 結(jié)點(diǎn)的平衡因子后，若是需要繼續(xù)往上進(jìn)行平衡因子的更新，那么要執(zhí)行以下操作：

if (parent->_bf == 1 || parent->_bf == -1)
{cur = cur->_parent; // cur指向了它的父親
	parent = parent->_parent; // 它的父親指向了它的祖先
}

可以看到，我們之所以將 AVL 樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)設(shè)置為三叉鏈結(jié)構(gòu)，是因?yàn)槲覀兛梢院芊奖愕耐ㄟ^(guò)父指針找到其父結(jié)點(diǎn)，進(jìn)而對(duì)其平衡因子進(jìn)行更新。

而當(dāng) parent 的平衡因子為正負(fù) 2 時(shí)，我們需要對(duì)其進(jìn)行旋轉(zhuǎn)操作，當(dāng)旋轉(zhuǎn)完成以后，就無(wú)需繼續(xù)往上更新平衡因子了，即樹(shù)的高度沒(méi)有發(fā)生變化，也就不會(huì)影響其父結(jié)點(diǎn)的平衡因子了。

if (parent->_bf == 2 || parent->_bf == -2)
{// 旋轉(zhuǎn)的四種處理方式
	// 1.左單旋
	// 2.右單旋
	// 3.左右雙旋
	// 4.右左雙旋

	// 當(dāng)旋轉(zhuǎn)完成以后，直接跳出
	break;
}

代碼示例

public:
	// 插入函數(shù)
	bool Insert(const pair& kv)
	{// 如果AVL樹(shù)是空樹(shù)，把插入節(jié)點(diǎn)直接作為根節(jié)點(diǎn)
		if (_root == nullptr)
		{	_root = new Node(kv);
			_root->_bf = 0;
			return true;
		}

		// 1.按照二叉搜索樹(shù)的規(guī)則插入
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{	if (cur->_kv.first< kv.first) // 待插入節(jié)點(diǎn)的key值大于當(dāng)前節(jié)點(diǎn)的key值
			{		// 往右子樹(shù)走
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first >kv.first) // 待插入節(jié)點(diǎn)的key值小于當(dāng)前節(jié)點(diǎn)的key值
			{		// 往左子樹(shù)走
				parent = cur; 
				cur = cur->_left;
			}
			else // 待插入節(jié)點(diǎn)的key值等于當(dāng)前節(jié)點(diǎn)的key值
			{		return false; // 插入失敗，返回false
			}
		}

		// 2.當(dāng)循環(huán)結(jié)束，說(shuō)明cur找到了空的位置，那么就插入
		cur = new Node(kv); // 構(gòu)造一個(gè)新節(jié)點(diǎn)
		if (parent->_kv.first< kv.first) // 如果新節(jié)點(diǎn)的key值大于當(dāng)前parent節(jié)點(diǎn)的key值
		{	// 就把新節(jié)點(diǎn)鏈接到parent的右邊
			parent->_right = cur;
		}
		else // 如果新節(jié)點(diǎn)的key值小于當(dāng)前parent節(jié)點(diǎn)的key值
		{	// 就把新節(jié)點(diǎn)鏈接到parent的左邊
			parent->_left = cur;
		}
		cur->_parent = parent; // 別忘了把新節(jié)點(diǎn)里面的_parent指向parent(因?yàn)槲覀兌x的是一個(gè)三叉鏈)

		// 3.更新平衡因子,如果出現(xiàn)不平衡,則需要進(jìn)行旋轉(zhuǎn)
		while (parent) // 最遠(yuǎn)要更新到根節(jié)點(diǎn)去
		{	if (cur == parent->_right) // 如果cur插在parent的右邊，說(shuō)明parent的右子樹(shù)增高
			{		parent->_bf++; // 那么parent的平衡因子要++
			}
			else // 如果cur插在parent的左邊，說(shuō)明parent的左子樹(shù)增高
			{		parent->_bf--; // 那么parent的平衡因子要--
			}

			// 判斷是否更新結(jié)束，或者是否需要進(jìn)行旋轉(zhuǎn)
			if (parent->_bf == 0) // 如果parent的bf等于0，說(shuō)明左右子樹(shù)高度一致，就更新結(jié)束(原因是新插入的節(jié)點(diǎn)把parent左右子樹(shù)中矮的那一邊給填補(bǔ)了）
			{		// 高度不變,更新結(jié)束
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) // 繼續(xù)往上更新平衡因子(插入節(jié)點(diǎn)導(dǎo)致某一邊變高了，說(shuō)明parent所在的子樹(shù)高度改變了)
			{		// 子樹(shù)的高度變了，就要繼續(xù)往上更新祖先
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2) // 說(shuō)明插入節(jié)點(diǎn)導(dǎo)致本來(lái)高的一邊又變高了，子樹(shù)不平衡了，那么此時(shí)需要做旋轉(zhuǎn)處理
			{		// 旋轉(zhuǎn)的四種處理方式
				// 1.左單旋
				// 2.右單旋
				// 3.左右雙旋
				// 4.右左雙旋
				
				// 旋轉(zhuǎn)完成，跳出
				break;
			}
			else
			{		// 如果程序走到了這里，說(shuō)明在插入節(jié)點(diǎn)之前AVL樹(shù)就存在不平衡的子樹(shù)，也就是存在平衡因子 >= 2的節(jié)點(diǎn)
				// 所以這里加一個(gè)斷言進(jìn)行處理
				assert(false);
			}
		}
		// 插入成功，返回true
		return true;
	}

4. AVL樹(shù)的旋轉(zhuǎn)

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

根據(jù)節(jié)點(diǎn)插入位置的不同，AVL 樹(shù)的旋轉(zhuǎn)分為四種：

• 左單旋（LL）
• 右單旋（RR）
• 左右雙旋（LR）
• 右左雙旋（RL）

其實(shí)我們只要搞懂 LL 和 RR 就好了，因?yàn)?LR 和 RL 都是由它們演變而來(lái)的。

不管是什么旋轉(zhuǎn)，都必須滿足兩點(diǎn)原則：

• 保持搜索樹(shù)的規(guī)則
• 子樹(shù)變平衡

🍑 左單旋

下面是一個(gè) AVL 樹(shù)的抽象圖，長(zhǎng)方形條代表的是子樹(shù)，h表示 a，b，c 三顆子樹(shù)的高度。

• 結(jié)點(diǎn) 30 的右子樹(shù)深度為 h + 2，左子樹(shù)深度為 h + 1，所以平衡因子為 1。
• 結(jié)點(diǎn) 60 的右子樹(shù)深度為 h + 1，左子樹(shù)深度為 h + 1，所以平衡因子為 0。

現(xiàn)在我們?cè)?c 子樹(shù)的中插入一個(gè)新結(jié)點(diǎn)，那么此時(shí) c 子樹(shù)的高度就變成了 h + 1，同時(shí)結(jié)點(diǎn) 60 的平衡因子為 1，結(jié)點(diǎn) 30 的平衡因子為 2，此時(shí)右邊的高度大于左邊的高度，需要進(jìn)行左單旋。

左單旋的步驟如下：

• 先讓 subR 的左子樹(shù)（subRL）作為 parent 的右子樹(shù)。
• 然后讓 parent 作為 subR 的左子樹(shù)。
• 接下來(lái)讓 subR 作為整個(gè)子樹(shù)的根。
• 最后更新平衡因子。

左單旋圖如下所示：

經(jīng)過(guò)旋轉(zhuǎn)以后，它們的平衡因子就發(fā)生了變化：

• 結(jié)點(diǎn) 30 的右子樹(shù)深度為 h，左子樹(shù)深度為 h，所以平衡因子為 0。
• 結(jié)點(diǎn) 60 的右子樹(shù)深度為 h + 1 + 1，左子樹(shù)深度為 h + 1 + 1，所以平衡因子為 0。

這樣旋轉(zhuǎn)以后還滿足二叉搜索樹(shù)的性質(zhì)嗎？當(dāng)面滿足，原因如下：

• subR 的左子樹(shù)（subRL）當(dāng)中結(jié)點(diǎn)的值本身就比 parent 的值大，因此可以作為 parent 的右子樹(shù)。
• 而 parent 及其左子樹(shù)當(dāng)中結(jié)點(diǎn)的值本身就比 subR 的值小，因此可以作為 subR 的左子樹(shù)。

什么時(shí)候需要用到左旋操作呢？可以看到，當(dāng) parent 的平衡因子為 2，cur 的平衡因子為 1 時(shí)，需要進(jìn)行左單旋。并且經(jīng)過(guò)左單旋后，樹(shù)的高度沒(méi)有發(fā)生變化，所以左單旋后無(wú)需繼續(xù)往上更新平衡因子。

左單旋動(dòng)圖演示：

可以看到，我們?cè)?32 的右邊插入一個(gè)值為 35 的新節(jié)點(diǎn)，那么此時(shí) 32 的平衡因子從 0 變成了 1，29 的平衡因子從 1 變成了 2，出現(xiàn)了右邊高，左邊低的局面，所以需要進(jìn)行左單旋

代碼示例

private:
	// 左單旋（右邊高需要左單旋）
	void RotateL(Node* parent)
	{Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent; // 先保存parent的parent

		// 1.建立parent和subRL之間的關(guān)系
		parent->_right = subRL;
		if (subRL) // 如果subRL節(jié)點(diǎn)不為空，那么要更新它的parent
		{	subRL->_parent = parent;
		}

		// 2.建立subR和parent之間的關(guān)系
		subR->_left = parent;
		parent->_parent = subR;

		// 3.建立ppNode和subR之間的關(guān)系（分情況討論parent是整顆樹(shù)的根，還是局部子樹(shù)）
		if (parent == _root) // 當(dāng)parent是根節(jié)點(diǎn)時(shí)
		{	_root = subR; // subR就變成了新的根節(jié)點(diǎn)
			_root->_parent = nullptr; // 根節(jié)點(diǎn)的的parent為空
		}
		else // 當(dāng)parent是整個(gè)樹(shù)的局部子樹(shù)時(shí)
		{	if (parent == ppNode->_left) // 如果parent在ppNode的左邊
			{		ppNode->_left = subR; // 那么subR就是parent的左子樹(shù)
			}
			else // 如果parent在ppNode的右邊
			{		ppNode->_right = subR; // 那么subR就是parent的右子樹(shù)
			}
			subR->_parent = ppNode; // subR的parent還要指向ppNode
		}

		// 更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}

還有一點(diǎn)需要注意，如果在旋轉(zhuǎn)前 parent（30） 就是樹(shù)的根，那么此時(shí)只需要更新根結(jié)點(diǎn)為 subR（60）即可。

如果 parent（30） 只是整顆樹(shù)局部的一顆子樹(shù)，那么此時(shí)就需要看 30 是它父親的左子樹(shù)還是右子樹(shù)，然后再和 subR 鏈接起來(lái)，如下圖所示：

🍑 右單旋

下面是一個(gè) AVL 樹(shù)的抽象圖，長(zhǎng)方形條代表的是子樹(shù)，h表示 a，b，c 三顆子樹(shù)的高度。

• 結(jié)點(diǎn) 30 的右子樹(shù)深度為 h，左子樹(shù)深度為 h，所以平衡因子為 0。
• 結(jié)點(diǎn) 60 的右子樹(shù)深度為 h + 1，左子樹(shù)深度為 h + 1 + 1，所以平衡因子為 -1。

現(xiàn)在我們?cè)?a 子樹(shù)的中插入一個(gè)新結(jié)點(diǎn)，那么此時(shí) a 子樹(shù)的高度就變成了 h + 1，同時(shí)結(jié)點(diǎn) 60 的平衡因子為 -2，結(jié)點(diǎn) 30 的平衡因子為 -1，此時(shí)左邊的高度大于右邊的高度，需要進(jìn)行右單旋。

右單旋的步驟如下：

• 先讓 subL 的右子樹(shù)（subLR）作為 parent 的左子樹(shù)。
• 然后讓 parent 作為 subL 的右子樹(shù)。
• 接下來(lái)讓 subL 作為整個(gè)子樹(shù)的根。
• 最后更新平衡因子。

右單旋圖如下所示：

經(jīng)過(guò)旋轉(zhuǎn)以后，它們的平衡因子就發(fā)生了變化：

• 結(jié)點(diǎn) 30 的右子樹(shù)深度為 h + 1 + 1，左子樹(shù)深度為 h + 1 + 1，所以平衡因子為 0。
• 結(jié)點(diǎn) 60 的右子樹(shù)深度為 h + 1，左子樹(shù)深度為 h + 1，所以平衡因子為 0。

這樣旋轉(zhuǎn)以后還滿足二叉搜索樹(shù)的性質(zhì)嗎？當(dāng)面滿足，原因如下：

• subL 的右子樹(shù)當(dāng)中結(jié)點(diǎn)的值本身就比 parent 的值小，因此可以作為 parent 的左子樹(shù)。
• 而 parent 及其右子樹(shù)當(dāng)中結(jié)點(diǎn)的值本身就比 subL 的值大，因此可以作為 subL 的右子樹(shù)。

什么時(shí)候需要用到右旋操作呢？可以看到，當(dāng) parent 的平衡因子為 -2，cur 的平衡因子為 -1 時(shí)，需要進(jìn)行右單旋。并且經(jīng)過(guò)右單旋后，樹(shù)的高度沒(méi)有發(fā)生變化，所以右單旋后無(wú)需繼續(xù)往上更新平衡因子。

右單旋動(dòng)圖演示：

可以看到，我們?cè)?9 的左邊插入一個(gè)值為 5 的新節(jié)點(diǎn)，那么此時(shí) 9 的平衡因子從 0 變成了 -1，11 的平衡因子從 -1 變成了 -2，出現(xiàn)了左邊高，右邊低的局面，所以需要進(jìn)行右單旋

代碼示例

private:
	// 右單旋（左邊高就右單旋）
	void RotateR(Node* parent)
	{Node* subL = parent->_left; 
		Node* subLR = subL->_right;
		Node* ppNode = parent->_parent;

		// 1.建立parent和subLR之間的關(guān)系
		parent->_left = subLR;
		if (subLR) // 如果subLR節(jié)點(diǎn)不為空，那么要更新它的parent
		{	subLR->_parent = parent;
		}
		 
		// 2.建立subL和parent之間的關(guān)系
		subL->_right = parent;
		parent->_parent = subL;

		// 3.建立ppNode和subL之間的關(guān)系（分情況討論parent是整顆樹(shù)的根，還是局部子樹(shù)）
		if (parent == _root) // 當(dāng)parent是根節(jié)點(diǎn)時(shí)
		{	_root = subL; // subL就變成了新的根節(jié)點(diǎn)
			_root->_parent = nullptr; // 根節(jié)點(diǎn)的的parent為空
		}
		else // 當(dāng)parent是整個(gè)樹(shù)的局部子樹(shù)時(shí)
		{	if (parent == ppNode->_left) // 如果parent在ppNode的左邊
			{		ppNode->_left = subL; // 那么subL就是parent的左子樹(shù)
			}
			else // 如果parent在ppNode的右邊
			{		ppNode->_right = subL; // 那么subL就是parent的右子樹(shù)
			}
			subL->_parent = ppNode; // subR的parent還要指向ppNode
		}
		// 更新平衡因子
		parent->_bf = 0;
		subL->_bf = 0;
	}

需要注意，如果在旋轉(zhuǎn)前 parent（60） 就是樹(shù)的根，那么此時(shí)只需要更新根結(jié)點(diǎn)為 subL（30）即可。

如果 parent（60） 只是整顆樹(shù)局部的一顆子樹(shù)，那么此時(shí)就需要看 60 是它父親的左子樹(shù)還是右子樹(shù)，然后再和 subL 鏈接起來(lái)。

🍑 左右雙旋

下面是一個(gè) AVL 樹(shù)的抽象圖，長(zhǎng)方形條代表的是子樹(shù)，h表示 a 和 d 兩顆子樹(shù)的高度，h-1代表 b 和 c 兩顆子樹(shù)的高度。

• 結(jié)點(diǎn) 90 的右子樹(shù)深度為 h + 1，左子樹(shù)深度為 h + 1 + 1，所以平衡因子為 -1。
• 結(jié)點(diǎn) 30 的右子樹(shù)深度為 h - 1 + 1 + 1，左子樹(shù)深度為 h + 1，所以平衡因子為 0。
• 結(jié)點(diǎn) 60 的右子樹(shù)深度為 h - 1，左子樹(shù)深度為 h - 1，所以平衡因子為 0。

現(xiàn)在我們?cè)?b 子樹(shù)的中插入一個(gè)新結(jié)點(diǎn)，那么此時(shí) b 子樹(shù)的高度就變成了 h，同時(shí)結(jié)點(diǎn) 60 的平衡因子變成了 -1，結(jié)點(diǎn) 30 的平衡因子變成了 1，結(jié)點(diǎn) 90 的平衡因子變成了 -2，此時(shí)如果單純的以結(jié)點(diǎn) 90 為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋或者右單旋以后，那么仍然不是 AVL 樹(shù)，所以需要采取左右雙旋的方式。

注意：在 b 子樹(shù)當(dāng)中新增結(jié)點(diǎn)，或是在 c 子樹(shù)當(dāng)中新增結(jié)點(diǎn)，均會(huì)引發(fā)左右雙旋，這里以在 b 子樹(shù)當(dāng)中新增結(jié)點(diǎn)為例。

左右雙旋的步驟如下：

• 先以 subL 為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋。
• 然后以 parent 為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋。
• 最后再更新平衡因子。

（1）以 30 為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋

（2）以 90 為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋

左右雙旋后，實(shí)際上就是讓 subLR 的左子樹(shù)和右子樹(shù)，分別作為 subL 和 parent 的右子樹(shù)和左子樹(shù)，再讓 subL 和 parent 分別作為 subLR 的左右子樹(shù)，最后讓 subLR 作為整個(gè)子樹(shù)的根

這樣旋轉(zhuǎn)以后還滿足二叉搜索樹(shù)的性質(zhì)嗎？當(dāng)面滿足，原因如下：

• subLR 的左子樹(shù)當(dāng)中的結(jié)點(diǎn)本身就比 subL 的值大，因此可以作為 subL 的右子樹(shù)。
• subLR 的右子樹(shù)當(dāng)中的結(jié)點(diǎn)本身就比 parent 的值小，因此可以作為 parent 的左子樹(shù)。
• 經(jīng)過(guò)步驟1 和 2 以后，subL 及其子樹(shù)當(dāng)中結(jié)點(diǎn)的值都就比 subLR 的值小，而 parent 及其子樹(shù)當(dāng)中結(jié)點(diǎn)的值都就比 subLR 的值大，因此它們可以分別作為 subLR 的左右子樹(shù)。

左右雙旋后，平衡因子的更新隨著 subLR 原始平衡因子的不同分為以下三種情況：

（1）當(dāng) subLR 原始平衡因子是 -1 時(shí)，左右雙旋后 parent、subL、subLR 的平衡因子分別更新為 1、0、0

（2）當(dāng) subLR 原始平衡因子是 1 時(shí)，左右雙旋后 parent、subL、subLR 的平衡因子分別更新為 0、-1、0

（3）當(dāng) subLR 原始平衡因子是 0 時(shí)（說(shuō)明 subLR 為新增結(jié)點(diǎn)），左右雙旋后 parent、subL、subLR 的平衡因子分別更新為0、0、0

可以看到，經(jīng)過(guò)左右雙旋后，樹(shù)的高度沒(méi)有發(fā)生變化，所以左右雙旋后無(wú)需繼續(xù)往上更新平衡因子。

代碼示例

private:
// 左右雙旋（先左單旋，再右單旋）
	void RotateLR(Node* parent)
	{Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		// 1.先以subL為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
		RotateL(parent->_left);

		// 2.再以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋
		RotateR(parent);

		// 3.更新平衡因子
		if (bf == 0)
		{	parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{	parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{	parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{	// 如果走到了這里，說(shuō)明subLR的平衡因子在旋轉(zhuǎn)前就有問(wèn)題
			assert(false);
		}
	}

🍑 右左雙旋

下面是一個(gè) AVL 樹(shù)的抽象圖，長(zhǎng)方形條代表的是子樹(shù)，h表示 a 和 d 兩顆子樹(shù)的高度，h-1代表 b 和 c 兩顆子樹(shù)的高度。

• 結(jié)點(diǎn) 30 的右子樹(shù)深度為 h + 1 + 1，左子樹(shù)深度為 h + 1，所以平衡因子為 1。
• 結(jié)點(diǎn) 90 的右子樹(shù)深度為 h + 1，左子樹(shù)深度為 h - 1 + 1 + 1，所以平衡因子為 0。
• 結(jié)點(diǎn) 60 的右子樹(shù)深度為 h - 1，左子樹(shù)深度為 h - 1，所以平衡因子為 0。

現(xiàn)在我們?cè)?c 子樹(shù)的中插入一個(gè)新結(jié)點(diǎn)，那么此時(shí) c 子樹(shù)的高度就變成了 h，同時(shí)結(jié)點(diǎn) 60 的平衡因子變成了 1，結(jié)點(diǎn) 00 的平衡因子變成了 -1，結(jié)點(diǎn) 30 的平衡因子變成了 -2，此時(shí)如果單純的以結(jié)點(diǎn) 30 為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋或者右單旋以后，那么仍然不是 AVL 樹(shù)，所以需要采取右左雙旋的方式。

注意：在 b 子樹(shù)當(dāng)中新增結(jié)點(diǎn)，或是在 c 子樹(shù)當(dāng)中新增結(jié)點(diǎn)，均會(huì)引發(fā)右左雙旋，這里以在 c 子樹(shù)當(dāng)中新增結(jié)點(diǎn)為例。

右左雙旋的步驟如下：

• 先以 subR 為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋。
• 然后以 parent 為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋。
• 最后再更新平衡因子。

（1）以 90 為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋

（2）以 30 為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋

右左雙旋后，實(shí)際上就是讓 subRL 的左子樹(shù)和右子樹(shù)，分別作為 parent 和 subR 的右子樹(shù)和左子樹(shù)，再讓 parent 和 subR 分別作為 subRL 的左右子樹(shù)，最后讓 subRL 作為整個(gè)子樹(shù)的根。

這樣旋轉(zhuǎn)以后還滿足二叉搜索樹(shù)的性質(zhì)嗎？當(dāng)面滿足，原因如下：

• subRL 的左子樹(shù)當(dāng)中的結(jié)點(diǎn)本身就比 parent 的值大，因此可以作為 parent 的右子樹(shù)。
• subRL 的右子樹(shù)當(dāng)中的結(jié)點(diǎn)本身就比 subR 的值小，因此可以作為 subR 的左子樹(shù)。
• 經(jīng)過(guò)步驟 1 和 2 以后，parent 及其子樹(shù)當(dāng)中結(jié)點(diǎn)的值都就比 subRL 的值小，而 subR 及其子樹(shù)當(dāng)中結(jié)點(diǎn)的值都就比 subRL 的值大，因此它們可以分別作為 subRL 的左右子樹(shù)。

右左雙旋后，平衡因子的更新隨著 subLR 原始平衡因子的不同分為以下三種情況：

（1）當(dāng) subRL 原始平衡因子是 1 時(shí)，左右雙旋后 parent、subR、subRL 的平衡因子分別更新為 -1、0、0

（2）當(dāng) subRL 原始平衡因子是 -1 時(shí)，左右雙旋后 parent、subR、subRL 的平衡因子分別更新為 0、1、0

（3）當(dāng) subRL 原始平衡因子是 0 時(shí)（說(shuō)明 subRL為新增結(jié)點(diǎn)），左右雙旋后 parent、subR、subRL 的平衡因子分別更新為0、0、0

可以看到，經(jīng)過(guò)右左雙旋后，樹(shù)的高度沒(méi)有發(fā)生變化，所以右左雙旋后無(wú)需繼續(xù)往上更新平衡因子。

代碼示例

private:
	// 右左雙旋（先右單旋，再左單旋）
	void RotateRL(Node* parent)
	{Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		// 1.先以subR為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋
		RotateR(parent->_right);

		// 2.再以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
		RotateL(parent);

		// 3.更新平衡因子
		if (bf == 0)
		{	subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == 1)
		{	subRL->_bf = 0;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{	subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{	// 如果走到了這里，說(shuō)明subRL的平衡因子在旋轉(zhuǎn)前就有問(wèn)題
			assert(false);
		}
	}

🍑 總結(jié)

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

1. parent 的平衡因子為 2，說(shuō)明 parent 的右子樹(shù)高，設(shè) parent 的右子樹(shù)的根為 subR
   • 當(dāng) subR 的平衡因子為 1 時(shí)，執(zhí)行左單旋
   • 當(dāng) subR 的平衡因子為 -1 時(shí)，執(zhí)行右左雙旋
2. parent 的平衡因子為 -2，說(shuō)明 parent 的左子樹(shù)高，設(shè) parent 的左子樹(shù)的根為 subL
   • 當(dāng) subL 的平衡因子為 -1 是，執(zhí)行右單旋
   • 當(dāng) subL 的平衡因子為 1 時(shí)，執(zhí)行左右雙旋

旋轉(zhuǎn)完成后，原 parent 為根的子樹(shù)個(gè)高度降低，已經(jīng)平衡，不需要再向上更新。

6. AVL樹(shù)的刪除

平衡二叉樹(shù)的刪除操作與插入操作類(lèi)似，先執(zhí)行標(biāo)準(zhǔn)的 BST 刪除操作（可以參考文章： 什么是二叉查找樹(shù)），然后進(jìn)行相應(yīng)的平衡操作。

主要是三個(gè)大思路：

1. 按二叉搜索樹(shù)的規(guī)則刪除
2. 更新平衡因子
3. 出現(xiàn)不平衡，需要旋轉(zhuǎn)調(diào)整

只不過(guò)與二叉搜索樹(shù)的刪除不同的是，刪除節(jié)點(diǎn)后的平衡因子需要不斷更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。

下面簡(jiǎn)單講解一下刪除的算法思想吧。

🍑 算法思想

我們以刪除一個(gè)結(jié)點(diǎn)w為例進(jìn)行說(shuō)明平衡二叉樹(shù)刪除操作的具體算法步驟：

• 對(duì)結(jié)點(diǎn)w執(zhí)行標(biāo)準(zhǔn)的二叉搜索樹(shù)的刪除操作；
• 從結(jié)點(diǎn)w開(kāi)始，向上回溯，找到第一個(gè)不平衡的結(jié)點(diǎn)z（即平衡因子不是 -1，0 或 1 的結(jié)點(diǎn)），設(shè)y為結(jié)點(diǎn)z的高度最高的孩子結(jié)點(diǎn)；x是結(jié)點(diǎn)y的高度最高的孩子結(jié)點(diǎn)。
• 然后對(duì)以z為根結(jié)點(diǎn)的子樹(shù)進(jìn)行平衡操作，其中x、y、z可以的位置有四種情況，BST 刪除操作之后的平衡操作也就處理以下四種情況：
  • y是z的左孩子，x是y的左孩子 （Left Left ，LL )；
  • y是z的左孩子，x是y的右孩子 （Left Right ，LR )；
  • y是z的右孩子，x是y的右孩子 （Right Right ，RR )；
  • y是z的右孩子，x是y的左孩子 （Right Right ，RL )；

這里的四種情況與插入操作一樣，但需要注意的是，插入操作僅需要對(duì)以z為根的子樹(shù)進(jìn)行平衡操作；而平衡二叉樹(shù)的刪除操作就不一樣，先對(duì)以z為根的子樹(shù)進(jìn)行平衡操作，之后可能需要對(duì)z的祖先結(jié)點(diǎn)進(jìn)行平衡操作，向上回溯直到根結(jié)點(diǎn)。

🍑 示例一

我們已刪除下圖中的結(jié)點(diǎn) 32 為例進(jìn)行說(shuō)明。

第一步：由于 32 結(jié)點(diǎn)為葉子結(jié)點(diǎn)，直接刪除，并保存刪除結(jié)點(diǎn)的父節(jié)點(diǎn) 17 。

第二步：從節(jié)點(diǎn) 17 向上回溯，找到第一個(gè)不平衡結(jié)點(diǎn) 44 ，并找到不平衡結(jié)點(diǎn)的左右孩子中深度最深的結(jié)點(diǎn) 78 （即 y ）；以及 y 的孩子結(jié)點(diǎn)當(dāng)中深度最深的結(jié)點(diǎn) 50 （即 x ）。 發(fā)現(xiàn)為 RL 的情況。

第三步：對(duì)結(jié)點(diǎn) 78 進(jìn)行右旋操作

第四步：對(duì)結(jié)點(diǎn) 44 進(jìn)行左旋操作

🍑 示例二

我們以刪除下圖中的結(jié)點(diǎn) 80 為例進(jìn)行說(shuō)明。

第一步，由于結(jié)點(diǎn) 80 為葉子結(jié)點(diǎn)，則直接刪除，并保存結(jié)點(diǎn) 80 的父結(jié)點(diǎn) 78 。

第二步：從結(jié)點(diǎn) 78 開(kāi)始尋找第一個(gè)不平衡結(jié)點(diǎn)，發(fā)現(xiàn)就是結(jié)點(diǎn) 78 本身（即結(jié)點(diǎn) z ），找到結(jié)點(diǎn) 78 深度最深的葉子結(jié)點(diǎn) 60 （即結(jié)點(diǎn) y ），以及結(jié)點(diǎn) y 的深度最深的葉結(jié)點(diǎn) 55 （即結(jié)點(diǎn) x ）。即 LL 的情況。

第三步：右旋結(jié)點(diǎn) 78

第四步：從旋轉(zhuǎn)后的返回的新的根結(jié)點(diǎn) 60 向上回溯（這里就和平衡二叉樹(shù)的插入操作有別了奧，平衡二叉樹(shù)的插入操作僅對(duì)第一個(gè)不平衡結(jié)點(diǎn)的子樹(shù)進(jìn)行平衡操作，而AVL的刪除需要不斷地回溯，直到根結(jié)點(diǎn)平衡為止 ），判斷是否還有不平衡結(jié)點(diǎn)，發(fā)現(xiàn)整棵樹(shù)的根結(jié)點(diǎn) 50 為第一個(gè)不平衡結(jié)點(diǎn)，找到對(duì)應(yīng)的 y 結(jié)點(diǎn) 25 和 x 結(jié)點(diǎn) 10 。同樣是 LL 的情況。

第五步：對(duì) z 結(jié)點(diǎn) 50 進(jìn)行右旋操作。

🍑 代碼實(shí)現(xiàn)

關(guān)于左旋與右旋操作，以及平衡因子的計(jì)算與之前講的文章（ 什么是二叉查找樹(shù)）中的實(shí)現(xiàn)是一致的，我們直接看 AVL 樹(shù)刪除操作的實(shí)現(xiàn)代碼：

代碼示例

// 刪除函數(shù)
	bool Erase(const K& key)
	{//用于遍歷二叉樹(shù)
		Node* parent = nullptr;
		Node* cur = _root;
		//用于標(biāo)記實(shí)際的刪除結(jié)點(diǎn)及其父結(jié)點(diǎn)
		Node* delParentPos = nullptr;
		Node* delPos = nullptr;
		while (cur)
		{	if (key< cur->_kv.first) //所給key值小于當(dāng)前結(jié)點(diǎn)的key值
			{		//往該結(jié)點(diǎn)的左子樹(shù)走
				parent = cur;
				cur = cur->_left;
			}
			else if (key >cur->_kv.first) //所給key值大于當(dāng)前結(jié)點(diǎn)的key值
			{		//往該結(jié)點(diǎn)的右子樹(shù)走
				parent = cur;
				cur = cur->_right;
			}
			else //找到了待刪除結(jié)點(diǎn)
			{		if (cur->_left == nullptr) //待刪除結(jié)點(diǎn)的左子樹(shù)為空
				{if (cur == _root) //待刪除結(jié)點(diǎn)是根結(jié)點(diǎn)
					{_root = _root->_right; //讓根結(jié)點(diǎn)的右子樹(shù)作為新的根結(jié)點(diǎn)
						if (_root)
							_root->_parent = nullptr;
						delete cur; //刪除原根結(jié)點(diǎn)
						return true; //根結(jié)點(diǎn)無(wú)祖先結(jié)點(diǎn)，無(wú)需進(jìn)行平衡因子的更新操作
					}
					else
					{delParentPos = parent; //標(biāo)記實(shí)際刪除結(jié)點(diǎn)的父結(jié)點(diǎn)
						delPos = cur; //標(biāo)記實(shí)際刪除的結(jié)點(diǎn)
					}
					break; //刪除結(jié)點(diǎn)有祖先結(jié)點(diǎn)，需更新平衡因子
				}
				else if (cur->_right == nullptr) //待刪除結(jié)點(diǎn)的右子樹(shù)為空
				{if (cur == _root) //待刪除結(jié)點(diǎn)是根結(jié)點(diǎn)
					{_root = _root->_left; //讓根結(jié)點(diǎn)的左子樹(shù)作為新的根結(jié)點(diǎn)
						if (_root)
							_root->_parent = nullptr;
						delete cur; //刪除原根結(jié)點(diǎn)
						return true; //根結(jié)點(diǎn)無(wú)祖先結(jié)點(diǎn)，無(wú)需進(jìn)行平衡因子的更新操作
					}
					else
					{delParentPos = parent; //標(biāo)記實(shí)際刪除結(jié)點(diǎn)的父結(jié)點(diǎn)
						delPos = cur; //標(biāo)記實(shí)際刪除的結(jié)點(diǎn)
					}
					break; //刪除結(jié)點(diǎn)有祖先結(jié)點(diǎn)，需更新平衡因子
				}
				else //待刪除結(jié)點(diǎn)的左右子樹(shù)均不為空
				{//替換法刪除
					//尋找待刪除結(jié)點(diǎn)右子樹(shù)當(dāng)中key值最小的結(jié)點(diǎn)作為實(shí)際刪除結(jié)點(diǎn)
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{minParent = minRight;
						minRight = minRight->_left;
					}
					cur->_kv.first = minRight->_kv.first; //將待刪除結(jié)點(diǎn)的key改為minRight的key
					cur->_kv.second = minRight->_kv.second; //將待刪除結(jié)點(diǎn)的value改為minRight的value
					delParentPos = minParent; //標(biāo)記實(shí)際刪除結(jié)點(diǎn)的父結(jié)點(diǎn)
					delPos = minRight; //標(biāo)記實(shí)際刪除的結(jié)點(diǎn)
					break; //刪除結(jié)點(diǎn)有祖先結(jié)點(diǎn)，需更新平衡因子
				}
			}
		}
		if (delParentPos == nullptr) //delParentPos沒(méi)有被修改過(guò)，說(shuō)明沒(méi)有找到待刪除結(jié)點(diǎn)
		{	return false;
		}

		//記錄待刪除結(jié)點(diǎn)及其父結(jié)點(diǎn)（用于后續(xù)實(shí)際刪除）
		Node* del = delPos;
		Node* delP = delParentPos;

		//更新平衡因子
		while (delPos != _root) //最壞一路更新到根結(jié)點(diǎn)
		{	if (delPos == delParentPos->_left) //delParentPos的左子樹(shù)高度降低
			{		delParentPos->_bf++; //delParentPos的平衡因子++
			}
			else if (delPos == delParentPos->_right) //delParentPos的右子樹(shù)高度降低
			{		delParentPos->_bf--; //delParentPos的平衡因子--
			}
			//判斷是否更新結(jié)束或需要進(jìn)行旋轉(zhuǎn)
			if (delParentPos->_bf == 0)//需要繼續(xù)往上更新平衡因子
			{		//delParentPos樹(shù)的高度變化，會(huì)影響其父結(jié)點(diǎn)的平衡因子，需要繼續(xù)往上更新平衡因子
				delPos = delParentPos;
				delParentPos = delParentPos->_parent;
			}
			else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新結(jié)束
			{		break; //delParent樹(shù)的高度沒(méi)有發(fā)生變化，不會(huì)影響其父結(jié)點(diǎn)及以上結(jié)點(diǎn)的平衡因子
			}
			else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要進(jìn)行旋轉(zhuǎn)（此時(shí)delParentPos樹(shù)已經(jīng)不平衡了）
			{		if (delParentPos->_bf == -2)
				{if (delParentPos->_left->_bf == -1)
					{Node* tmp = delParentPos->_left; //記錄delParentPos右旋轉(zhuǎn)后新的根結(jié)點(diǎn)
						RotateR(delParentPos); //右單旋
						delParentPos = tmp; //更新根結(jié)點(diǎn)
					}
					else if (delParentPos->_left->_bf == 1)
					{Node* tmp = delParentPos->_left->_right; //記錄delParentPos左右旋轉(zhuǎn)后新的根結(jié)點(diǎn)
						RotateLR(delParentPos); //左右雙旋
						delParentPos = tmp; //更新根結(jié)點(diǎn)
					}
					else //delParentPos->_left->_bf == 0
					{Node* tmp = delParentPos->_left; //記錄delParentPos右旋轉(zhuǎn)后新的根結(jié)點(diǎn)
						RotateR(delParentPos); //右單旋
						delParentPos = tmp; //更新根結(jié)點(diǎn)
						//平衡因子調(diào)整
						delParentPos->_bf = 1;
						delParentPos->_right->_bf = -1;
						break; //更正
					}
				}
				else //delParentPos->_bf == 2
				{if (delParentPos->_right->_bf == -1)
					{Node* tmp = delParentPos->_right->_left; //記錄delParentPos右左旋轉(zhuǎn)后新的根結(jié)點(diǎn)
						RotateRL(delParentPos); //右左雙旋
						delParentPos = tmp; //更新根結(jié)點(diǎn)
					}
					else if (delParentPos->_right->_bf == 1)
					{Node* tmp = delParentPos->_right; //記錄delParentPos左旋轉(zhuǎn)后新的根結(jié)點(diǎn)
						RotateL(delParentPos); //左單旋
						delParentPos = tmp; //更新根結(jié)點(diǎn)
					}
					else //delParentPos->_right->_bf == 0
					{Node* tmp = delParentPos->_right; //記錄delParentPos左旋轉(zhuǎn)后新的根結(jié)點(diǎn)
						RotateL(delParentPos); //左單旋
						delParentPos = tmp; //更新根結(jié)點(diǎn)
						//平衡因子調(diào)整
						delParentPos->_bf = -1;
						delParentPos->_left->_bf = 1;
						break; //更正
					}
				}
				//delParentPos樹(shù)的高度變化，會(huì)影響其父結(jié)點(diǎn)的平衡因子，需要繼續(xù)往上更新平衡因子
				delPos = delParentPos;
				delParentPos = delParentPos->_parent;
				//break; //error
			}
			else
			{		assert(false); //在刪除前樹(shù)的平衡因子就有問(wèn)題
			}
		}
		//進(jìn)行實(shí)際刪除
		if (del->_left == nullptr) //實(shí)際刪除結(jié)點(diǎn)的左子樹(shù)為空
		{	if (del == delP->_left) //實(shí)際刪除結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子
			{		delP->_left = del->_right;
				if (del->_right)
					del->_right->_parent = parent;
			}
			else //實(shí)際刪除結(jié)點(diǎn)是其父結(jié)點(diǎn)的右孩子
			{		delP->_right = del->_right;
				if (del->_right)
					del->_right->_parent = parent;
			}
		}
		else //實(shí)際刪除結(jié)點(diǎn)的右子樹(shù)為空
		{	if (del == delP->_left) //實(shí)際刪除結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子
			{		delP->_left = del->_left;
				if (del->_left)
					del->_left->_parent = parent;
			}
			else //實(shí)際刪除結(jié)點(diǎn)是其父結(jié)點(diǎn)的右孩子
			{		delP->_right = del->_left;
				if (del->_left)
					del->_left->_parent = parent;
			}
		}
		delete del; //實(shí)際刪除結(jié)點(diǎn)
		return true;
	}

7. AVL樹(shù)的遍歷

中序遍歷和二叉樹(shù)的中序?qū)崿F(xiàn)一樣，只不過(guò)因?yàn)橹行蚴沁f歸遍歷，涉及到傳參，所以需要寫(xiě)一個(gè)子函數(shù)。

代碼示例

private:
	// 中序遍歷（子函數(shù)）
	void _InOrder(Node* root)
	{if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout<< root->_kv.first<< " ";
		_InOrder(root->_right);
	}
public:
	// 中序遍歷
	void InOrder()
	{_InOrder(_root);
		cout<< endl;
	}

8. AVL樹(shù)的查找

AVL樹(shù)的查找與二叉搜索樹(shù)一樣：

• 若樹(shù)為空樹(shù)，則查找失敗，返回 nullptr。
• 若樹(shù)不為空樹(shù)，則有以下三種情況：
  • 若 key 值小于當(dāng)前結(jié)點(diǎn)的值，則應(yīng)該在該結(jié)點(diǎn)的左子樹(shù)當(dāng)中進(jìn)行查找。
  • 若 key 值大于當(dāng)前結(jié)點(diǎn)的值，則應(yīng)該在該結(jié)點(diǎn)的右子樹(shù)當(dāng)中進(jìn)行查找。
  • 若 key 值等于當(dāng)前結(jié)點(diǎn)的值，則查找成功，返回對(duì)應(yīng)結(jié)點(diǎn)。

代碼示例

public:
	// 查找函數(shù)
	Node* Find(const K& key)
	{Node* cur = _root;
		while (cur)
		{	if (cur->_kv.first< key) // key值大于該結(jié)點(diǎn)的值
			{		cur = cur->_left; // 在該結(jié)點(diǎn)的右子樹(shù)當(dāng)中查找
			}
			else if (cur->_kv.first< key) // key值小于該結(jié)點(diǎn)的值
			{		cur = cur->_right; // 在該結(jié)點(diǎn)的左子樹(shù)當(dāng)中查找
			}
			else // 當(dāng)前節(jié)點(diǎn)的值等于key值
			{		return cur; //返回該結(jié)點(diǎn)
			}
		}
		return nullptr; //查找失敗
	}

9. AVL樹(shù)的高度

這里和求二叉樹(shù)的深度是一樣的方式，采用分治的思想：

• 若為空樹(shù)，則深度為 0。

• 若不為空樹(shù)，則深度 = 左右子樹(shù)中深度大的值 + 1（為什么要加1呢？因?yàn)檫€有第一層，也就是根節(jié)點(diǎn)這一層?。?/p>

代碼示例

private:
	// 求樹(shù)的高度（子函數(shù)）
	int _Height(Node* root)
	{if (root == nullptr) // 空樹(shù)高度為0
			return 0;

		int lh = _Height(root->_left); // 遞歸計(jì)算左子樹(shù)高度
		int rh = _Height(root->_right); // 遞歸計(jì)算右子樹(shù)高度

		return lh >rh ? lh + 1 : rh + 1; // 左樹(shù)高度或者右樹(shù)高度大的哪一個(gè)，然后再+1，就是整棵樹(shù)的高度
	}
public:
	// 樹(shù)的高度
	int Height()
	{return _Height(_root);
	}

10. AVL樹(shù)的驗(yàn)證

AVL樹(shù)是在二叉搜索樹(shù)的基礎(chǔ)上加入了平衡性的限制，因此要驗(yàn)證AVL樹(shù)，可以分為下面兩步：

（1）驗(yàn)證其為二叉搜索樹(shù)

• 如果中序遍歷可得到一個(gè)有序的序列，就說(shuō)明為二叉搜索樹(shù)

（2）驗(yàn)證其為平衡樹(shù)

• 每個(gè)節(jié)點(diǎn)子樹(shù)高度差的絕對(duì)值不超過(guò) 1（注意節(jié)點(diǎn)中如果沒(méi)有平衡因子）

• 節(jié)點(diǎn)的平衡因子是否計(jì)算正確

檢測(cè)二叉樹(shù)是否平衡的代碼

private:
	// 判斷是否為平衡二叉樹(shù)（子函數(shù)）
	bool _IsBalanceTree(Node* root)
	{// 空樹(shù)也是AVL樹(shù)
		if (nullptr == root)
			return true;

		// 計(jì)算pRoot節(jié)點(diǎn)的平衡因子：即pRoot左右子樹(shù)的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;

		// 如果計(jì)算出的平衡因子與pRoot的平衡因子不相等，或者
		// pRoot平衡因子的絕對(duì)值超過(guò)1，則一定不是AVL樹(shù)
		if (abs(diff) >= 2)
		{	cout<< root->_kv.first<< "節(jié)點(diǎn)平衡因子異常"<< endl;
			return false;
		}

		if (diff != root->_bf)
		{	cout<< root->_kv.first<< "節(jié)點(diǎn)平衡因子不符合實(shí)際"<< endl;
			return false;
		}

		// pRoot的左和右如果都是AVL樹(shù)，則該樹(shù)一定是AVL樹(shù)
		return _IsBalanceTree(root->_left)
			&& _IsBalanceTree(root->_right);
	}
public:
	// 判斷是否為平衡二叉樹(shù)
	bool IsBalanceTree()
	{return _IsBalanceTree(_root);
	}

🍑 數(shù)據(jù)測(cè)試

（1）測(cè)試一組有序值

// 插入有序值
void TestAVLTree1()
{const int N = 20;

	vectorv;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i< N; ++i)
	{v.push_back(i);
	}

	AVLTreet;
	for (auto e : v)
	{t.Insert(make_pair(e, e));
	}

	if (t.IsBalanceTree())
	{cout<< "AVL樹(shù)平衡"<< endl;
	}
	else
	{cout<< "AVL樹(shù)不平衡"<< endl;
	}
	
	cout<< "AVL樹(shù)高度："<< t.Height()<< endl;

	cout<< "中序遍歷：";
	t.InOrder();
}

運(yùn)行結(jié)果

（2）測(cè)試一組隨機(jī)值

// 插入隨機(jī)值
void TestAVLTree2()
{const size_t N = 20;

	vectorv;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i< N; ++i)
	{v.push_back(rand());
	}

	AVLTreet;
	for (auto e : v)
	{t.Insert(make_pair(e, e));
	}
	if (t.IsBalanceTree())
	{cout<< "AVL樹(shù)平衡"<< endl;
	}
	else
	{cout<< "AVL樹(shù)不平衡"<< endl;
	}
	cout<< "AVL樹(shù)高度："<< t.Height()<< endl;

	cout<< "中序遍歷：";
	t.InOrder();
}

運(yùn)行結(jié)果

11. AVL樹(shù)優(yōu)缺點(diǎn)分析

優(yōu)點(diǎn)：

• 平衡二叉樹(shù)的優(yōu)點(diǎn)不言而喻，相對(duì)于二叉排序樹(shù)（BST）而言，平衡二叉樹(shù)避免了二叉排序樹(shù)可能出現(xiàn)的最極端情況（斜樹(shù)）問(wèn)題，其平均查找的時(shí)間復(fù)雜度為 O ( l o g N ) O(logN) O(logN)

缺點(diǎn)：

• 平衡二叉樹(shù)為了保持平衡，動(dòng)態(tài)進(jìn)行插入和刪除操作的代價(jià)也會(huì)增加。因此出現(xiàn)了后來(lái)的紅黑樹(shù)（下篇文章會(huì)講解）

時(shí)間復(fù)雜度分析：

• 左旋和右旋操作僅需要改變幾個(gè)指針，時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)，更新結(jié)點(diǎn)的深度以及獲得平衡因子僅需要常數(shù)時(shí)間，所以平衡二叉樹(shù)的刪除操作的時(shí)間復(fù)雜度與二叉排序樹(shù)BST的刪除操作一樣，均為 O ( h ) O(h) O(h)，其中 h 為樹(shù)的高度。由于AVL 樹(shù)是平衡的，所以高度 h = l o g N h=logN h=logN ，因此，AVL 刪除操作的時(shí)間復(fù)雜度為 O ( l o g N ) O(logN) O(logN)

總結(jié)：

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

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：C/C++數(shù)據(jù)結(jié)構(gòu)（十一）——平衡二叉樹(shù)（AVL樹(shù)）-創(chuàng)新互聯(lián)
鏈接分享：http://muchs.cn/article48/djheep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、微信小程序、網(wǎng)站策劃、App開(kāi)發(fā)、Google、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)