【数据结构高阶】AVL树

上期博客我们讲解了set/multiset/map/multimap的使用，下面我们来深入到底层，讲解其内部结构：

目录

一、AVL树的概念

二、AVL树的实现

2.1 节点的定义

2.2 数据的插入

2.2.1 平衡因子的调整

2.2.1.1 调整平衡因子的规律

2.2.2 子树的旋转调整

2.2.2.1 左单旋

2.2.2.2 右单旋

2.2.2.3 左右双旋

2.2.2.4 右左双旋

2.3 AVL树的检查验证

2.4 测试代码

三、AVL树实现的完整代码

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年，发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

● 它的左右子树都是AVL树

● 左右子树高度之差（简称平衡因子，不是每种AVL树都有平衡因子，平衡因子只是AVL树实现的一种方式）的绝对值不超过1（下图的平衡因子计算公式为：节点的右子树高度-左子树高度）

下图是一个AVL树：

二、AVL树的实现

2.1 节点的定义

这次我们直接实现K-V模型的二叉树：

template<class Key,class Val>
class AVLTreeNode
{
public:
	AVLTreeNode<Key, Val>* _left;
	AVLTreeNode<Key, Val>* _right;
	AVLTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作
	pair<Key, Val> _kv;
	int _bf;//balance factor(平衡因子)

	AVLTreeNode(pair<Key, Val> kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_bf(0)
	{}
};

2.2 数据的插入

AVL树的数据插入需要遵循二叉搜索树的规律：

template<class Key, class Val>
class AVLTree
{
public:
	typedef AVLTreeNode<Key, Val> Node;

	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}

private:
	AVLTreeNode<Key, Val>* _root = nullptr;
};

但是成功插入数据后就结束了吗？在AVL树中可没有这么简单，我们需要更新其插入节点的父节点的平衡因子，来保证这课树的整体结构还是一个AVL树。

2.2.1 平衡因子的调整

下面我们来讨论一下更新父节点平衡因子的操作：

我们看到上面的二叉树，现在向其中插入一个键值为8的数据：

插入后我们发现其插入节点的父节点平衡因子需要修改，那就要修改一下：

修改其父节点后，我们发现其父节点的父节点的平衡因子也需要调整，那再调整一下吧：

但是本次调整过后，平衡因子出现了2这个数值，但是平衡因子只能是1/0/-1，说明这时该节点下的子树已经不满足AVL树的结构了，这时要对其子树进行旋转来调整该树的结构（至于怎么旋转我们在下面会详细讲解），经过旋转过后子树肯定是满足AVL树的结构的，所以就并不再检查进行旋转的节点父节点平衡因子了：

那我们再看看另一种情况，我们向下面的二叉树中插入键值为6的数据：

插入后，我们发现需要修改其父节点的平衡因子： 

修改后，我们发现其父节点的平衡因子为0，为0时就意味着子树的高度没有发生变化，我们就没有必要再向上更新其父节点的平衡因子了： 

2.2.1.1 调整平衡因子的规律

所以总结一下上述规律，我们插入节点后肯定是要调整其父节点的平衡因子的，那调整父节点的平衡因子后，什么时候要向上调整其父节点的父节点（爷爷节点）的平衡因子呢？

这里有三种情况：

当父节点的平衡因子调整过后为1或-1时，此时说明其节点所在的子树的高度发生了变化（变为1或-1前，平衡因子只可能是0，说明插入之前子树两边的高度是相同的，这时在插入一个节点会导致其中一颗子树的高度发生变化），这时需要再继续向上调整其父节点的平衡因子

当父节点的平衡因子调整过后为2或-2时，该节点的子树不平衡，需要处理这颗旋转处理子树，旋转实质是是将该节点所在的子树的高度降1，所以旋转过后不影响子树的高度变化，此时就不需要再向上更新其父节点的平衡因子了

当父节点的平衡因子调整过后为0时（变为0前，平衡因子只可能是1或-1，说明插入之前一边高，一边低，但是插入节点是在矮的那边，其子树的高度不变），说明所在的子树高度不变，不用继续向上更新

我们用代码来实现一下平衡因子的调整：

template<class Key, class Val>
class AVLTree
{
public:
	typedef AVLTreeNode<Key, Val> Node;

	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//向上调整各节点的平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				--parent->_bf;//更新平衡因子
			}
			else
			{
				++parent->_bf;//更新平衡因子
			}
			//根据父节点的平衡因子的情况决定师傅继续向上调整各节点的平衡因子
			if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1或1继续向上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//平衡因子为2或-2,树的结构不平衡，旋转parent节点所在子树
			{
				//旋转parent所在的子树
			}
			else if (parent->_bf == 0)//平衡因子为0,插入结束
			{
				break;
			}
			else//出现其他的情况说明树的根据有问题，报错退出
			{
				cout << "树的结构出错了" << endl;
				assert(0);
				exit(-1);
			}
		}
		return true;
	}

private:
	AVLTreeNode<Key, Val>* _root = nullptr;
};

2.2.2 子树的旋转调整

当某个节点的平衡因子变为2或-2时，我们需要对其所在的子树进行旋转调整

下面我们分情况来讨论：

2.2.2.1 左单旋

下面的图代表的是一棵AVL树，其中52和60表示的两个节点，A、B、C分别为高度为h的AVL子树：

下面向C子树中插入数据使其高度发生变化：

现在键值为52的节点平衡因子变为2，下面我们要将这棵子树旋转：

我们可以看到旋转的过程是这样的：

B子树变成52的右子树->52变成60的左子树->60变成整颗树的根

上面这种需要旋转的树的根节点平衡因子为2，并且其根节点右孩子节点的平衡因子为1；这种情况下的旋转我们将其称为左单旋

下面我们就用代码实现一下左单旋：

void RotateL(Node* parent)//左单旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* pparent = parent->_parent;
	parent->_right = subRL;//更新parent的右节点
	if (subRL)//防止该节点为空
	{
		subRL->_parent = parent;//更新subRL的父节点
	}
	parent->_parent = subR;//更新parent的父节点
	subR->_left = parent;//subR的左子树置为parent
	subR->_parent = pparent;//更新subR的父节点
	if (pparent == nullptr)//旋转的是整棵树
	{
		_root = subR;//更新根节点
	}
	else//将旋转后的子树链接上整个二叉树
	{
		if (pparent->_left == parent)
		{
			pparent->_left = subR;
		}
		else
		{
			pparent->_right = subR;
		}
	}
	subR->_bf = parent->_bf = 0;//更新平衡因子
}

下图是画出了代码所表示的节点： 

2.2.2.2 右单旋

再来看到另一种情况：

 下面向子树A中插入数据使其高度发生变化：

现在键值为60的节点平衡因子变为-2，下面我们要将这棵子树旋转： 

我们可以看到旋转的过程是这样的：

B子树变成60的左子树->60变成52的右子树->52变成整颗树的根

上面这种需要旋转的树的根节点平衡因子为-2，并且其根节点左孩子节点的平衡因子为-1；这种情况下的旋转我们将其称为右单旋

下面我们用代码实现一下右单旋：

void RotateR(Node* parent)//右单旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* pparent = parent->_parent;
	parent->_left = subLR;//更新parent的左节点
	if (subLR)//防止该节点为空
	{
		subLR->_parent = parent;//更新subLR的父节点
	}
	parent->_parent = subL;//更新parent的父节点
	subL->_right = parent;//subL的右子树置为parent
	subL->_parent = pparent;//更新subL的父节点
	if (pparent == nullptr)//旋转的是整棵树
	{
		_root = subL;//更新根节点
	}
	else//将旋转后的子树链接上整个二叉树
	{
		if (pparent->_left == parent)
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
	}
	subL->_bf = parent->_bf = 0;//更新平衡因子
}

下图画出了代码所表示的节点： 

2.2.2.3 左右双旋

接着来看到稍微复杂一点的情况，下面的图代表的是一棵AVL树，其中99、66和88表示的是三个节点，A、D分别为高度为h的AVL子树，B、C分别为高度为h-1的AVL子树：

现在我们向B子树中插入数据使其高度发生变化：

现在键值为99的节点平衡因子变为-2，下面我们要将这棵子树旋转： 

下面先将66所在子树进行左单旋：

再让99所在子树右单旋：

上面这种需要旋转的树的根节点平衡因子为-2，并且其根节点左孩子节点的平衡因子为1；这种情况下的两次旋转我们将其称为左右双旋

但是我们要注意的是，当新增节点在C子树上时，通过左右双旋调整后的结果又不一样：

我们可以看到因为新增节点的位置发生了变化，最终导致了各节点的平衡因子出现了差异

除了这两种情况，还有一种当h为0的极端情况：

所以我们在用代码实现的时要注意

void RotateLR(Node* parent)//左右双旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int subLR_bf = subLR->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
	RotateL(subL);//调用左单旋
	RotateR(parent);//调用右单旋
	if (subLR_bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (subLR_bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (subLR_bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.2.2.4 右左双旋

最后我们只剩一种情况了：需要旋转的树的根节点平衡因子为-2，并且其根节点右孩子节点的平衡因子为-1

下面我们来分析：

我们向上面这棵树中的C子树插入数据使其高度发生变化：

现在键值为66的节点平衡因子变为2，下面我们要将这棵子树旋转：

下面先将99所在子树进行右单旋：

再将66所在子树进行左单旋：

这样先右旋再左旋的情况我们将其称做：右左双旋

和左右双旋一样，新增节点的位置发生变化，会导致各节点的平衡因子出现差异，当新增节点在B子树上时，通过左右双旋调整后的结果又不一样：：

另外还有h为0的特殊情况：

好了，分析到这里，使用代码实现也就不是问题了：

void RotateRL(Node* parent)//右左双旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int subRL_bf = subRL->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
	RotateR(subR);//调用右单旋
	RotateL(parent);//调用左单旋
	if (subRL_bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_bf = 0;
	}
	else if (subRL_bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (subRL_bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.3 AVL树的检查验证

下面我们来实现一个函数来检查自己所创建的AVL树是否符合规则：

int _CountHeight(Node* root)//计算树的高度
{
	if (root == nullptr)
		return 0;
	int leftnum = _CountHeight(root->_left);
	int rightnum = _CountHeight(root->_right);
	return leftnum > rightnum ? leftnum + 1 : rightnum + 1;
}
bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;
	int leftH = _CountHeight(root->_left);
	int rightH = _CountHeight(root->_right);
	if (rightH - leftH != root->_bf)//检查当前节点平衡因子是否正确
	{
		cout << root->_kv.first << "节点平衡因子异常" << endl;
		return false;
	}

	return abs(leftH - rightH) < 2
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);//检查左右子树高度之差的绝对值是否小于2
}
bool IsBalance()//检查是否为AVL树
{
	return _IsBalance(_root);
}

2.4 测试代码

void Test_AVLTree()
{
	const size_t N = 5000;
	AVLTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
	cout << t.CountHeight() << endl;
}

运行效果：

三、AVL树实现的完整代码

#pragma once
#include<iostream>
#include<cassert>

using namespace std;

template<class Key,class Val>
class AVLTreeNode
{
public:
	AVLTreeNode<Key, Val>* _left;
	AVLTreeNode<Key, Val>* _right;
	AVLTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作
	pair<Key, Val> _kv;
	int _bf;//balance factor(平衡因子)

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


template<class Key, class Val>
class AVLTree
{
	typedef AVLTreeNode<Key, Val> Node;

public:
	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//向上调整各节点的平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				--parent->_bf;//更新平衡因子
			}
			else
			{
				++parent->_bf;//更新平衡因子
			}
			//根据父节点的平衡因子的情况决定师傅继续向上调整各节点的平衡因子
			if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1或1继续向上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//平衡因子为2或-2,树的结构不平衡，旋转parent节点所在子树
			{
				//旋转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);//左右双旋
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);//右左双旋
				}
				else
				{
					assert(false);
				}
				break;
			}
			else if (parent->_bf == 0)//平衡因子为0,插入结束
			{
				break;
			}
			else//出现其他的情况说明树的根据有问题，报错退出
			{
				cout << "树的结构出错了" << endl;
				assert(0);
				exit(-1);
			}
		}
		return true;
	}

	void InOrder()//中序遍历
	{
		_InOrder(_root);
		cout << endl;
	}

	int CountHeight()//计算树的高度
	{
		return _CountHeight(_root);
	}

	bool IsBalance()//检查是否为AVL树
	{
		return _IsBalance(_root);
	}

private:
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
		parent->_right = subRL;//更新parent的右节点
		if (subRL)//防止该节点为空
		{
			subRL->_parent = parent;//更新subRL的父节点
		}
		parent->_parent = subR;//更新parent的父节点
		subR->_left = parent;//subR的左子树置为parent
		subR->_parent = pparent;//更新subR的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subR;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
		subR->_bf = parent->_bf = 0;//更新平衡因子
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
		parent->_left = subLR;//更新parent的左节点
		if (subLR)//防止该节点为空
		{
			subLR->_parent = parent;//更新subLR的父节点
		}
		parent->_parent = subL;//更新parent的父节点
		subL->_right = parent;//subL的右子树置为parent
		subL->_parent = pparent;//更新subL的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subL;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
		subL->_bf = parent->_bf = 0;//更新平衡因子
	}

	void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int subLR_bf = subLR->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
		RotateL(subL);//调用左单旋
		RotateR(parent);//调用右单旋
		if (subLR_bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if(subLR_bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (subLR_bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int subRL_bf = subRL->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
		RotateR(subR);//调用右单旋
		RotateL(parent);//调用左单旋
		if (subRL_bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (subRL_bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (subRL_bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)//如果是空树就直接结束
		{
			return;
		}
		_InOrder(root->_left);//先递归遍历其左子树
		cout << root->_kv.first << " ";//再遍历其根节点
		_InOrder(root->_right);//最后递归遍历其右子树
	}

	int _CountHeight(Node* root)//计算树的高度
	{
		if (root == nullptr)
			return 0;
		int leftnum = _CountHeight(root->_left);
		int rightnum = _CountHeight(root->_right);
		return leftnum > rightnum ? leftnum + 1 : rightnum + 1;
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int leftH = _CountHeight(root->_left);
		int rightH = _CountHeight(root->_right);
		if (rightH - leftH != root->_bf)//检查当前节点平衡因子是否正确
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		}

		return abs(leftH - rightH) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);//检查左右子树高度之差的绝对值是否小于2
	}
private:
	AVLTreeNode<Key, Val>* _root = nullptr;
};