C++——AVL树

作者：几冬雪来

时间：2023年11月30日

内容：C++板块AVL树讲解

前言：

AVL树与搜索二叉树之间的关系：

AVL树概念：

插入结点：

平衡因子：

旋转：

双旋：

验证AVL树：

代码：

结尾：

前言：

在上一篇博客中我们完成了对C++中异常的讲解，但异常在C++中并不是一个重点知识，而在更前面的二叉搜索树中我们有提到过，二叉搜索树是一个非常重要的知识板块，它作为基础会引出之后要学习AVL树与红黑树，而今天我们就来讲解二者其中的一棵树——AVL树。

AVL树与搜索二叉树之间的关系：

在了解AVL树之前，我们先来回顾一下之前说过的AVL树和红黑树是以二叉搜索树为基础改良出来的树。

那么AVL树和红黑树是怎么对二叉搜索树进行改良的？

在二叉搜索树博客处我们就有说过二叉搜索树的一种特殊情况，就是上图这种二叉搜索树一边过长，另一边只有一个值的这种极端场景。

在这种极端场景下这棵二叉搜索树就会退化成类似链表的结果。

而AVL树和红黑树就是为了解决这种情况诞生的，只不过二者解决这个问题所用的方法有些类似，但是其性质天差地别。

因此AVL树与红黑树又被称为二叉平衡搜索树。

AVL树概念：

了解完了AVL树之后，接下来就来讲解一下AVL树的概念。

如果二叉搜索树插入一个新结点后，要是能保证每个结点的左右子树高度差的绝对值不超过1。这就是AVL树的做法。

而做到控制这棵树的方法有很多。

在这里控制树的方法就是引入了平衡因子，但是这里的平衡因子并不是必须的。

而这个地方每个结点都有平衡因子，它的平衡因子有一套计算公式。

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

而这里的AVL树也是成功的控制了树的效率，它的增删查改时间复杂度为O(logN)。

这个地方满二叉树结点的个数为2^h-1，转换为AVL树的话，这里的-1就要换为-x。与此同时我们也可以计算出x的范围是多少。

插入结点：

在书写完了AVL树的基础框架之后，要想让AVL可以去控制它的平衡，在这个基础上需要我们先进行结点的插入操作。

在书写完了它的插入代码之后，接下来就是要对它的平衡因子进行修改了，那要怎么去修改该结点的平衡因子呢？

平衡因子：

在书写完了二叉搜索树的代码之后，接下来就需要去控制它的平衡。

在这个地方地方有一颗AVL树，要在AVL树插入一个结点，如果这个结点不平衡应该怎么办？又怎么确定它就是不平衡的呢？

而为了解决这些问题，就需要对其进行假设。

这里假设出三种新结点的插入方法，然后依次对它们进行分析。

首先这个地方可以确定这个结点cur与它的父结点parent，这里插入的方法也有两种，一种是插入在parent的左边，另一种是插在parent的右边。

那么它的平衡因子会发生怎么样的变化？

类似上图，类似情况一：如果父结点原先就有一个右结点，再插入一个结点到父结点左边的话，这个地方父结点的平衡因子就会从1变为0。

情况二：原parent左右结点都为空，在这种情况下插入左结点父结点的平衡因子会变为-1，如果插入右结点的话，它的平衡因子会变为1。

但是要注意插入的结点只会影响它的父结点与祖先的平衡因子，它其他方向是不会被影响的。

接下来就是其增加结点对父结点或者祖宗结点平衡因子的影响。

在这里如果父结点在增加结点前自己原先已有左结点或者右结点，这里向它另一边增加结点崩坏改变高度，只会影响到父结点。

类似左边的图不会影响到祖宗，但是右边的图AVL树的高度发生变化，会影响到祖宗。

这里还需要知道一个点当parent更新等于0的时候，这里就说明parent所在的子树高度不变，不会影响到祖先，因此没有必要向上更新。

相反如果更新后平衡因子等于1或者-1的话，说明它的子树高度变化，要向上进行更新。要是等于2或者-2的话，该子树的高度变化且不平衡，这里这棵树就出问题了不能继续向上更新。

这里平衡因子的作用就是用来判断该AVL树是否平衡没有出现问题。

既然知道了这里的平衡因子的使用方法，那么下来就要在代码中去实现它。

首先要记录父结点的平衡因子是0或者1和-1等值，这个地方就需要定义一个整形且将这个整形初始化为0。

这里首先要知道什么情况下更新要停止，一种情况就是parent的平衡因子为0的时候更新结束，另一种是更新到parent的平衡因子为2或-2的情况，该树出问题停止更新，最后一种特殊情况那就是当更新到根节点的时候，这里也是要停止的。

然后接下来就要书写更新平衡因子的代码。

因为平衡因子的更新有可能更新到根结点，因此这个地方使用parent来作为循环的条件。

接下来就是对_bf的++与--，如果插入的结点为parent的左边，那么_bf就进行--操作，反之在右边进行++操作。如果_bf为0则证明不用再更新了，这里就break跳出循环。

然后就判断_bf为-1与1和2与-2的情况，如果平衡因子为-1或1的话cur与parent都向上移动，如果平衡因子值为2或者-2那就需要处理这种情况，最后为了防止代码出错导致_bf会变为其他值，else语句中药进行断言操作。

旋转：

接下来就是平衡因子的处理了，这里如果某个结点的平衡因子为2，那就说明它的左子树高度比右子树少2。

反正为-2的话则是右子树高度比左子树少2。

如果发生什么两种情况的其中一种的话，那么这里就要对较高子树的那边做一个旋转的操作。

但是在旋转时需要注意几个问题。

1.旋转后保持它是搜索树

2.让这棵树变为平衡树且降低这棵子树的高度

再者就是旋转的原理图。

这里就是旋转的原理。

如同上图，根结点或者某棵区域树的平衡因子为2，这个时候就需要用到旋转。

而旋转的核心操作就是把cur的左给parent的右，再让parent给cur的左。这样子做可以让这棵树依旧保持是搜索树，同时保证了平衡因子不为2或者-2，也降低了树的高度。

如果根结点为2那么这个地方就需要进行左单旋，相反为-2则是进行右单旋，这样的结果都能保证根结点的平衡因子为0。

这棵树旋转后相比插入之前高度发生了变化。

接下来就是旋转处代码的书写。

这里就是旋转的具体操作，输入核心代码看似只有两句，但是真正写的时候需要对其进行更改的地方有很多。

同时旋转的时候要注意的东西也有很多，如果稍微漏了一点则可能会导致旋转代码的失败。

这里就是旋转代码的原理图。

首先给两个结点存cur的位置与cur->left的位置，再给一个结点存parent的父结点。

接下来将curleft给给parent的right完成第一步连接，接下来处理cur左子树为空的情况，然后将原parent的父结点指向cur，然后就是判断原parent结点的parent是空函数某个子树的左右结点后将其连接好修改。

最后就是对平衡因子的修改，这里就是AVL树它的左单旋。

而既然有左单旋，那么同样的AVL树也右单旋，对比左单旋，右单旋的操作就是将左单旋的代码进行一定的修改。

这个地方就是右单旋的代码书写，它和左单旋的区别在于一个是指向cur的left，另外一个是指向cur的right。

但是即使是这样，它们的实现原理还是相同的，这里的内容就不再去过多的赘述了。

而且在讲解完了左右单旋之后，接下来就要讲到AVL树的左右双旋。

双旋：

在AVL树中不仅有单旋操作，同时还有双旋的操作。

这里地方单旋有一个特点，那就是一定是单纯的右边高或者左边高。

那么为什么只能单纯的一边高，而不是parent结点是右边高，来到cur结点变成左边高呢？这里就需要一张图来带我们对其进行了解。

这里就是只能单纯的一边高的原因，在上边的那棵树就是单纯的右边高，这个地方cur的左给parent的右后再让cur的左指向parent，这样左并不会破坏这棵树的平衡。

但是下边这棵树并不是单纯的一边高，在parent那里是右子树高，但是到cur处变成了左子树高。在这种情况下让cur的左给parent的右，再让cur的左指向parent，这样子做还是会使得cur的平衡因子为2。

而为了解决这个问题就需要使用到双旋的操作。

这里就是双旋操作的概念图。

这里在结点值为2的左子树插入一个新结点，要让这棵树变成平衡树的话，这个地方先要以3结点为旋转点进行一次右单旋，再然后以1为旋转点再继续一次左单旋，这里就能成功的解决这个问题了。

而要进行的是单旋还是双旋的基本条件也是很好区分的。

这里如果满足parent的值是2，cur的值为-1。又或者parent的值是-2，cur的值为1，这两种情况都达到了使用双旋的条件。

在知道条件之后，接下来就需要书写代码了。

而且这里的双旋的代码就可以套用上面两个单旋的代码，如果parent为2，cur为-1，那么就要进行双旋操作。

首先就是将parent的右为旋转点进行一次右单旋，再以parent为旋转点进行一次左单旋，这样就能达到想要的效果。

而旋转完了之后，下来就是对_bf的修改了，只不过在。

这里要注意的点是，如上图在值为60的结点左右插入结点都能用双旋使它变为AVL树，但是插入的是左右哪个结点却会影响到树的造型与_bf的值。

如图，如果插入在60结点的左边，最后的结果是值为90的结点平衡因子为1，值为30与60结点的平衡因子都为0。

但是插入在60结点的右边，最后是60与90结点的平衡因子为0，30结点的平衡因子为-1，这就是需要注意的点。

如果值为60的结点平衡因子为0，那就说明这个结点是新增结点，在双旋之后3者的平衡因子都为0。

同样的在这里值为60结点的子树的下一个结点后插入新结点，最终也使得这棵树的parent与它的左右两个结点的平衡因子不同。

在上边有提及值为60的结点平衡因子是0的情况我们可以确定60是这个地方的新增结点。

但是这个地方值为60的结点必须保证它自己是新增结点才行，如果插入结点使得值为60的结点拥有左右子树并且它的平衡因子为0的话，这个地方结点会在更新到60处停止，并不会继续向上更新。

因此我们也可以得出一个结论，如上图平衡因子的更新关键看的是值为60的这个结点。

再接下来就是对其代码的书写，这里我们先写入的是parent的右边，也就是parent为正数时候的处理方式。

首先要确定cur与cur的left的位置，再用_bf记录没旋转前cur的左left的平衡因子。

旋转完了之后判断平衡因子为0，1与-1三种情况对应的curleft，cur与parent各种的平衡因子是什么，这样就能成功的实现双旋的操作。

剩下的再把parent的左边双旋代码也写出来即可。

验证AVL树：

在上边我们完成了结点的平衡因子的修改，并且在不同情况下平衡因子对针对不同情况进行修改，但在并不意味着这里的平衡因子就没有问题了。

这里依旧会存在插入的值引发平衡因子发生异常的问题。

因此就需要来验证这里的AVL树是否正常。

像这个地方的IsBlance就是来验证AVL树的。

首先如果根结点为空的话就直接返回true，如果不是的话，接下来就是从根结点判断它的左右子树的高度，在判断根结点左右子树的函数中再走判断根结点的左右结点对应的左右子树，用递归的形式。

在然后就是判断如果它的左子树的高度-右子树的高度不等于该结点的_bf的话，这里就对代码进行报错。

要是没问题的话就返回true。

就像上图一样，在.cpp文件中我们创建了一个数组并且使用map的make_pair将组数组进行了排序和平衡因子的修改。

但是在打印insert的值和它们对应的平衡因子的时候我们可以看见，在插入结点11的时候树发生的错误，而且这个错误导致了原先平衡因子正常值为7的结点，它的平衡因子出错了。

然后就是通过条件断点和监视窗口解决这个问题。

在这里我们在值为11的结点处设置一个条件断点，接下来就是监视窗口的调试和平衡因子产生的变化。

这个地方最终可以确定在右旋处有一点代码没有添加。

这就是AVL树的验证方法。

代码：

AVLTree.cpp

#include"AVLTree.h"

int main()
{
	int a[] = { 16,3,7,11,9,26,18,14,15 };
	AVLTree<int, int> t;
	for (auto e : a)
	{
		if (e == 11)
		{
			int x = 0;
		}

		t.Insert(make_pair(e, e));
		cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	return 0;
}

AVLTree.h

#pragma once

#include <iostream>
#include <assert.h>
using namespace std;

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),
		_right(nullptr),
		_left(nullptr),
		_parent(nullptr),
		_bf(0)
	{

	}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
	Node* parent;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		while (cur)
		{
			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->_left)
			{
				parent->_bf--;
			}

			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续更新
				cur = parent;
				parent = parent->_parent;
			}
			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 if(parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int bf = curleft->_bf; 

		RotateR(parent->_right);
		RotateL(parent);
		if (bf == 0)
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			cur->_bf = 1;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;

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

		if (bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
	}

	void RotateL(Node* parent)  
	{ 
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppnode = parent->_parent;

		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}
		cur->_left = parent;
		parent->_parent = cur;

		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}

		parent->_bf = cur->_bf = 0; 
	}

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* ppnode = parent->_parent;

		parent->_left = cur->_right;
		if (curright)
		{
			curright->_parent = parent;
		}
		cur->_right = parent;
		parent->_parent = cur;
		if (ppnode == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
		parent->_bf = cur->_bf = 0;
	}

	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHight = Height(root->_left);
		int rightHight = Height(root->_right);

		return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
	}

	bool IsBalance()
	{
		return IsBlance(_root);
	}

	bool IsBlance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHight = Height(root->_left);
		int rightHight = Height(root->_right);

		if (rightHight - leftHight != root->_bf)
		{
			cout << "平衡因子出错:" << root->_kv.first << "->" << root->_bf << endl;
			return false;
		}

		return abs(rightHight - leftHight) < 2 && IsBlance(root->_left) && IsBlance(root->_right);
	}

private:
	Node* _root = nullptr;
};

结尾：

到这里我们的AVL树就大概的讲解完毕了，在AVL树里面还会用到删除和查找操作，查找操作十分容易，但是AVL的删除操作相比插入操作有些繁琐。这里不讲解的原因是因为删除操作本质和插入操作没什么区别，只是平衡因子改动变麻烦了，实际上无论是去外应聘或者找工作什么的，都极少要求手撕。而在讲解完了AVL树之后，后面就是要讲另一棵树——红黑树，最后希望这篇博客能给各位带来帮助。