C++进阶--AVL树

一、AVL树的概念

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

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

二、AVL树节点的定义

??我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将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;
	
	int _bf;    // 平衡因子（balance factor）
	//构造函数
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

注意：给每个结点增加平衡因子并不是必须的，只是实现AVL树的一种方式，不引入平衡因子也可以实现AVL树，只不过麻烦一点。

三、AVL树的插入

AVL树插入结点时有以下三个步骤：
1.按照二叉搜索树的插入方法，找到待插入位置。
2.找到待插入位置后，将待插入结点插入到树中。
3.更新平衡因子，如果出现不平衡，则需要进行旋转。
因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：
1.待插入结点的key值比当前结点小就插入到该结点的左子树。
2.待插入结点的key值比当前结点大就插入该结点的右子树。
3.待插入结点的key值与当前结点的key值相等就插入失败。
??如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。最后记得将当前结点的_parent指针指向它的parent。
与二叉搜索树插入结点不同的是，AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子。
??由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化（变了继续更新，不变则不再更新），因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新。

??插入完一个结点之后，首先，需要做的是以下三个步骤
1.更新平衡因子
2.如果更新完以后，平衡因子没有出现问题（|bf|<=1），平衡结构没有受影响，不需要处理。
3.如果更新完以后，平衡因子出现问题（|bf|>1），平衡结构受到影响，需要处理（旋转）
??所以插入结点后需要倒着往上更新平衡因子，更新规则如下：
1.新增结点在parent的右边，parent的平衡因子++。
2.新增结点在parent的左边，parent的平衡因子–。
每更新完一个结点的平衡因子后，都需要进行以下判断：
什么决定了是否继续往上更新爷爷结点，取决于parent所在的子树高度是否变化？变了继续更新，不变则不再更新

• 如果parent的平衡因子等于-1或者1，表明parent所在的子树变了，继续更新。为什么？因为插入前parent的平衡因子为0，说明插入前左右两边高度相等，现在有一边高1，说明parent一边高一边低，高度变了。
• 如果parent的平衡因子等于0，表明parent所在的子树高度不变，不用继续往上更新，这一次插入结束。为什么呢？说明插入前是parent的平衡因子是-1或1，插入之前一边高，一边低，插入结点填上矮的那边，它的高度不变。
• 如果parent的平衡因子等于-2或者2，表明parent所在的子树不平衡，需要处理这颗子树（旋转处理）

??而在最坏情况下，我们更新平衡因子时会一路更新到根结点。
??说明一下：由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。当然，也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是比较麻烦。
??若是在更新平衡因子的过程中，出现了平衡因子为-2/2的结点，这时需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析：
??我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑：

cur=parent;
parent = parent -> _parent;

当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0

理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平很因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：
1.其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1/1
2.其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中教矮的一棵子树增高了，新增结点后其平衡因子更新为0。
综上所述：当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
可以将旋转处理分为以下四类

1.当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
2.当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
3.当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
4.当parent的平衡因子为2，cur的平衡因子为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)
			{
				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->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//更新平衡因子
		while (parent)
		{
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续更新
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf==2||parent->_bf==-2)
			{
				//需要旋转处理 --  1、让这棵子树平衡  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)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}

				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

四、AVL树的旋转

4.1 左单旋

左单旋示意图如下：

左单旋的步骤如下：
1.让subR的左子树作为parent的右子树。
2.让parent作为subR的左子树。
3.让subR作为整个子树的根。
4.更新平衡因子。

左单旋后满足二叉搜索树的性质：
1.subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
2.parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。

平衡因子更新如下：

可以看到，经过左单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左单旋后无需继续往上更新平衡因子。

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

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* ppnode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

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

注意：结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向。

4.2 右单旋

右单旋示意图如下：

右单旋的步骤如下：
1.让subL的右子树作为parent的左子树。
2.让parent作为subL的右子树。
3.让subL作为整个子树的跟。
4.更新平衡因子。

右单旋后满足二叉搜索树的性质：
1.subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。
2.parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。

平衡因子更新如下：

可以看到，经过右单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以右单旋后无需继续往上更新平衡因子。

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 (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
		subL->_bf = parent->_bf = 0;
	}

注意：结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向。

4.3 左右双旋

左右双旋示意图如下：
1.插入新结点

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

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

左右双旋的步骤如下：
1.以subL为旋转点进行左单旋。
2.以parent为旋转点进行右单旋。
3.更新平衡因子。

左右双旋后满足二叉搜索树的性质：
左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根。
1.subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2.subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
3.经过步骤1/2后，subL及其子树当中结点的值都比subLR的值小，而parent及其子树当中结点的值都比subLR的值大，因此他们可以分别作为subLR的左右子树。

左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1.当subLR原始平衡因子是-1时（在b的位置进行插入），左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0

2.当subLR原始平衡因子是1时（在c的位置进行插入），左右双旋后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;

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

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

4.4 右左双旋

右左双旋示意图如下：
1.插入新结点

2.以90为旋转点进行右单旋

3.以30为旋转点进行左单旋

右左双旋的步骤如下：
1.以subR为旋转点进行右单旋
2.以parent为旋转点进行左单旋
3.更新平衡因子

右左双旋后满足二叉搜索树的性质：
右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根。
1.subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。
2.subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树
3.经过步骤1/2后，parent及其子树当中结点的值都比subRL的值小，而subR及其子树当中结点的值都比subRL的值大，因此它们可以分别作为subRL的左右子树

右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1.当subRL原始平衡因子是1时，左右双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0
2.当subRL原始平衡因子是-1时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、1、0
3.当subRL原始平衡因子是0时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、0、0

可以看到，经过右左双旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以右左双旋后无需继续往上更新平衡因子。

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

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

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

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1.验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2.验证其为平衡树

• 每个结点子树高度差的绝对值不超过1（注意结点中如果没有平衡因子）
• 结点的平衡因子是否计算正确

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

bool _IsBalance(Node* root)
	{
		if (root == NULL)
		{
			return true;
		}

		int leftH = _Height(root->_left);
		int rightH = _Height(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);
	}

3.验证用例

• 常规场景1
  {16，3，7，11，9，26，18，14，15}

• 特殊场景2
  {4，2，6，1，3，5，15，7，16，14}

六、AVL树的删除

??因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将结点删除，然后再更新平衡因子，只不过与删除不同的是，删除结点后的平衡因子更新，最差情况下一直要调整到根结点的位置。
??可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆

七、AVL树的性能

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