C++數(shù)據(jù)結(jié)構(gòu)AVL樹全面分析

更新時間：2022年02月28日 14:07:12 作者：呆呆獸學(xué)編程

今天的這一篇博客，我要跟大家介紹一顆樹——AVL樹，它也是一顆二叉搜索樹，它就是在二叉搜索樹中加了一個平衡因子的概念在里面，下面我就來和大家聊一聊這棵樹是個怎么樣的樹

??概念

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

它的左右子樹都是AVL樹
左右子樹高度之差的絕對值（也叫平衡因子）不超過1
我規(guī)定：平衡因子（balance factor）= 右子樹高度 - 左子樹高度（后面這樣實(shí)現(xiàn)）

??AVL樹的實(shí)現(xiàn)

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

這里節(jié)點(diǎn)是一個三叉鏈，里面存放了元素的數(shù)據(jù)和該節(jié)點(diǎn)此時的平衡因子。不管今后我們進(jìn)行什么操作，都要維持這里的平衡因子的絕對值不超過1。

template<class K, class V>
struct AVLTreeNode
{
	// 三叉鏈
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	int _bf; // balance factor  平衡因子 右子樹高度-左子樹高度

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

??AVL樹的插入

??方法概述

第一步：我們先按照二叉搜索樹樹插入節(jié)點(diǎn)的方式，插入節(jié)點(diǎn)（這一步很簡單，上一篇博客介紹過）

第二步：更新平衡因子，更新平衡因子的過程是一個難點(diǎn)，下面我給大家分析一下整個過程

??平衡因子的調(diào)節(jié)

??正常情況

實(shí)際上，我們應(yīng)該能夠發(fā)現(xiàn)，插入一個節(jié)點(diǎn)后，它之后影響它祖先的平衡因子（可能是所有祖先，也可能是一部分祖先），下面就是一個分析過程：

第一步：判斷父親節(jié)點(diǎn)是否存在，不存在直接結(jié)束，如果存在，且插入節(jié)點(diǎn)是它的左孩子，那么父親節(jié)點(diǎn)的平衡因子就減1，如果是父親的右，父親的平衡因子就加1。然后對父親節(jié)點(diǎn)的平衡因子進(jìn)行檢索。

第二步：繼續(xù)對父親節(jié)點(diǎn)的平衡因子進(jìn)行檢索，平衡因子會有一下三種情況

第一種情況：此時父親的平衡因子為0，則說明插入前父親的平衡因子為1或-1，缺少左節(jié)點(diǎn)或右節(jié)點(diǎn)插入后，插入的節(jié)點(diǎn)已經(jīng)補(bǔ)齊了左節(jié)點(diǎn)或右節(jié)點(diǎn)，整體高度不變，對上層無影響，不需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：

第二種情況此時父親節(jié)點(diǎn)的平衡因子為-1或1，則說明插入前父親的平衡因子為0，插入后增加了一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，整體高度增加1，對上層有影響，繼續(xù)迭代更新祖先的平衡因子。下面是一個演示圖：

第三種情況：此時父親節(jié)點(diǎn)的平衡因子為-2或2，則說明插入前父親的平衡因子為-1或1，多了一個左節(jié)點(diǎn)或一個右節(jié)點(diǎn)，插入后增加了一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，此時多了兩個左節(jié)點(diǎn)和右節(jié)點(diǎn)，這棵子樹一邊已經(jīng)被拉高了，此時這棵子樹不平衡了，需要旋轉(zhuǎn)處理。下面是一個演示圖：

??旋轉(zhuǎn)處理（出現(xiàn)了不平衡子樹）

旋轉(zhuǎn)有四種情況：

1.左單旋（新插入的節(jié)點(diǎn)在右子樹的右側(cè)）

具體步驟：讓subR的左孩子成為parent的右孩子，然后讓parent成為subR的左孩子，最后把兩個節(jié)點(diǎn)的平衡因子修改為0.

先畫一個具像圖給大家演示如何進(jìn)行這個操作（下面是一部分失衡的子樹）：

再畫一個抽像圖來演示：

代碼實(shí)現(xiàn)如下：

// 左單旋 bf為2  右邊高，把上面的壓下來放到左邊
void RotateL(Node* parent)
{		
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	// 1.先讓把subR的左邊（可能為空也可能不為空）作為parent的右邊
	parent->_right = subRL;
	// 2.如果subRL不為空，就讓subRL的父指針指向parent
	if (subRL) subRL->_parent = parent;
	// 3.先記錄parent的父節(jié)點(diǎn)的位置，然后把parent作為subR的左邊 
	Node* ppNode = parent->_parent;
	subR->_left = parent;
	// 4.parent的父指針指向subR
	parent->_parent = subR;

	// 5.如果ppNode為空==>說明subR現(xiàn)在是根節(jié)點(diǎn)，就讓subR的父指針指向nullptr
	//   不是根節(jié)點(diǎn)就把subR的父指針指向parent的父節(jié)點(diǎn)，parent的父節(jié)點(diǎn)（左或右）指向subR
	if (ppNode == nullptr)
	{
		// 更新根節(jié)點(diǎn)
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		// 判斷parent是ppNode的左還是右
		if (ppNode->_left == parent)
			ppNode->_left = subR;
		else
			ppNode->_right = subR;

		subR->_parent = ppNode;
	}

	// 6.把parent和subR的平衡因子更新為0
	subR->_bf = parent->_bf = 0;
}

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

具體步驟：讓subL的右孩子成為parent的左孩子，然后讓parent成為subL的右孩子，最后把兩個節(jié)點(diǎn)的平衡因子修改為0.

先畫一個具像圖給大家演示如何進(jìn)行這個操作（下面是一部分失衡的子樹）：

在給大家演示一下抽象圖：

代碼實(shí)現(xiàn)如下：

// 右單旋 bf為-2  左邊高，把上面的壓下來放到右邊
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	// 1.先讓把subL的右邊（可能為空也可能不為空）作為parent的左邊
	parent->_left = subLR;
	// 2.如果subLR不為空，就讓subLR的父指針指向parent
	if (subLR) subLR->_parent = parent;
	// 3.先記錄parent的父節(jié)點(diǎn)的位置，然后把parent作為subL的右邊
	Node* ppNode = parent->_parent;
	subL->_right = parent;
	// 4.parent的父指針指向subL
	parent->_parent = subL;

	// 5.如果ppNode為空==>說明subR現(xiàn)在是根節(jié)點(diǎn)，就讓subL的父指針指向nullptr
	//   不是根節(jié)點(diǎn)就把subL的父指針指向parent的父節(jié)點(diǎn)，parent的父節(jié)點(diǎn)（左或右）指向subL
	if (ppNode == nullptr)
	{
		// 更新根節(jié)點(diǎn)
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		// 判斷parent是ppNode的左還是右
		if (ppNode->_left == parent)
			ppNode->_left = subL;
		else
			ppNode->_right = subL;

		subL->_parent = ppNode;
	}

	// 6.把parent和subL的平衡因子更新為0
	subL->_bf = parent->_bf = 0;
}

3.右左雙旋（新節(jié)點(diǎn)插入在較高右子樹左側(cè)，這里和第一種情況的區(qū)別就是前者是直線，后者是折線）

具體步驟先對subR進(jìn)行一個右單旋，然后對parent進(jìn)行左單旋，修改平衡因子，有三種改法。

三個節(jié)點(diǎn)從左至右的三個節(jié)點(diǎn)一次是：parent、subRL和subR。

如果subRL的平衡因子為0，就將它們依次改為0，0, 0；

如果subRL的平衡因子為1，就將它們依次改為-1，0, 0；

如果subRL的平衡因子為-1，就將它們依次改為0，0, 1。

先看具像圖：

再看一個抽象圖（兩種情況）：

subRL的bf為1

subRL的bf為-1

代碼實(shí)現(xiàn)如下：

// 右左旋轉(zhuǎn)==>parent->_bf==2&&cur->_bf==-1
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;// 保留subRL的平衡因子的值，方便知道新插入的節(jié)點(diǎn)是在subRL的左子樹還是右子樹

	// 旋轉(zhuǎn) 先對subR進(jìn)行右旋轉(zhuǎn)，再對parent進(jìn)行左旋轉(zhuǎn)
	RotateR(subR);
	RotateL(parent);

	// 從左到右 parent subRL subR
	if (bf == -1)// subRL的左子樹  bf: 0 0 1
	{
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1)// subRL的右子樹 bf: -1 0 0
	{
		parent->_bf = -1;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
}

4.左右雙旋（新節(jié)點(diǎn)插入在較高右子樹左側(cè)，這里和第一種情況的區(qū)別就是前者是直線，后者是折線）

具體步驟先對subL進(jìn)行一個左單旋，然后對parent進(jìn)行右單旋，修改平衡因子，有三種改法。三個節(jié)點(diǎn)從左至右的三個節(jié)點(diǎn)一次是：subL、subLR和parent。（和上面的類似，這樣有助于我們記住平衡因子的調(diào)整，同時我們也可以畫簡圖理解記憶）

如果subLR的平衡因子為0，就將它們依次改為0，0, 0；

如果subLR的平衡因子為1，就將它們依次改為-1，0, 0；

如果subLR的平衡因子為-1，就將它們依次改為0，0, 1。

先看具像圖：

再看一個抽象圖（也有兩種情況）：

subLR的bf為-1

subLR的bf為1

代碼實(shí)現(xiàn)如下：

// 左右旋轉(zhuǎn)==>parent->_bf==-2&&cur->_bf==1
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的節(jié)點(diǎn)是在subLR的左子樹還是右子樹

	// 旋轉(zhuǎn) 先對subL進(jìn)行左旋轉(zhuǎn)，再對parent進(jìn)行右旋轉(zhuǎn)
	RotateL(subL);
	RotateR(parent);

	// 從左到右 subL subLR parent
	if (bf == -1)// subLR的左子樹  bf: 0 0 1
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)// subLR的右子樹 bf: -1 0 0
	{
		subL->_bf = -1;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
}

??插入代碼實(shí)現(xiàn)

插入的步驟也就是如上面說的一樣，下面的代碼我們通過迭代實(shí)現(xiàn)。

代碼實(shí)現(xiàn)如下：

bool Insert(const pair<K, V>& kv)
{
	// 先按照二叉搜索數(shù)一樣插入元素

	// 無節(jié)點(diǎn)是插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}

	// 有節(jié)點(diǎn)時插入
	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)
	{
		parent = cur;
		// 小于往左走
		if (kv.first < cur->_kv.first)
		{
			cur = cur->_left;
		}
		// 大于往右走
		else if (kv.first > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else
		{
			// 找到了，就返回false
			return false;
		}
	}

	cur = new Node(kv);
	// 判斷cur應(yīng)該插在parent的左還是右 
	// 小于在左，大于在右		
	if (cur->_kv.first < parent->_kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	// 更新parent的平衡因子
	
	// 節(jié)點(diǎn)的插入只會影響cur的祖先的平衡因子（不是所有的，是一部分，分情況）
	while (parent)
	{
		// 更新parent的平衡因子
		// cur在parent的左，parent->_bf--
		// cur在parent的右，parent->_bf++
		if (cur == parent->_left)
			parent->_bf--;
		else
			parent->_bf++;
		// bf 可能為 -2、-1、0、1、2
		// 如果平衡因子為0，說明更新之前，parent的bf為-1或1，現(xiàn)在補(bǔ)齊了左節(jié)點(diǎn)或右節(jié)點(diǎn)，bf==0，對上層無影響
		// 如果平衡因子為-1或1，說明更新之前，parent的bf為0，現(xiàn)在增加了一個左節(jié)點(diǎn)或有節(jié)點(diǎn)，bf==-1 || bf==1,對上層有影響
		// 如果平衡因子為-2或2，說明更新之前，parent的bf為-1或1，現(xiàn)在往左（右）節(jié)點(diǎn)補(bǔ)了左（右）節(jié)點(diǎn)，也就是一邊
		// 拉高了，樹不平衡了，需要用左旋轉(zhuǎn)或右旋轉(zhuǎn)來進(jìn)行調(diào)整
		if (parent->_bf == 0)
		{
			// 對上層無影響，退出
			break;
		}
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			// 對上層有影響，迭代更新
			cur = parent;
			parent = parent->_parent;
		}
		else
		{
			// 平衡樹出現(xiàn)了問題，需要調(diào)整
			// 1.右邊高，左旋轉(zhuǎn)調(diào)整
			if (parent->_bf == 2)
			{
				// 如果是一條直線==>左旋轉(zhuǎn)即可
				// 如果是一條折線==>右左旋轉(zhuǎn)
				if (cur->_bf == 1)
					RotateL(parent);
				else if (cur->_bf == -1)
					RotateRL(parent);

			}
			// 2.左邊高，右旋轉(zhuǎn)調(diào)整
			else if (parent->_bf == -2)
			{
				// 如果是一條直線==>右旋轉(zhuǎn)即可
				// 如果是一條折線==>左右旋轉(zhuǎn)
				if (cur->_bf == -1)
					RotateR(parent);
				else if (cur->_bf == 1)
					RotateLR(parent);
			}

			// 調(diào)整后是平衡樹，bf為0，不需要調(diào)整了
			break;
		}
	}

	return bool;
}

??AVL樹的查找

查找的代碼和二叉搜索樹是一樣的，這里就不過多介紹。

代碼實(shí)現(xiàn)如下：

bool Find(const K& key)
{
	if (_root == nullptr)
		return false;

	Node* cur = _root;
	while (cur)
	{
		// 小于往左走
		if (key < cur->_kv.first)
		{
			cur = cur->_left;
		}
		// 大于往右走
		else if (key > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else
		{
			// 找到了
			return true;
		}
	}

	return false;
}

??AVL樹的刪除

??方法概述

第一步：我們先按照二叉搜索樹樹刪除節(jié)點(diǎn)的方式，刪除節(jié)點(diǎn)（這一步很簡單，上一篇博客介紹過）

第二步：然后根據(jù)對應(yīng)刪除情況更新平衡因子，這里更新平衡因子的方法與插入的更新方法是相反的，下面我給大家分析一下整個過程

??平衡因子的調(diào)節(jié)

??正常情況

刪除節(jié)點(diǎn)后，如果刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)，就結(jié)束。否則根據(jù)刪除節(jié)點(diǎn)為父節(jié)點(diǎn)的左右調(diào)整父節(jié)點(diǎn)的平衡因子。如果刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子，那么父親節(jié)點(diǎn)的平衡因子加1，否則減1。然后對父親節(jié)點(diǎn)進(jìn)行檢索。

有以下幾種情況：

第一種情況：此時父親的平衡因子為0，則說明刪除前父親的平衡因子為1或-1，多出一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，刪除節(jié)點(diǎn)后，左右高度相等，整體高度減1，對上層有影響，需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：（如果此時3為根節(jié)點(diǎn)，那么也可以結(jié)束）

第二種情況：此時父親的平衡因子為-1或1，則說明刪除前父親的平衡因子為0，左右高度相等，刪除節(jié)點(diǎn)后，少了一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，但是整體高度不變，對上層無影響，不需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：

第三種情況：此時父親節(jié)點(diǎn)的平衡因子為-2或2，則說明刪除前父親的平衡因子為-1或1，多了一個左節(jié)點(diǎn)或一個右節(jié)點(diǎn)，刪除了一個右節(jié)點(diǎn)或左節(jié)點(diǎn)，此時多了兩個左節(jié)點(diǎn)和右節(jié)點(diǎn)，這棵子樹一邊已經(jīng)被拉高了，此時這棵子樹不平衡了，需要旋轉(zhuǎn)處理。下面是一個演示圖：

??需要旋轉(zhuǎn)處理的幾種情況

這里我只分析右邊高的情況，左邊高和它對稱的，操作是相同的。

情況一：

操作方法：對parent進(jìn)行左旋轉(zhuǎn)，因?yàn)閟ubR的平衡因子為0，需要繼續(xù)檢索，然后繼續(xù)迭代，把cur迭代sub的位置，parent到cur的父親的位置

具像圖：

抽象圖：

情況二：

操作方法：對parent進(jìn)行左旋，然后修改平衡因子，把subR的平衡因子改為-1，parent的平衡因子改為1，因?yàn)閟ubR的平衡因子為-1，所以無需迭代，直接結(jié)束

具像圖：

抽象圖：

情況三：

操作方法：對subR進(jìn)行右旋，然后對parent進(jìn)行左旋，此時subR的平衡因子為0，需迭代

具像圖：

抽象圖：

??刪除代碼如下

刪除代碼如下：

bool Erase(const K& key)
{
	if (_root == nullptr)
		return false;

	// 有節(jié)點(diǎn)時插入
	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)
	{
		// 小于往左走
		if (key < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		// 大于往右走
		else if (key > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			// 找到了
			// 1.左邊為空，把parent指向cur的右
			// 2.右邊為空，把parent指向cur的左
			// 3.左右都不為空，用右子樹的最左邊的節(jié)點(diǎn)（最小節(jié)點(diǎn)）的值替換要刪除的節(jié)點(diǎn)，然后轉(zhuǎn)換為用1的情況刪除該節(jié)點(diǎn)
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
					delete cur;
					break;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
						parent->_bf++;
					}
					else
					{
						parent->_right = cur->_right;
						parent->_bf--;
					}

				}

				if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent);
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
					delete cur;
					break;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
						parent->_bf++;
					}
					else
					{
						parent->_right = cur->_left;
						parent->_bf--;
					}
				}

				if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent);
				delete cur;
			}
			else
			{
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;// 先去右子樹
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;// 一種往左走
				}

				cur->_kv = rightMin->_kv;

				// 替代刪除
				// 刪除minNode  第一種情況：左節(jié)點(diǎn)為空
				if (rightMinParent->_left == rightMin)
				{
					rightMinParent->_left = rightMin->_right;
					rightMinParent->_bf++;
				}
				else
				{
					rightMinParent->_right = rightMin->_right;
					rightMinParent->_bf--;
				}

				if (rightMinParent->_bf != -1 && rightMinParent->_bf != 1) AfterEraseUpdateBf(rightMinParent);
				delete rightMin;
			}
			return true;
		}
	}
	return false;
}
void AfterEraseUpdateBf(Node* parent)
{
	if (parent == nullptr)
		return;
	
	Node* cur = parent;
	goto first;

	while (parent)
	{
		// 更新parent的平衡因子
		// cur在parent的左，parent->_bf++
		// cur在parent的右，parent->_bf--
		if (cur == parent->_left)
			parent->_bf++;
		else
			parent->_bf--;
		// bf 可能為 -2、-1、0、1、2
		// 如果平衡因子為0，說明更新之前，parent的bf為-1或1，現(xiàn)在刪掉了左節(jié)點(diǎn)或右節(jié)點(diǎn)，整體高度變了，對上層有影響
		// 如果平衡因子為-1或1，說明更新之前，parent的bf為0，現(xiàn)在刪掉了一個左節(jié)點(diǎn)或有節(jié)點(diǎn)，整體高度不變，對上層無影響
		// 如果平衡因子為-2或2，說明更新之前，parent的bf為-1或1，現(xiàn)在往左（右）節(jié)點(diǎn)補(bǔ)了左（右）節(jié)點(diǎn)，也就另一邊
		// 拉高了，樹不平衡了，需要用左旋轉(zhuǎn)或右旋轉(zhuǎn)來進(jìn)行調(diào)整
	first:
		if (parent->_bf == 0)
		{
			// 對上層有影響，迭代更新
			// 如果parent是根節(jié)點(diǎn)就結(jié)束
			if (parent->_parent == nullptr)
				break;
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			// 對上層無影響，退出
			break;
		}
		else
		{
			// 平衡樹出現(xiàn)了問題，需要調(diào)整
			// 1.右邊高，左旋轉(zhuǎn)調(diào)整
			if (parent->_bf == 2)
			{
				// 如果是一條直線==>左旋轉(zhuǎn)即可
				// 如果是一條折線==>右左旋轉(zhuǎn)
				if (parent->_right->_bf == 1)
				{
					RotateL(parent);
					cur = parent->_parent;
					parent = cur->_parent;
					continue;
				}
				else if (parent->_right->_bf == -1)// 調(diào)整后 p sL s  如果sL是1或-1可以退出 
				{
					Node* s = parent->_right;
					Node* sL = s->_left;
					RotateRL(parent);
					// 不平衡向上調(diào)整  注意：bug1（以為調(diào)整完就是1或-1了，其實(shí)這里不是，畫圖思考一下）
					//if (sL->_bf != 1 && sL->_bf != -1)
					{
						cur = sL;
						parent = cur->_parent;
						continue;
					}
				}
				else if (parent->_right->_bf == 0)// 旋轉(zhuǎn)后平衡因子要修改，畫圖感受 parent: 1 parent->_parent:- 1
				{
					RotateL(parent);
					parent->_bf = 1;
					parent->_parent->_bf = -1;
				}

			}
			// 2.左邊高，右旋轉(zhuǎn)調(diào)整
			else if (parent->_bf == -2)
			{
				// 如果是一條直線==>右旋轉(zhuǎn)即可
				// 如果是一條折線==>左右旋轉(zhuǎn)
				if (parent->_left->_bf == -1)
				{
					RotateR(parent);
					cur = parent->_parent;// bug2 cur要變成這個位置是因?yàn)檫x擇后父親的位置變了，畫圖
					parent = cur->_parent;
					continue;//parent不是-1或1就繼續(xù)
				}
				else if (parent->_left->_bf == 1)// 調(diào)整后 s sR p  如果sL是1或-1可以退出
				{
					Node* s = parent->_left;
					Node* sR = s->_right;
					RotateLR(parent);
					// 不平衡向上調(diào)整 為0時如果parent為根
					//if (sR->_bf != 1 && sR->_bf != -1)
					{
						cur = sR;
						parent = cur->_parent;
						continue;
					}
				}
				else if (parent->_left->_bf == 0)// 平衡因子要修改，畫圖感受 parent->_parent: 1 parent: -1 
				{
					RotateR(parent);
					parent->_parent->_bf = 1;
					parent->_bf = -1;
				}
			}

			// 調(diào)整后是平衡樹，bf為1或-1，不需要調(diào)整了
			break;
		}
	}
}

??AVL樹的測試代碼

下面是驗(yàn)證是否為AVL樹的代碼：

int _Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	return 1 + max(leftHeight, rightHeight);
}
bool _IsBalanceTree(Node* root)
{
	if (root == nullptr)
		return true;
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	return rightHeight - leftHeight == root->_bf
		&& abs(rightHeight - leftHeight) < 2
		&& _IsBalanceTree(root->_left)
		&& _IsBalanceTree(root->_right);
}

實(shí)例演示：

void TestAVLTree1()
{
	AVLTree<int, int> at;
	srand((size_t)time(nullptr));
	// int a[] = { 4,3,5,3,1,2,7 };
	// int a[] = { 1,2,3,4,5,6,7,8,9 };
	// int a[] = { 2,4,6,3,5,1,9,10,8,7 };
	// int a[] = { 4,2,3,5 };
	// int a[] = { 16,3,7,11,9,26,18,14,15 };
	// int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	// int* a = new int[10000];
	/*int i = 1;
	for (auto& e : a)
	{
		e = i++;
	}*/
	vector<int> a;
	for (size_t i = 0; i < 13; ++i)
	{
		// a.push_back(rand());
		a.push_back(13);
	}
	for (auto e : a)
	{
		int begin = clock();
		pair<AVLTreeNode<int, int>*, bool> ret = at.Insert(make_pair(e, e));
		int end = clock();
		// cout << ret.first->_kv.second << endl;
		// cout << ret.first->_kv.second << ":" << ret.second << endl;
		
		cout << "插入 " << e << " 后變化 --> Height: " << at.Height() << " 是否為AVLTree：" << at.IsBalanceTree();
		cout << " 用時: " << end - begin << "ms" << endl;

	}

	cout << "------------------------------------------------------" << endl;
	// at.InOrder();
	for (auto e : a)
	{
		if (e == 11478)
		{
			int a = 0;
		}
		int begin = clock();
		at.Erase(e);
		int end = clock();

		cout << "刪除 " << e << " 后變化 --> Height: " << at.Height() << " 是否為AVLTree：" << at.IsBalanceTree();
		cout << " 用時: " << end - begin << "ms" << endl;
	}

	at.InOrder();
}

代碼運(yùn)行結(jié)果如下：