[C++知识库]【初阶与进阶C++详解】第十六篇：AVL树-平衡搜索二叉树（定义+插入+旋转+验证）

🏆个人主页：企鹅不叫的博客

? 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

?? 博主码云gitee链接：代码仓库地址

?若有帮助可以【关注+点赞+收藏】，大家一起进步！

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector(vector接口介绍+vector模拟实现+vector迭代器区间构造/拷贝构造/赋值)

【初阶与进阶C++详解】第十篇：list(list接口介绍和使用+list模拟实现+反向迭代器和迭代器适配)

【初阶与进阶C++详解】第十一篇：stack+queue+priority_queue+deque（仿函数）

【初阶与进阶C++详解】第十二篇：模板进阶(函数模板特化+类模板特化+模板分离编译)

【初阶与进阶C++详解】第十三篇：继承(菱形继承+菱形虚拟继承+组合)

【初阶与进阶C++详解】第十四篇：多态（虚函数+重写（覆盖）+抽象类+单继承和多继承）

【初阶与进阶C++详解】第十五篇：二叉树搜索树（操作+实现+应用KVL+性能+习题）

💎一、AVL树概念

二叉搜索树虽可以缩短查找的效率(logN)，但如果数据有序或接近有序二叉搜索树将退化为单支树(On)，查找元素相当于在顺序表中搜索元素，效率低下。

平衡树也是搜索二叉树，其引入了一个平衡因子的概念，用于控制搜索二叉树的平衡。它会保证左右子树的高度之差（绝对值）不超过1。当新插入节点导致高度之差超过1时，便会触发旋转，使得树的高度降低，稳定了二叉搜索树效率。

• 它的左右子树都是AVL树

• 左右子树高度之差的绝对值（也叫平衡因子）不超过1

• 平衡因子= 右子树高度 - 左子树高度

💎二、AVL树节点的定义

这里节点是一个三叉链，里面存放了元素的数据和该节点此时的平衡因子。

• 左右子树高度相同 0
• 左子树高于右子树 -1
• 右子树高于左子树 1

template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;//键值对
	AVLTreeNode<K, V>* _left;//左子树
	AVLTreeNode<K, V>* _right;//右子树
	AVLTreeNode<K, V>* _parent;//父节点

	// 右子树-左子树的高度差
	int _bf;  // 平衡因子

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

💎三、AVL树插入

🏆1.平衡因子的调节

AVL需要控制高度，所以每次插入我们都需要更新判断树节点的平衡因子是否符合要求

思路：

• 如果是空树，给root new一个新节点

• 根据二叉搜索树的规则（左小右大规则）来找到新节点应该插入的位置，进行插入

• 插入之后，需要向上更新平衡因子（可能包括多个祖先），如果该插入节点在父节点的右边，平衡因子+1，如果在该节点的左边，平衡因子-1。

• parent更新后的平衡因子为1或-1，则说明在parent的右边或者左边新增了结点，从而影响了parent的父亲结点所以要继续往上更新平衡因子。

  

• parent更新后的平衡因子为0，说明插入前父亲的平衡因子为1或-1经过++或- -变成0的，说明新增结点在parent矮的一侧使得parent的左右子树一样高，不会影响parent的父亲结点，就不用往上更新平衡因子。

  

• 如果平衡因子的绝对值等于2，已经不满足AVL树，说明当前就需要旋转

  

框架代码：

bool Insert(const pair<K, V>& kv)
	{
		// 1、搜索树的规则插入
		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
		//判断为空树
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_bf = 0;
			return true;
		}
		//同步kvl操作
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//判断key的插入位置
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		//找到位置后插入节点
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		//插入之后需要向上更新平衡因子
		while (parent) // 最远要更新根
		{
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			//更新了之后，需要判断是否继续更新，还是需要旋转
			// 原来是1 or -1  变成 0  插入节点填上矮的那边
			if (parent->_bf == 0)
			{
				// 高度不变，更新结束
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
				// 原来是0  变成 1 或 -1  插入节点导致一边变高了
			{
				// 子树的高度变了，继续更新祖先
				cur = cur->_parent;//向上更新
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
				// 原来是-1 or 1  变成 2 或 -2  插入节点导致本来高一边又变高了
			{
				// 子树不平衡，旋转
        		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);
				}
				
				break;
			}
			else
			{
				// 插入之前AVL就存在不平衡子树
				assert(false);
			}
		}

		return true;
	}

💎四、AVL树旋转（重点）

1.1左单旋（新插入的节点在右子树的右侧）

步骤：让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0。

代码部分：

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的父节点的位置，然后把parent作为subR的左边 
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		// 4.parent的父指针指向subR
		parent->_parent = subR;
		// 5.如果ppNode为空==>说明subR现在是根节点，就让subR的父指针指向nullptr
		//不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR
		if (parent == _root)
		{
			// 更新根节点
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			// 判断parent是ppNode的左还是右
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}

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

1.2右单旋（新节点插入到较高左子树的左侧）

步骤： 让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0

代码部分：

void RotateR(Node* parent)
{
	//让不平衡的结点parent的左子树变为其原本左子树subL的右节点subLR
	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的父节点的位置，然后把parent作为subL的右边
	Node* ppNode = parent->_parent;
	subL->_right = parent;
	// 4.parent的父指针指向subL
	parent->_parent = subL;
	// 5.如果parent为根节点，则让subL成为新的根节点
	if (parent == _root)
	{
		// 更新根节点
		_root = subL;
		_root->_parent = nullptr;
	}
	//如果不是根节点，则改变subL与其祖父节点的指向关系
	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;
}

两种单旋的情况：

? 左单旋，prev平衡因子为2,subR平衡因子为1，需要左单旋

右单旋，prev平衡因子为-2,subL平衡因子为-1，需要右单旋

总结：当父节点的平衡因子的绝对值超过1，其左/右边节点的平衡因子为1且和父节点平衡因子的正负相同时，需要向另外一个方向进行单旋

//插入函数的旋转部分
else if (parent->_bf == 2 || parent->_bf == -2)
{
    if (parent->_bf == 2 && cur->_bf == 1)
    {
        RotateL(parent);
    }
    else if (parent->_bf == -2 && cur->_bf == -1)
    {
        RotateR(parent);
    }
    else
    {
        //左右双旋，右左双旋
    }
    break;
}

1.3右左双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

步骤：先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子

如果subRL的平衡因子为0，就将它们依次改为0，0, 0；本身就是新增节点
如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；

如果subRL的平衡因子为-1，就将它们依次改为0，0, 1

// 右左旋转==>parent->_bf==2&&cur->_bf==-1
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	// 保留subRL的平衡因子的值，方便知道新插入的节点是在subRL的左子树还是右子树,调节旋转完后的平衡因子
	int bf = subRL->_bf;
	//先右单旋将折线结构转换为直线结构
	RotateR(parent->_right);
	//然后再左单旋
	RotateL(parent);
	// 从左到右 parent subRL subR
	if (bf == 0)// subRL的左子树  bf: 0 0 0
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == 1)// subRL的右子树 bf: -1 0 0
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)// subRL的左子树  bf: 0 0 1
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else
	{
		// subLR->_bf旋转前就有问题
		assert(false);
	}
}

1.4左右双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

步骤：先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子

如果subLR的平衡因子为0，就将它们依次改为0，0, 0；
如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；

如果subLR的平衡因子为-1，就将它们依次改为0，0, 1

// 左右旋转==>parent->_bf==-2&&cur->_bf==1
void RotateLR(Node* parent)
{ 
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的节点是在subLR的左子树还是右子树,调节旋转完后的平衡因子
	//先左单旋将折线结构转换为直线结构
	RotateL(parent->_left);
	//然后再右单旋
	RotateR(parent);
	// 从左到右 parent subRL subR
	if (bf == 0)// subRL的左子树  bf: 0 0 0
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1)// subLR的右子树 bf: -1 0 0
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == -1)// subLR的左子树  bf: 0 0 1
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		// subLR->_bf旋转前就有问题
		assert(false);
	}
}

💎五、AVL树验证

AVL树有两点需要验证，通过高度判断，子树两边高度是否平衡，根据二叉搜索树的特性，判断平衡因子是否符合

//计算高度
int _Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int lh = _Height(root->_left);
	int rh = _Height(root->_right);
	//如果左子树高于右子树，就返回左子树+1（根）
	return lh > rh ? lh + 1 : rh + 1;
}
//判断是否为平衡二叉树
bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树
	if (nullptr == root)
		return true;

	// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;

	// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
	// pRoot平衡因子的绝对值超过1，则违反规则，则一定不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "节点平衡因子异常" << endl;
		return false;
	}

	if (diff != root->_bf)
	{
		cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
		return false;
	}

	// pRoot的左和右如果都是AVL树，则该树一定是AVL树
	return _IsBalanceTree(root->_left)
		&& _IsBalanceTree(root->_right);
}

实例演示：

void TestAVLTree2()
{
	const size_t N = 1024*1024;
	vector<int> v;
	v.reserve(N);
	srand(time(0));//使用随机数
	for (size_t i = 0; i < N; ++i)
	{
		v.push_back(rand());
		//v.push_back(i);
	}

	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}

	cout << "是否平衡?" << t.IsBalanceTree() << endl;
	cout << "高度:" << t.Height() << endl;
}

💎六、AVL树删除(了解)

思路：

1.按照二叉搜索树的规则删除

2.更新平衡因子，并且进行旋转来调整（最坏情况下可能会一直调整到根节点）。

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

	// 有节点时插入
	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.左右都不为空，用右子树的最左边的节点（最小节点）的值替换要删除的节点，然后转换为用1的情况删除该节点
			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  第一种情况：左节点为空
				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，现在删掉了左节点或右节点，整体高度变了，对上层有影响
		// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在删掉了一个左节点或有节点，整体高度不变，对上层无影响
		// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就另一边
		// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整
	first:
		if (parent->_bf == 0)
		{
			// 对上层有影响，迭代更新
			// 如果parent是根节点就结束
			if (parent->_parent == nullptr)
				break;
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			// 对上层无影响，退出
			break;
		}
		else
		{
			// 平衡树出现了问题，需要调整
			// 1.右边高，左旋转调整
			if (parent->_bf == 2)
			{
				// 如果是一条直线==>左旋转即可
				// 如果是一条折线==>右左旋转
				if (parent->_right->_bf == 1)
				{
					RotateL(parent);
					cur = parent->_parent;
					parent = cur->_parent;
					continue;
				}
				else if (parent->_right->_bf == -1)// 调整后 p sL s  如果sL是1或-1可以退出 
				{
					Node* s = parent->_right;
					Node* sL = s->_left;
					RotateRL(parent);
					// 不平衡向上调整  注意：bug1（以为调整完就是1或-1了，其实这里不是，画图思考一下）
					//if (sL->_bf != 1 && sL->_bf != -1)
					{
						cur = sL;
						parent = cur->_parent;
						continue;
					}
				}
				else if (parent->_right->_bf == 0)// 旋转后平衡因子要修改，画图感受 parent: 1 parent->_parent:- 1
				{
					RotateL(parent);
					parent->_bf = 1;
					parent->_parent->_bf = -1;
				}

			}
			// 2.左边高，右旋转调整
			else if (parent->_bf == -2)
			{
				// 如果是一条直线==>右旋转即可
				// 如果是一条折线==>左右旋转
				if (parent->_left->_bf == -1)
				{
					RotateR(parent);
					cur = parent->_parent;// bug2 cur要变成这个位置是因为选择后父亲的位置变了，画图
					parent = cur->_parent;
					continue;//parent不是-1或1就继续
				}
				else if (parent->_left->_bf == 1)// 调整后 s sR p  如果sL是1或-1可以退出
				{
					Node* s = parent->_left;
					Node* sR = s->_right;
					RotateLR(parent);
					// 不平衡向上调整 为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;
				}
			}

			// 调整后是平衡树，bf为1或-1，不需要调整了
			break;
		}
	}
}

💎七、AVL树查找

和KVL树一样

//因为kvl树我们需要修改value，所以返回节点的指针
Node* _FindR(Node* root, const K& key)
{
	if (root == nullptr)
		return nullptr;

	if (root->_kv.first < key)
	{
		return _FindR(root->_right, key);
	}
	else if (root->_kv.first > key)
	{
		return _FindR(root->_left, key);
	}
	else
	{
		return root;//返回节点的指针
	}
}

💎八、AVL树性能

1. AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度logN
2. 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置