【高阶数据结构】AVL树（动图详解）

一. AVL树的概念

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

因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度

一棵AVL树或者是空树或者是具有以下性质的二叉搜索树

• 它的左右子树都是AVL树
• 左右子树高度之差(简称 平衡因子)的绝对值不超过1(-1/0/1)
• 平衡因子= 右子树高度 - 左子树高度非必须也可以不要只是方便我们实现的一种方式

如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在
$O(lo{g}_{2}n)$搜索时间复杂度O($lo{g}_{2}n$)

单支树的效率是$O(N)$AVL树不一样在10亿中只用找30次可能多一点

二. AVL树结点的定义

此处我们定义成三叉链结构 方便后序的操作也在每个节点引入了平衡因子右子树高度-左子树高度还需要实现一下构造函数左右子树以及父节点都是空再把平衡因子设置为0即可

template<class K, class V>
struct AVLTreeNode
{
	//定义三叉链
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	 
	//存储的键值对
	pair<K, V> _kv;

	//平衡因子(balance factor)
	int _bf;

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

注意平衡因子不是必须的只是我们实现高度平衡的一种方式不用平衡因子也是可以实现的

三. AVL树的插入

插入节点有三个步骤

1. 按照二叉搜索树的原理找到待插入的位置
2. 判断待插入的节点是在parent的左还是右插入节点
3. 更新平衡因子如果发现不平衡则要旋转

🔥因为AVL树本身就是一颗二叉搜索树插入规则比较节点大小即可

• 插入的节点key值 > 当前位置的key值插入到右子树
• 插入的节点key值 < 当前位置的key值插入到左子树
• 插入的节点key值等于当前位置的key值插入失败

🌈那判断完插入成功与否是不是就要判断平衡因子的更新了

平衡因子是否更新取决于该结点的左右子树的高度是否发生了变化因此插入一个结点后该结点的 祖先结点的平衡因子可能需要更新

🌏更新平衡因子的规则

• 新增在右parent -> bf++新增在左parent -> bf --

每更新完一个结点的平衡因子后都需要进行以下判断

1. 如果parent的平衡因子等于-1或者1表明还需要继续往上更新平衡因子
2. 如果parent的平衡因子等于0表明无需往上更新平衡因子
3. 如果parent的平衡因子等于-2或者2就已经不平衡了需要旋转处理
4. 如果parent的平衡因子大于2或者小于-2就说明之前插入的就不是AVL树了赶紧去检查💥

更新后的平衡因子	分析
-1 or 1	说明parent插入前的平衡因子是0左右子树高度相等插入后有一边高parent高度变了则需要往上继续更新
0	说明parent插入前的平衡因子是 -1 or 1左右子树一边高一边低插入后两边相等插入的填上了矮的那一边parent的高度不变不需要继续往上更新
-2 or 2	说明parent插入前的平衡因子是 -1 or 1已经是平衡的临界值了插入后变成-2 or 2 打破了平衡parent所在的子树需要旋转处理

最坏的情况如下一路更新到root根节点

那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子更新完parent结点的平衡因子后若是需要继续往上进行平衡因子的更新向上递归直到parent为空的情况以下逻辑是必须的

	cur = parent;
	parent = parent->_parent; 

当平衡因子出现了2/-2的情况要对子树进行旋转处理但也要遵守原则

• 旋转成平衡树
• 保持搜索树的规则

而旋转有四种大情况对此我们要进行分类

1. 当parent的平衡因子为2cur的平衡因子为1时进行左单旋

2. 当parent的平衡因子为-2cur的平衡因子为-1时进行右单旋

3. 当parent的平衡因子为-2cur的平衡因子为1时进行左右双旋

4. 当parent的平衡因子为2cur的平衡因子为-1时进行右左双旋

注意旋转过后无需再往上更新平衡因子了因为高度已经没有发生变化了也就不会影响父节点的平衡因子了

	//插入
	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)//插入节点值大于当前节点的key
			{
				parent = cur;
				cur = cur->_right;//往右走
			}
			else if (cur->_kv.first > kv.first)//插入节点值小于当前节点的key
			{
				parent = cur;
				cur = cur->_left;//往左走
			}
			else
			{
				//插入的节点key值等于当前位置的key值插入失败
				return false;
			}
		}
		//开始插入
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else if (parent->_kv.first < kv.first)
		{
			parent->_left = cur;
		}

		//连接parent
		cur->_parent = parent;

		//控制平衡
		//1、更新平衡因子

		while (parent)
		{
			if (cur == parent->right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			if (parent->_bf == -1 || parent->_bf == 1)//也可以用abs
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//说明parent所在的子树已经不平衡了需要旋转
				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);//左右双旋
				}

				break;
			}
			else
			{
				assert(false);//在插入前树的平衡因子就有问题
			}
		}
		return true;
	}

四. AVL树的旋转

🥑左单旋

新节点插入较高右子树的右侧—右右左单旋

⚡动图展示

抽象图过程解析

其中h可以等于0、1、2等等不过都可以归纳到这种大情况处理情况都一样都是引发parent 等于2cur等于1

左单旋旋转步骤

1. subRL变成parent的右子树subL和parent的关系要注意🔥subL可能为空
2. parent成为subR的左子树parent和subLR的关系
3. subR成为根节点ppNode 和 subL关系也要注意🔥parent是子树的根还是整棵树的根
4. 最后更新平衡因子

为什么要这样旋转要符合二叉搜索树规则

• subR的左子树的值本身就比parent的值要大所以可以作为parent的右子树
• parent及其左子树当中结点的值本身就比subR的值小所以可以作为subR的左子树

平衡因子更新

可以看见左单旋后树的高度就平衡了也就无需继续向上更新平衡因子了

代码实现如下详细注释

	void RotateL(Node* parent)
	{
	    //三叉链
		Node* subR = parent->_right;
		Node* subLR = subR->_left;
		Node* ppNode = parent->_parent;

		//subR 和 parent之间的关系
		subR->_left = parent;
		parent->_parent = subR;

		//subRL 和 parent之间的关系
		subRL = parent->_right;
		if (subRL)
			subRL->parent = parent;

		//ppNode 和 subR的关系
		if (ppNode == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;//没有父节点所以为空
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
		
		//更新平衡因子
		subR->_bf = parent->_bf = 0;
	}

🥑右单旋和左单旋高度相似

新节点插入较高左子树的左侧—左左右单旋

动图演示

抽象图过程解析

右单旋旋转步骤

与左单旋雷同看上面就行

同样也要满足二叉搜索树的性质也是和左单旋雷同看上面就行

平衡因子更新如下

同样右单旋后parent的平衡因子为0左右子树高度相等也就无需继续往上更新平衡因子了

话不多说上代码

//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* ppNode = parent->_parent;

	//subL 和 parent的关系
	subL->_right = parent;
	parent->_parent = subL;

	//subLR 和 parent之间的关系
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;

	//ppNode 和 subL的关系
	if (ppNode == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left == subL;
		}
		else
		{
			ppNode->_right == subL;
		}
		subL->_parent = ppNode;
	}
		
	//更新平衡因子
	subL->_bf = parent->_bf = 0;
}

🔥左右单旋

新节点插入较高左子树的右侧—左右先左单旋再右单旋、

动图演示

在b树或者c树中新增节点均会引发左右双旋

旋转示意图如下

1、插入新节点

2、以30为旋转点进行左单旋

3、以90为旋转点进行右单旋

左右单旋的步骤如下

1. 以subL为节点左单旋
2. 以parent为节点右单旋
3. 更新平衡因子这才是重点

左右双旋后满足二叉搜索树的性质

实际上就是把subLR的左子树和右子树分别作为subL和parent的右子树和左子树再让subL和parent分别作为subLR的左右子树最后让subLR作为整个子树的根看图理解

• subLR左子树的节点值比subL的值大所以可以作为subL的右子树
• subLR右子树的节点值比parent的值小因此可以作为parent的左子树
• 前两个步骤之后subL以及子树的值和parent的值均符合所以可以当subLR的左右子树

重点来了以subLR为突破口
左右双旋后平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况

1. 当subLR原始平衡因子是-1时左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0

2. 当subLR原始平衡因子是1时左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0

3. 当subLR原始平衡因子是0时左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0

经过左右双旋后即树的高度没有发生变化所以无需继续往上更新平衡因子

话不多说代码实现一下吧

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

		//subL节点左单旋
		RotateL(subL);

		//parent节点进行右单旋
		RotateR(parent);

		//更新平衡因子
		if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if(bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);//旋转前的平衡因子就出错了
		}
	}

🔥右左单旋

动图演示

旋转图演示过程

1、插入新节点

2、以subR的节点进行右单旋

3、以parent的节点进行右单旋

旋转步骤和左右双旋雷同

重点来了以subRL为突破口
左右双旋后平衡因子的更新随着subRL 原始平衡因子的不同分为三种情况分别对应subRL = 0、1、2情况此处就不多赘述了详细可以浏览左右双旋的情况一样

代码实现

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

		//subR右单旋
		RotateR(subR);

		//parent进行左单旋
		RotateL(parent);

		if (bf == 1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			subR->_bf = 1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

五. 验证AVL树

AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步

1. 验证其为二叉搜索树
   如果中序遍历可得到一个有序的序列就说明为二叉搜索树
2. 验证其为平衡树
   • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
   • 节点的平衡因子是否计算正确

先验证是否为二叉搜索树

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;


		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

但中序遍历只能代表是二叉搜索树不能代表是AVL树为此还需要验证二叉树的平衡性查平衡因子有一种监守自盗的感觉因为平衡因子我们刚修改完所以我们去查高度俩判断

• 如果是空树证明平衡是AVL树
• 根高度差不大于2并且递归子树的高度差都不大于2即是AVL树
• 特殊情况平衡因子和该点的高度差对不上要判断一下

	//是否平衡
	bool IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHT = Height(root->_left);
		int rightHT = Height(root->_right);
		int diff = rightHT - leftHT;
		
		if (diff  = root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		//小于2就为真 并且递归调用子树判断是否平衡
		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

	//后序查找
	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHT = Height(root->_left);
		int rightHT = Height(root->_right);

		return max(leftHT, rightHT) + 1;
	}

六. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即$lo{g}_2(N)$。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合