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

1. AVL 樹的概念

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

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

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

如果一棵二叉搜索樹是高度平衡的，它就是 AVL 樹。如果它有 n 個(gè)節(jié)點(diǎn)，其高度可保持在 $O(lo{g}_{2}n)$，搜索時(shí)間復(fù)雜度是 $O(lo{g}_{2}n)$。

2. AVL 樹節(jié)點(diǎn)的定義

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data)
		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
		, _data(data), _bf(0)
	{}
	
	AVLTreeNode<T>* _pLeft;		// 該節(jié)點(diǎn)的左孩子
	AVLTreeNode<T>* _pRight; 	// 該節(jié)點(diǎn)的右孩子
	AVLTreeNode<T>* _pParent; 	// 該節(jié)點(diǎn)的雙親
	T _data;
	int _bf; 					// 該節(jié)點(diǎn)的平衡因子
};

3. AVL 樹的插入

AVL 樹就是在二叉搜索樹的基礎(chǔ)上引入了平衡因子，因此 AVL 樹也可以看成是二叉搜索樹。那么 AVL 樹的插入過程可以分為兩步：

1. 按照二叉搜索樹的方式插入新節(jié)點(diǎn)；
2. 調(diào)整節(jié)點(diǎn)的平衡因子。

bool Insert(const T& data)
{
	// 1. 先按照二叉搜索樹的規(guī)則將節(jié)點(diǎn)插入到AVL樹中
	// ...
	
	// 2. 新節(jié)點(diǎn)插入后，AVL樹的平衡性可能會(huì)遭到破壞，此時(shí)就需要更新平衡因子，并檢測(cè)是否破壞了AVL樹的平衡性
	
	/*
	pCur插入后，pParent的平衡因子一定需要調(diào)整，在插入之前，pParent
	的平衡因子分為三種情況：-1，0, 1, 分以下兩種情況：
		1. 如果pCur插入到pParent的左側(cè)，只需給pParent的平衡因子-1即可
		2. 如果pCur插入到pParent的右側(cè)，只需給pParent的平衡因子+1即可

	此時(shí)：pParent的平衡因子可能有三種情況：0，正負(fù)1，正負(fù)2
		1. 如果pParent的平衡因子為0，說明插入之前pParent的平衡因子為正負(fù)1，插入后被調(diào)整
		   成0，此時(shí)滿足AVL樹的性質(zhì)，插入成功
		2. 如果pParent的平衡因子為正負(fù)1，說明插入前pParent的平衡因子一定為0，插入后被更
		   新成正負(fù)1，此時(shí)以pParent為根的樹的高度增加，需要繼續(xù)向上更新
		3. 如果pParent的平衡因子為正負(fù)2，則pParent的平衡因子違反平衡樹的性質(zhì)，需要對(duì)其進(jìn)
		   行旋轉(zhuǎn)處理
	*/

	while (pParent)
	{
		// 更新雙親的平衡因子
		if (pCur == pParent->_pLeft)
			pParent->_bf--;
		else
			pParent->_bf++;
			
		// 更新后檢測(cè)雙親的平衡因子
		if (0 == pParent->_bf)
		{
			break;
		}
		else if (1 == pParent->_bf || -1 == pParent->_bf)
		{
			// 插入前雙親的平衡因子是0，插入后雙親的平衡因?yàn)闉?或者-1，說明以雙親為根的二叉樹
			// 的高度增加了一層，因此需要繼續(xù)向上調(diào)整
			pCur = pParent;
			pParent = pCur->_pParent;
		}
		else
		{
			// 雙親的平衡因子為正負(fù)2，違反了AVL樹的平衡性，需要對(duì)以pParent
			// 為根的樹進(jìn)行旋轉(zhuǎn)處理
			if (2 == pParent->_bf)
			{
				// ...
			}
			else
			{
				// ...
			}
		}
	}
	return true;
}

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

如果在一棵原本是平衡的 AVL 樹中插入一個(gè)新節(jié)點(diǎn)，可能造成不平衡，此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。根據(jù)節(jié)點(diǎn)插入位置的不同，AVL 樹的旋轉(zhuǎn)分為四種：

1. 新節(jié)點(diǎn)插入較高左子樹的左側(cè) - 左左：右單旋

   

   /*
   	上圖在插入前，AVL樹是平衡的，新節(jié)點(diǎn)插入到30的左子樹(注意：此處不是左孩子)中，30左
   子樹增加了一層，導(dǎo)致以60為根的二叉樹不平衡，要讓60平衡，只能將60左子樹的高度減少一層，右子
   樹增加一層，即將左子樹往上提，這樣60轉(zhuǎn)下來，因?yàn)?0比30大，只能將其放在30的右子樹，而如果30有
   右子樹，右子樹根的值一定大于30，小于60，只能將其放在60的左子樹，旋轉(zhuǎn)完成后，更新節(jié)點(diǎn)
   的平衡因子即可。在旋轉(zhuǎn)過程中，有以下幾種情況需要考慮：
   	1. 30節(jié)點(diǎn)的右孩子可能存在，也可能不存在
   	2. 60可能是根節(jié)點(diǎn)，也可能是子樹
   	   如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，要更新根節(jié)點(diǎn)
   	   如果是子樹，可能是某個(gè)節(jié)點(diǎn)的左子樹，也可能是右子樹
   */
   
   void _RotateR(PNode pParent)
   {
   	// pSubL: pParent的左孩子
   	// pSubLR: pParent左孩子的右孩子，注意：該
   	PNode pSubL = pParent->_pLeft;
   	PNode pSubLR = pSubL->_pRight;
   	
   	// 旋轉(zhuǎn)完成之后，30的右孩子作為雙親的左孩子
   	pParent->_pLeft = pSubLR;
   	// 如果30的左孩子的右孩子存在，更新親雙親
   	if (pSubLR)
   		pSubLR->_pParent = pParent;
   		
   	// 60 作為 30的右孩子
   	pSubL->_pRight = pParent;
   	
   	// 因?yàn)?0可能是棵子樹，因此在更新其雙親前必須先保存60的雙親
   	PNode pPParent = pParent->_pParent;
   	
   	// 更新60的雙親
   	pParent->_pParent = pSubL;
   	
   	// 更新30的雙親
   	pSubL->_pParent = pPParent;
   	
   	// 如果60是根節(jié)點(diǎn)，根新指向根節(jié)點(diǎn)的指針
   	if (NULL == pPParent)
   	{
   		_pRoot = pSubL;
   		pSubL->_pParent = NULL;
   	}
   	else
   	{
   		// 如果60是子樹，可能是其雙親的左子樹，也可能是右子樹
   		if (pPParent->_pLeft == pParent)
   			pPParent->_pLeft = pSubL;
   		else
   			pPParent->_pRight = pSubL;
   	}
   	
   	// 根據(jù)調(diào)整后的結(jié)構(gòu)更新部分節(jié)點(diǎn)的平衡因子
   	pParent->_bf = pSubL->_bf = 0;
   }
   

2. 新節(jié)點(diǎn)插入較高右子樹的右側(cè) - 右右：左單旋

   

   實(shí)現(xiàn)及情況考慮可參考右單旋。

3. 新節(jié)點(diǎn)插入較高左子樹的右側(cè) - 左右：先左單旋再右單旋

   

   將雙旋變成單旋后再旋轉(zhuǎn)，即：先對(duì) 30 進(jìn)行左單旋，然后再對(duì) 90 進(jìn)行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。

   // 旋轉(zhuǎn)之前，60的平衡因子可能是-1/0/1，旋轉(zhuǎn)完成之后，根據(jù)情況對(duì)其他節(jié)點(diǎn)的平衡因子進(jìn)行調(diào)整
   void _RotateLR(PNode pParent)
   {
   	PNode pSubL = pParent->_pLeft;
   	PNode pSubLR = pSubL->_pRight;
   	
   	// 旋轉(zhuǎn)之前，保存pSubLR的平衡因子，旋轉(zhuǎn)完成之后，需要根據(jù)該平衡因子來調(diào)整其他節(jié)點(diǎn)的平衡因子
   	int bf = pSubLR->_bf;
   	
   	// 先對(duì)30進(jìn)行左單旋
   	_RotateL(pParent->_pLeft);
   	
   	// 再對(duì)90進(jìn)行右單旋
   	_RotateR(pParent);
   	
   	if (1 == bf)
   		pSubL->_bf = -1;
   	else if (-1 == bf)
   		pParent->_bf = 1;
   }
   

4. 新節(jié)點(diǎn)插入較高右子樹的左側(cè) - 右左：先右單旋再左單旋

   

   參考左右雙旋。

總結(jié)：

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

1. pParent 的平衡因子為 2，說明 pParent 的右子樹高，設(shè) pParent 的右子樹的根為 pSubR：

   • 當(dāng) pSubR 的平衡因子為 1 時(shí)，執(zhí)行左單旋；
   • 當(dāng) pSubR 的平衡因子為 -1 時(shí)，執(zhí)行右左雙旋。

2. pParent 的平衡因子為 -2，說明 pParent 的左子樹高，設(shè) pParent 的左子樹的根為 pSubL：

   • 當(dāng) pSubL 的平衡因子為 -1 時(shí)，執(zhí)行右單旋；
   • 當(dāng) pSubL 的平衡因子為 1 時(shí)，執(zhí)行左右雙旋。

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

5. AVL 樹的驗(yàn)證

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

1. 驗(yàn)證其為二叉搜索樹

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

2. 驗(yàn)證其為平衡樹

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

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

     int _Height(PNode pRoot);
     bool _IsBalanceTree(PNode pRoot)
     {
     	// 空樹也是AVL樹
     	if (nullptr == pRoot) return true;
     	
     	// 計(jì)算pRoot節(jié)點(diǎn)的平衡因子：即pRoot左右子樹的高度差
     	int leftHeight = _Height(pRoot->_pLeft);
     	int rightHeight = _Height(pRoot->_pRight);
     	int diff = rightHeight - leftHeight;
     	
     	// 如果計(jì)算出的平衡因子與pRoot的平衡因子不相等，或者pRoot平衡因子的絕對(duì)值超過1，則一定不是AVL樹
     	if (diff != pRoot->_bf || (diff > 1 || diff < -1))
     		return false;
     		
     	// pRoot的左和右如果都是AVL樹，則該樹一定是AVL樹
     	return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot -> _pRight);
     }
     

3. 驗(yàn)證用例

   • 常規(guī)場(chǎng)景

     { 16, 3, 7, 11, 9, 26, 18, 14, 15 }

   • 特殊場(chǎng)景

     { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }

     

6. AVL 樹的刪除

因?yàn)?AVL 樹也是二叉搜索樹，可按照二叉搜索樹的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不過與刪除不同的是，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。

7. AVL 樹的性能

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

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】AVL 樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！