🐱作者：一只大喵咪1201
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

我们知道，二叉搜索树的搜索效率非常高，平均时间复杂度是O(log₂N)，但是当数据原本就有序时，插入二叉树中就会形成单支结构，此时搜索的时间复杂度就是O(N)。

为了避免二叉搜索树的这个缺陷，在它的基础上提出了AVL树(高度平衡二叉搜索树)和红黑树。

🌲AVL树

• AVL树：当向二叉搜索树中插入新节点后，要保证每个节点的左右子树高度差的绝对值不超过1。

根据高度差不超过1的规制，可以避免二叉搜索树出现单支的情况，使其更加接近完全二叉树，保证搜索效率是O(log₂N)。

AVL树的性质：

• 它的左右子树都是AVL树。
• 左右子树的高度差(简称平衡因子)的绝对值不超过1。

注意： 一颗空树或者只有一个根的树也属于AVL树。

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

• a和b两种情况下根节点的平衡因子都是是0，因为此时左右子树高度相同。
• c情况下根节点的平衡因子是-1，因为此时左子树比右子树多一个节点。
• d情况下根节点的平衡因子是1，因为此时左子树比右子树少一个节点。

在AVL树中，每个节点的平衡因子只能是1，0，-1三种情况，一旦不是这三种就需要进行调整，保证平衡因子不会出现第四种情况。

插入新节点10以后，导致多个节点的平衡因子发生了变化：

• 节点9的平衡因子从0变成了1，说明新节点插入到了节点9的右边。
• 节点8的平衡因子从1变成了2，因为新节点插入到了节点8的右子树中。
• 节点8的平衡因子不再是1，0，-1三个数中的一个，所以就需要进行调整。

至于怎么调整一会儿本喵再详细讲解。

🌴AVL树的插入

破坏二叉搜索树平衡的操作主要就是插入，所以我们主要来看看AVL树是如何插入的，是如何在插入过程中保证平衡的。

节点的定义：

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

	//节点的构造函数
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

• 节点中的值是一个键值对。
• 是一个三叉链的结构，不仅有左右子节点的指针，还有父节点的指针。
• 平衡因子用来衡量该节点的状态，默认情况下是0。

AVL树的定义：

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		//............
	}
protected:
	Node* _root = nullptr;//缺省值
};

和二叉搜索树一样，AVL树种也是只有一个成员变量根，给根一个缺省值，默认情况下它是空树。

插入：

AVL树的插入和二叉搜索树的插入在前半部分一模一样，大于根的插入到右边，小于根的插入到左边，区别在于AVL树插入后的调整。

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		//空树时直接插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//更新平衡因子，进行调整
		break;
	}
}

上面代码是将节点插入到二叉搜索树中的代码，不再解释，最重要的是后面的更新平衡因子，这才是AVL树的重点。

🌴AVL树的旋转

平衡因子不是-1/0/1的节点进行调整，调整的方式是旋转，下面本喵来详细介绍一下如何旋转。

每一个子树都是一个AVL树，所以子树的平衡因子发生变化，势必会对其父节点以及祖父节点等祖宗节点有影响，可能会引发一系列的调整。

当子树更新完毕后，是否继续向上更新平衡因子的依据是子树的高度是否发生变化：

1. parent->_bf == 0，说明之前是-1或者1，说明插入之前，该节点的左右子树一边高一边低，此次插入填平了，但是高度没有发生变化，所以不用继续向上更新。
2. parent->_bf == 1 或者 parent->_bf == -1，说明之前是，两边一样高，此次插入导致一边高于另外一边，高度发生了变化，所以需要继续向上更新。
3. parent->_bf == 2 或者 parent->_bf == -1，说明之前是1或者-1，本来就左右不平衡，此次插入导致更加不平衡，违反了规则，需要进行旋转处理。

更新平衡因子的代码：

		//更新平衡因子，进行调整
		while (parent)//最差更新到根
		{
			//左边新插入，平衡因子减一
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			//右边新插入，平衡因子加一
			else
			{
				parent->_bf++;
			}

			//跟新后的平衡因子是0，说明高度没有变化，不用继续更新
			if (parent->_bf == 0)
			{
				break;
			}
			//新插入节点，高度发生了变化，向上更新
			else if(parent->_bf==1 || parent->_bf == -1)
			{
				//向上更新父节点
				cur = parent;
				parent = parent->_parent;
			}
			//高度差超出1，进行旋转
			else if(parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转
				//更新旋转后的平衡因子
			}
			//前面出错，正常情况下不会进入这里
			else
			{
				//出错直接退出
				assert(false);
			}

旋转的作用：

1. 让这颗子树左右高度差不超过1。
2. 旋转过程中继续保持它是搜索树。
3. 更新旋转节点和其孩子节点的平衡因子。
4. 让这颗子树的高度跟插入之前保持一直。

左单旋

• 插入新节点以后，右子树的高度发生了变化，最终变成了2，需要进行旋转。

旋转过程：

• 30变成60的左子节点，60变成根节点。
• 30和60的平衡因子都变成了0。

在上图的基础上，左右子树同时增加一层节点，如下图：

• 插入新节点后，右子树高度发生了变化，最后变成了2，需要进行旋转。

旋转过程：

• 40变成30的右子节点
• 30变成60的左子节点
• 60变成根节点
• 30和60的平衡因子变成0。

在上图基础上再增加一层节点，如下图：

此时30的左子树有两层，右子树有3层。

• 左子树的两层有三种情况，如黑色箭头指向的，这里使用红色框代表两层子树。
• 右子树中要想让新增节点引起旋转，新增的两层节点必须如上图所示。
• 新插入的节点可以插入的位置有两个，如上图实线圈和虚线圈所示。

旋转过程：

• 60的左子树变成30的右子树。
• 30变成60的左子树。
• 60变成根。
• 30和60的平衡因子变成0。

从新增两层开始就有多种情况了，当层数越多，情况就越多，所以使用抽象图来代表有多层子树的情况：

a，b，c都是高度为h的AVL子树。

• 在子树c处插入新节点，此时c子树高度变成了h+1，更新平衡因子，最终导致30的平衡因子变成了2，需要进行旋转。

旋转过程：

• 60的左子树变成30的右子树。
• 30变成60的左子树。
• 60变成根。
• 30和60的平衡因子变成0。

通过上面具象图和抽象图插入节点后的旋转，我们可以总结出一些规律：

• 插入新的节点后，平衡因子发生了变化的3个节点在同一条直线上，平衡因子为2的节点在最上边，其余两个依次排在右下方。

//用左单旋的代码条件
parent->_bf == 2 && cur->_bf == 1;

旋转过程：

• subRL成为parent的右子树。
• parent成为subR的左子树。
• subR成为根。
• parent个subR的平衡因子变成0。

上面所述的旋转就左旋。形象的理解就是将左边高的一端按下去。

将左单旋的具体实现封装在一个函数中，在更新平衡因子的过程中调用左单旋来调整结构。

右单旋

右单旋的结构只是和左单旋的结构方向不一样，其他都一样，本喵就不再画具象图推演了，直接上抽象图：

a，b，c都是高度为h的AVL子树。

• 在子树a处插入新节点，此时a子树高度变成了h+1，更新平衡因子，最终导致60的平衡因子变成了-2，需要进行旋转。

旋转过程：

• 30的右子树成员60的左子树。
• 60成为30的右子树。
• 30成为根。
• 60和30的平衡因子变成0。

右单旋的规律：

• 插入新的节点后，平衡因子发生了变化的3个节点在同一条直线上，平衡因子为-2的节点在最上边，其余两个依次排在左下方。

//用右单旋的代码条件
parent->_bf == -2 && cur->_bf == -1;

旋转过程：

• subLR成为parent的左子树。
• parent成为subL的右子树。
• subL成为根。
• parent和subL的平衡因子成为0。

形象的理解就是右边高，将右边按下去。

右单旋实现代码：

//右旋实现
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			//不为空才会链接
			subLR->_parent = parent;
		}
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		//旋转后与旧树的链接
		if (ppNode == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		//新根是子树
		else
		{
			//在左子树插入的
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			//在右子树插入的
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		//更新平衡因子
		parent->_bf = subL->_bf = 0;
	}

只是逻辑和左单旋相反，其他一样，不再进行详细讲解。

左右双旋

• 插入新节点后，左子树的高度发生变化，根节点90的平衡因子最终变成-2。

旋转过程：

• 左子树先进行左单旋：

• 30变成40的左子树。
• 40变成根节点。

• 再整体进行右单旋：

• 90变成40的右子树。
• 40变成根节点。

• 90和40的平衡因子变成0。

在上图基础上各个子树再增加一层节点：

插入的节点为红色圈，可插入的位置有两个。

• 插入新的节点后，左子树的高度发生了变化，根节点90的平衡因子变成了-2。

旋转过程：

• 先进行左单旋：

• 50的左子树变成30的右子树(图中左子树为空，所以不用管)。
• 30变成50的左子树。
• 50变成子树的根。

• 再进行右单旋：

• 50的右子树变成90的左子树。
• 90变成50的右子树。
• 50变成根。

• 90的平衡因子变成0，30的平衡因子变成-1，50的平衡因子变成0。

在上图基础上再增加一层节点：

相对于最开始来说一共增加了两层，红色框表示两层，这两层右三种情况，如黑色简单所指。

• 插入新节点后，左子树高度发生了变化，根节点90的平衡因子变成-2。

旋转过程：

• 先进行左单旋：

• 50的左子树变成30的右子树。
• 30变成50的左子树。
• 50变成子树的根。

• 再进行右单旋：

• 50的右子树变成90的左子树。
• 90变成50的右子树。
• 50成为根。

• 30的平衡因子变成-1，90和50的平衡因子变成0。

将上面具象图画成抽象图：

h表示子树的高度，紫色框表示插入的节点。

• 插入新节点后，左子树的高度发生变化，根节点90的平衡因子变成-2。

//用左右双旋的代码条件
parent->_bf == -2 && cur->_bf == 1;

旋转过程：

• 先进行左单旋：

• 60的左子树变成30的右子树。
• 30变成60的左子树。
• 60成为子树的根。

• 再进行右单旋：

• 60的右子树成为90的左子树。
• 90成为60的右子树。
• 60成为根。

• 60的平衡因子变成0，90的平衡因子变成1，30的平衡因子变成0。

左右双旋规律：

• 插入新的节点后，平衡因子发生了变化的3个节点形成一个左边突出的拐，平衡因子为-2的节点在最上边，左下方是平衡因子为1的节点，最后一个在1节点的右下方，该节点的平衡因子可能是-1也可能是1。

平衡因子更新：

双旋中，旋转很好实现，直接复用前面的左单旋和右单旋就可以，难点在于双旋过后平衡因子的更新。从上面具象图和抽象图中看不出一点平衡因子的变化规律。

换个角度来看：

• 子树b在旋转前是60的左子树，旋转后成为了30的右子树。
• 子树c在旋转前是60的右子树，旋转后成为了90的左子树。
• 节点60在旋转前是子树根，旋转后成了新的根。

一步到位的来看，旋转就是将节点60的左右子树分摊给了30个90，而它自己做了新的根。

• 新插入的节点如果在子树b，那么旋转后30的右子树高度就会加一，导致30的平衡因子是0，90的平衡因子是1。
• 新插入的节点如果在子树c，那么旋转后90的左子树高度就会加一，导致90的平衡因子是0，30的平衡因子是-1。
• 新的根节点60的平衡因子是0。

自己是新增：

• 插入新节点后，60的平衡因子是0，说明它自己就是新增节点。
• 此时旋转过后，平衡因子变化了的3个节点的平衡因子都变成了0。

左右双旋代码实现：

重点在于平衡因子的更新，左单旋和右单旋直接复用前面的代码即可。

右左双旋

右左双旋和左右双旋逻辑相反，同样也不再画具象图了，直接看抽象图：

• 插入新节点后，右子树的高度发生了变化，最终根节点30的平衡因子变成了2。

//右左双旋的代码条件
parent->_bf == 2 && cur->_bf == -1;

旋转过程：

• 先进行右单旋：
• 60的右子树变成90的左子树。
• 90变成60的右子树。
• 60成为子树根。
• 再进行左单旋：
• 60的左子树变成30的右子树。
• 30变成60的左子树。
• 60成为根。
• 90的平衡因子变成0，30的平衡因子变成-1，60的平衡因子变成0。

右左双旋规律：

• 插入新节点后，变化了平衡因子的3个节点，组成一个右边退出的拐，平衡因子为2的节点在最上边，为-1的节点在其右下方，剩下一个在其左下方。

平衡因子更新：

同样忽略旋转过程，直接对比最开始和旋转后的结构：

更新方法和左右双旋的方式一样，就不再对图详细解释了，直接看代码：

//右左双旋实现
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;//在单旋转之前拿到平衡因子

		RotateR(subR);//先进行右单旋
		RotateL(parent);//在进行左单旋

		//更新平衡因子
		//插入subRL的左边
		if (bf == -1)
		{
			//右单旋后，该分支成为parent的右子树
			//parent的平衡因子为0
			parent->_bf = 0;
			//左单旋后，另一个分支成为subR的左子树
			//subR的平衡因子是1
			subR->_bf = 1;
		}
		//插入subRL的右边
		else if (bf == 1)
		{
			//右单旋后，另一分支成为parent的右子树
			//parent的平衡因子为-1
			parent->_bf = -1;
			//左单旋后，该分支成为subR的左子树
			//subR的平衡因子为0
			subR->_bf = 0;
		}
		//subRL就是新插入的节点
		else if (bf == 0)
		{
			//parent和subR的平衡因子都是0
			parent->_bf = 0;
			subR->_bf = 0;
		}
		//出错
		else
		{
			//正常情况下不会进入这里
			assert(false);
		}
		//新根的平衡因子为0
		subRL->_bf = 0;
	}

只是逻辑和左右双旋相反，就不再详细讲解了。

注意：

1. 旋转过后，平衡因子的更新最好是在封装的旋转函数中更新，如果在外面更新会因为指向关系混乱而出错。
2. 双旋时，在左右单旋之前拿到平衡因子，否则会因为旋转改变平衡因子导致判断出问题。

🌴AVL树的验证

上面已经实现了AVL树的插入，包括旋转的插入，此时我们通过插入就能成功建立一颗AVL树。

写几个测试用例看看创建是否能够成功，插入的数值是键值对，如上图所示，并且按照升序打印出来。

• 但是这只能证明二叉搜索树创建成功了，到底是不是AVL树是无法证明。

为了证明这是AVL树需要专门写一个函数来检查一下。

如上图所示，是专门用来检测是否是AVL树的。

• 通过检测，上面的三个测试用例都是AVL树。

这样拿三个例子可能不具有代表性，下面我门用随机数来检测：

• 插入十万个随机数，经过多次检测运行，发现都是AVL数，此时说明我们的AVL数成功实现了。

🌴AVL数的删除(了解)

AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

情况比较复杂，有兴趣的小伙伴可以自行了解，推荐《数据结构-用面向对象方法与C++描述》殷人昆版。

🌴AVL数的性能

AVL数是二叉搜索树，而且左右子树的高度差不会超过1，所以它非常接近完全二叉树，可以保证搜索的时间复杂度在O(log₂N)，而不会出现单只的情况。

但是还是存在一定的效率损失问题：

• 插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，
  有可能一直要让旋转持续到根的位置。

虽然旋转保证了搜索的时间复杂度在O(log₂N)，但是又增加了旋转的时间复杂度，主要是体现在插入数据时。

也就是说，AVL树的结构在修改时会导致效率低下。

🌴总结

AVL树是在二叉搜索树的基础上增加左右子树高度不超过1的限制，但是在修改结构的时候又因为旋转导致了效率降低，后面的红黑树就克服了这个问题，下篇文章见。