作者：@小萌新
专栏：@数据结构进阶
作者简介：大二学生 希望能和大家一起进步！
本篇博客简介：介绍高阶数据结构:AVL树

AVL树的概念

首先抛出一个问题 为什么AVL树会诞生呢？

还记不记得我们在学习二叉搜索树最后总结的时候说的一句话

在二叉搜索树是完全二叉树的情况下效率最高 此时的效率是 LogN

在二叉搜索时是单边树的情况下效率最差 此时效率退化至 N

为了解决这个退化的效率问题 AVL树诞生了

AVL树是由两位俄国科学家G.M. Adelson-Velsky和E.M.Landis在1962年发明的。他们在一篇论文中提出了AVL树这一概念，并将其命名为"AVL树"，以纪念他们的姓氏的首字母。
AVL树是一种自平衡二叉搜索树，它能够保证插入、删除和查找操作的时间复杂度都是O(log n)，因此在很多场合下都很有用。

AVL树可以是一颗空树 也可以是具有以下性质的一颗二叉搜索树

1. 它的左右子树都是AVL树
2. 树的左右子树高度差不超过一 （以下样例均为右子树减左子树）

上面就是一棵AVL树

蓝色数字表示的是左右子树的高度差值(以下简称平衡因子) 它们都是不超过1的

红色的数字表示储存数据的值 符合二叉搜索树的性质

我们可以发现 当一颗二叉搜索树是AVL树的时候 假设它一共有N个节点 那么它的高度非常接近LogN 同样的搜索效率也接近LogN

这也就解决了单边树的低效问题

AVL树节点类的定义

我们这里使用KV模型来实现AVL树

为了方便后续的操作 使用三叉链结构来完成它

一个节点除了指向它的左右两个子节点之外还指向它的父节点 一共三个指针 所以称为三叉链

此外 我们还增加一个int类型的数据 来记录平衡因子

代码表示如下

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

	// 平衡因子
	int _bf;

	// 储存的键值对
	pair<K, V> _kv;


	// 构造函数
	AVLTreeNode(const pair<K , V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0) //因为构造出来之后没有左右子树 所以说平衡因子为0
	{}

};

AVL树的插入

AVL树的插入满足下面几个步骤

1. 遵循二叉搜索树的插入原则 找到待插入位置
2. 找到插入位置之后 插入节点
3. 更新平衡因子 如果平衡因子不满足AVL树的条件 则使之满足

第一步第二步很简单 如果还有不明白的同学可以参考这篇博客

二叉搜索树的实现

接下来我们重点学习第三步

由于我们插入一个节点之后 只有可能是这个节点的父节点的高度受到影响

所以说我们只需要更新它的祖先节点 这也是我们为什么设计成三叉链结构的原因 - 方便找祖先节点

（这个图稍微有点漏洞 我们这里假设新增的节点是6.5 前面的节点都是浮点数）

新增节点之后我们开始更新平衡因子 遵循下面的规则

1. 如果新增节点在父节点的右边 则平衡因子++
2. 如果新增节点在父节点的左边 则平衡因子–

这里我们可以发现 如果有一个父节点的平衡因子更新成了0 则无需向上继续更新了

怎么解释这个现象呢？

我们都知道 平衡因子是根据父节点左右子树的高度来确定的

如果父节点的平衡因子被更新成了0 那么肯定就说明 原来有一边的高度是大于另一边的 而且是大于1

插入一个新的节点之后两边的高度差就被填平了

那么对于父节点的父节点来说 这边子树的高度并没有变化 所以说我们不需要向上更新了

所以说我们有具体的规则如下

• 如果父节点的平衡因子更新之后结果为1或者-1 则需要继续向上更新祖先节点的平衡因子
• 如果父节点的平衡因子更新之后结果为0 则不需要继续向上更新祖先节点的平衡因子
• 如果父节点的平衡因子更新之后结果为2或者-2 则需要进行旋转操作来处理异常

我们假设目前的节点是cur 它的父节点是parent

因为我们执行的是插入操作 所以说我们的节点肯定是增加的 就看增加的是父节点的左子树还是右子树

因为我们不能确定是左子树还是右子树 所以要执行判断

• 如果cur是parent的左节点 则平衡因子–
• 如果cur是parent的右节点 则平衡因子++

但是到这里还没完 我们要需要继续向上更新 执行下面的代码

cur = parent;
parent = parent->_parent;

最差的情况下 我们一直要更新到根节点

按照上面的规则 我们写出代码

	bool insert(const pair <K,V>& kv)
	{
		if (_root == nullptr) // 如果AVL树为空 则直接为其根节点
		{
			_root = new Node(kv);
			return true;
		}

		// 如果不为空 则按照二叉树的插入方式 通过key值 即first来比较
		Node* cur = _root; // cur确定当前位置
		Node* parent = nullptr; // parent最后连接用 
		while (cur) // 当cur不为空的时候一直走
		{
			if (kv.first > cur->_kv.first) // 如果插入值大于当前节点 向右移
			{
				cur = cur->_right;
				parent = cur;
			}
			else if (kv.first < cur->_kv.first) // 如果插入值小于当前节点 向右移
			{
				cur = cur->_left;
				parent = cur;
			}
			else // 到这里这种情况说明等于 则插入失败 返回false
			{
				return false;
			}
		}

		// 将待插入节点插入到树中
		cur = new Node(kv);
		// 根据kv的key值来分辨插入的是左子树还是右子树
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent; // 因为是三叉链 所以要更新父节点
		}
		else // 因为走到这里了kv的key值不可能相等 所以说else就表示小于
		{
			parent->_left = cur;
			cur->_parent = parent; // 因为是三叉链 所以要更新父节点
		}


		// 更新平衡因子
		while (cur != _root) // 最坏的情况 一直更新到根节点 但是cur不可能到根节点
		{
			// 如果是右则平衡因子++ 反之则--
			if (cur = parent->_left)
			{
				parent->_bf--;
			}
			else if (cur = parent->_right)
			{
				parent->_bf++;
			}

			// 平衡因子更新完毕 此时开始查看父亲节点的平衡因子是多少 是否结束 是否需要旋转
			if (parent->_bf == 0) // 如果父亲的平衡因子是0 则停止更新 直接返回
			{
				return true;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) // 如果父亲的平衡因子是1或-1 则继续往上更新
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2) // 如果父亲的平衡因子是2或-2 则进行旋转操作
			{
				// 旋转
			}


		}
	}

省略了旋转操作的插入代码就在上面 接下来我们重点研究下AVL的旋转操作

AVL树的旋转

首先我们要明确一点 当parent节点的平衡因子是2或者-2时候 cur的平衡因子必然是1或者-1

因为如果cur的平衡因子是0 有两种情况

1. cur为新增节点 这个时候由于我们插入的是AVL树 所以其父节点只有可能是1 -1 或者0
2. cur为更新后的节点 此时cur为其子节点的父节点 其平衡因子更新到了0 不会继续向上更新 所以cur的父节点一定是有正常的平衡因子 1 -1 或者0

所以说我们这里就有四种情况

• parent的平衡因子是2 cur的平衡因子是1
• parent的平衡因子是2 cur的平衡因子是-1
• parent的平衡因子是-2 cur的平衡因子是1
• parent的平衡因子是-2 cur的平衡因子是-1

然后我们根据这四种情况来讨论如何旋转

左单旋

从上图我们可以观察发现 parent的平衡因子被更新为了2 此时肯定要触发旋转

旋转后的图片大概是这样子

经过旋转后 平衡因子全部恢复正常 并且此时将这颗二叉树作为一个整体 它的高度还是h+2

所以不用继续往上更新平衡因子了

那么我们具体来看看实现左单旋要分几步

1. 让 subr 左子树 subrl 成为 parent 的右子树
2. 让 parent 成为 subr 的左子树
3. 让 subr 作为整个子树的根 （如果parent不是根节点的话）
4. 更新平衡因子

此时 subr 和 parent 的平衡因子都更新为0

而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的

此外 观察第一张图我们可以知道

左单旋对应着 parent的平衡因子是2 cur的平衡因子是1 这种情况

我们左单旋的代码表示如下

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* grandparent = parent->_parent;


		// 建立subR和parent的联系
		subR->_left = parent;
		parent->_parent = subR;

		// 建立parent和subRL的联系
		parent->_right = subRL;
		if (subRL) // 有可能subRL为空
		{
			subRL->_parent = parent;
		}

		// 建立grandparent和sunR的联系
		// 这里要分grandparent是否存在以及parent是grandparent的左还是右
		if (grandparent) // 如果进去了 则说明grandparent存在 
		{
			// 如果存在 要分清楚parent在左边还是右边
			if (grandparent->_left == parent)
			{
				grandparent->_left = subR;
			}
			else
			{
				grandparent->_right = subR;
			}
			subR->_parent = grandparent;
		}
		// 否则就是不存在 我们更新_root 并且将subR的父节点置空
		else
		{
			_root = subR;
			subR->_parent = nullptr;
		}


		// 更新平衡因子
		subR->_bf = 0;
		parent->_bf = 0;
	}

只要按照上面的步骤一行行写 应该是不难理解的

这里尤其要注意的是 我们使用的是不熟悉的三叉链结构

右单旋

从上图我们可以观察发现 parent的平衡因子被更新为了-2 此时肯定要触发旋转

旋转后的图片大概是这样子

经过旋转后 平衡因子全部恢复正常 并且此时将这颗二叉树作为一个整体 它的高度还是h+2

所以不用继续往上更新平衡因子了

那么我们具体来看看实现右单旋要分几步

1. 让 subl 的右子树 sublr 成为 parent 的左子树
2. 让 parent 成为 subl 的左子树
3. 让 subr 作为整个子树的根 （如果parent不是根节点的话）
4. 更新平衡因子

此时 subl 和 parent 的平衡因子都更新为0

而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的

此外 观察第一张图我们可以知道

右单旋对应着 parent 的平衡因子是-2 cur 的平衡因子是-1 这种情况

我们右单旋的代码表示如下

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* grandparent = parent->_parent;


		// 建立subL和parent之间的联系
		subL->_right = parent;
		parent->_parent = subL;

		// 建立parent和subLR之间的联系 
		parent->_left = subLR;
		if (subLR) // subLR可能不存在 
		{
			subLR->_parent = parent;
		}

		// 建立grandparent和subl之间的联系
		// 这里要分grandparent是否存在以及parent是grandparent的左还是右
		if (grandparent)
		{
			// 如果存在 要分清楚parent在左边还是右边
			if (grandparent->_left == parent)
			{
				grandparent->_left = subL;
			}
			else
			{
				grandparent->_right = subL;
			}

			subL->_parent = grandparent;
		}
		else // 这里就是表示parent就是根节点
		{
			_root = subL;
			subL->_parent = nullptr;
		}


		// 更新平衡因子
		subL->_bf = 0;
		parent->_bf = 0;
	}

左右双旋

左右双旋一般分三步走 图片表示如下

第一步 插入新增节点 触发旋转机制

第二步 以30为旋转点进行左单旋

第三步 以90为旋转点进行右单旋

左右双旋的步骤如下

1. 以subL为旋转点进行左单旋
2. 以parent为旋转点进行右单旋
3. 更新平衡因子

而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的

此外 观察第二张图我们可以知道

左右双旋对应着 parent 的平衡因子是-2 cur 的平衡因子是1 这种情况

左右双旋后 平衡因子的更新随着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

产生这三种情况的原因分别是

插入的节点可能是sublr 的左子树 右子树 或者是sublr本身

代码表示如下

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = parent->_left->_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); 
		}
	}

右左单旋

右左双旋一般分三步走 图片表示如下

第一步 插入新增节点 触发旋转机制

第二步 以90作为节点进行右单旋

第三步 以30作为节点进行左单旋

右左双旋的步骤如下

1. 以subR为旋转点进行右单旋
2. 以parent为旋转点进行左单旋
3. 更新平衡因子

而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的

此外 观察第二张图我们可以知道

右左双旋对应着 parent 的平衡因子是2 cur 的平衡因子是-1 这种情况

右左双旋后 平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况

1. 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 1 0 0
2. 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 0 -1 0
3. 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 0 0 0

产生这三种情况的原因分别是

插入的节点可能是subrl 的左子树 右子树 或者是subrl本身

代码表示如下

	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;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 0)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false); 
		}
	}

AVL树的验证

首先AVL树是一颗二叉搜索树 所以说它满足中序遍历后是有序的这个原则 我们可以使用中序遍历来验证

代码表示如下

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


		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}

	void Inorder()
	{
		_Inorder(_root);
	}

但是中序遍历只能证明这棵树是二叉搜索树 要证明它是AVL树我们必须还要证明它的平衡因子全部无异常

我们可以从根节点开始 往上遍历每个子树来判断它是否是AVL树 如果全部是AVL树 则可以验证

如果有一颗不是 则证明不是AVL树

//判断是否为AVL树
bool IsAVLTree()
{
	int hight = 0; //输出型参数
	return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
	if (root == nullptr) //空树是平衡二叉树
	{
		hight = 0; //空树的高度为0
		return true;
	}
	//先判断左子树
	int leftHight = 0;
	if (_IsBalanced(root->_left, leftHight) == false)
		return false;
	//再判断右子树
	int rightHight = 0;
	if (_IsBalanced(root->_right, rightHight) == false)
		return false;
	//检查该结点的平衡因子
	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子设置异常：" << root->_kv.first << endl;
	}
	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
	hight = max(leftHight, rightHight) + 1;
	return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
}

AVL树的查找

AVL树的查找方式与二叉搜索树相同

1. 如果树为空树 则查找失败 返回nullptr
2. 如果key值小于当前节点 则进入当前节点的子树查找
3. 如果key值大于当前节点 则进入当前节点的子树查找
4. 如果key值等于当前节点 则返回当前节点

代码表示如下

	Node* find(const K& key)
	{
		Node* cur = _root;

		while (cur) // 一直查找到空为止
		{
			if (key < cur->_kv.first) // 小于
			{
				cur = cur->_left;
			}
			else if (key < cur->_kv.first) // 大于
			{
				cur = cur->_right;
			}
			else // 等于
			{
				return cur
			}
		}
		// 走到这里就是没找到
		return nullptr;
	}

AVL树的修改

我们所说的修改一般是值对于value值的修改

一般步骤如下

1. 找到对应的key值的结点
2. 对其value值进行修改

代码表示如下

	bool Modify(const K& key, const V& value)
	{
		Node* ret = find(key);
		// 有可能不存在
		if (ret == nullptr)
		{
			return false;
		}
		ret->_kv.second = value;
		return true;
	}

AVL树的删除

AVL树的删除满足下面几个步骤

1. 遵循二叉搜索树的删除原则 找到待删除位置
2. 找到删除位置之后 删除节点
3. 更新平衡因子 如果平衡因子不满足AVL树的条件 则使之满足

由于我们学习AVL树主要是为了后面的红黑树做铺垫 需要重点掌握的是AVL树的插入

并且AVL树的删除在平时的笔试面试中考察的很少 或者说几乎没有考察 所以同学们可以跳过这一部分的学习

AVL树的性能

AVL树是一颗近乎完全二叉树的二叉搜索树 所以说它查询的时间复杂度非常低 为Log N

但是如果要对于AVL树做一些结构修改的操作 它的性能就会十分低下 比如在插入和删除时 可能要经过大量的旋转操作

因此 如果是需要一种查询高效的数据结构 AVL树是十分合适的
但是 如果它经常要被修改 AVL树的性能就可能不太匹配了