AVL树的介绍及实现

（一）AVL的概念

AVL树是一棵高度平衡的二叉搜索树，通过控制高度差去控制平衡。AVL可以是一棵空树，若不是空树则需要具备以下性质：

1. 它的任意一棵左右子树都是AVL树
2. 任何一棵左右子树的高度差的绝对值不超过1

这篇文章我将引入一个平衡因子来完成AVL树的实现。平衡因子的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，而且任何结点的平衡因子只能为0/1/-1，若不是则需要进行旋转操作。AVL树并不是必须要平衡因子，但有了它能让我们更好地去观察和控制树是否平衡

AVL树见下图：

AVL树可以说它的整体结点数量及分布和完全二叉树类似，因为AVL树缺结点的话，缺的也就在树的最后两层上面，所以AVL树的高度可以控制在logN，那么增删查改的效率就是O(logN)，相比二叉搜索树有了本质的提升

（二）AVL树的实现

1.AVL树的结构

AVL树的结构与二叉搜索树的结构类似，在这里就不介绍了，不理解的可以看博主二叉搜索树的那篇文章，结构如下代码：

template<class K,class v>
struct AVLTNode
{
	pair<k, v> _kv;
	AVLTNode<k, v>* _left;
	AVLTNode<k, v>* _right;
	AVLTNode<k, v>* _parent;//需要parent指针，后续用来更新平衡因子
	int _bf; //balance factor用于存储平衡因子

	AVLTNode(const pair<k,v>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{ }
};

template<class k,class v>
class AVLTree
{
	typedef AVLTNode<k, v> Node;
public:

private:
	Node* _root = nullptr;
};

2.AVL树的插入

AVL树插入一个值的大致步骤如下：

1. 首先，插入一个值要按照二叉搜索树的插入规则来进行插入，插值比当前结点小，往左走；插值比当前结点大，往右走，走当空位置时，说明找到了插值的结点位置

代码的解析在二叉搜索树的那篇文章中，下面博主就直接放代码了：

bool insert(const pair<k, v>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	else
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);

		if (parent->_kv.first > cur->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;//使插入的结点与父结点进行连接，以便更新平衡因子

		//更新平衡因子
		//....
		return true;
	}
}

2. 插入完结点之后，更新平衡因子

当插入完一个结点之后，我们要如何判断插入之后，该树是否还保持平衡。可知，新增结点的平衡因子都为0，那新增结点之后会影响到哪些结点的平衡因子呢，来看下图：

如图，当插入11这个结点之后，影响了祖先结点的高度，就会影响全部祖先或者部分祖先的平衡因子，所以要更新从新增结点到根结点路径上的平衡因子，最坏的情况就是要更新平衡因子更新到根结点，如何判断是否需要更新到根结点的平衡因子，具体详解如下：

看上面的图，当新增结点11，新增在10的右边，结点10的高度就增加了1，而且增加在结点10 的右边，所以结点10的平衡因子就要++，因为平衡因子等于右子树的高度减左子树的高度，右子树的高度增加了1，那么就是平衡因子++，再继续看，新增的结点11对结点10的上一层也有影响，因为结点10的高度变了，变了就会对上一层有影响，那么结点10在结点8的右边，那么结点8的平衡因子也要++，新增节点也影响了结点8的高度，那么也会对根结点产生影响，根结点的平衡因子也要更新。

总结平衡因子更新原则：

• 平衡因子 = 右子树的高度 - 左子树的高度
• 只有子树高度变化才会影响当前结点平衡因子
• 插入结点，会增加高度，所以当新增结点在parent的右子树，那么parent的平衡因子++；若新增结点在parent的左子树，那么parent的平衡因子–
• parent所在子树高度是否变化决定了是否需要继续向上更新平衡因子

判断更新平衡因子停止的条件：

• 新增结点后，更新parent的平衡因子，若更新后平衡因子为1/-1，说明更新前到更新后parent的平衡因子的变化为0->1/0->-1，更新前parent的左右子树的高度相等，更新后变成了一高一低，parent所在的子树符合平衡的要求，但是高度增加了1，符合更新原则的最后一条规则，所以需要继续向上更新平衡因子
  
• 新增结点后，更新parent的平衡因子，若更新后平衡因子为2/-2，说明更新前到更新后的变化为1->2/-1->-2，更新前parent的左右子树的高度是一边高一边低的，新增结点插入到了高的那一边，导致高的那棵子树变得更高了，破坏了树的平衡，parent所在的子树不符合平衡要求，需要进行旋转操作来控制平衡，旋转的目标有两个：1.把parent子树旋转平衡 2.降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后不需要继续向上更新，更新结束，即插入结束（旋转操作，在下面有介绍）
  
• 新增结点后，更新parent的平衡因子，若更新后平衡因子为0，说明更新前到更新后的变化为1->0/-1->0，插入结点前parent左右子树的高度为一高一低，新插入的结点在parent低的那一边，左右子树的高度相等，使parent所在子树的高度不变，不会影响祖先结点的高度，停止更新，即插入结束

• 还有可能最坏的情况下一直更新到根结点，更完根结点的平衡因子之后，也结束了

实现代码如下：

//更新平衡因子
while (parent) //最坏情况下更新到根，若parent为空说明结束，因为只有根结点是没有父结点的
{
	if (parent->_right == cur)
	{
	//若新增结点在父结点的右子树，那么平衡因子++
		parent->_bf++;
	}
	else
	{
	//若新增结点在父结点的左子树，那么平衡因子--
		parent->_bf--;
	}
	//判断是否需要继续向上更新平衡因子
	if (parent->_bf == 0)
	{
	//若父结点平衡因子等于0，说明不影响祖先所在结点的高度，更新结束
		break;
	}
	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，破坏平衡要求，旋转处理
		// 旋转操作，旋转之后停止更新
		break;
	}
}

3. 破坏了平衡要求后需要进行旋转处理，旋转详解如下

旋转的原则：

• 保持搜索树的规则
• 让旋转的树从不满足平衡到满足平衡，其次降低旋转树的高度

旋转分为：左单旋、右单旋、左右双旋、右左双旋

右单旋：
右单旋的情况有很多种，这里就通过抽象出来进行讲解，如下图：

当新增结点在a位置时，树的平衡遭到破坏，此时结点10的平衡因子变成了-2，就需要进行旋转处理，旋转步骤：以结点10为旋转点，由于b的范围在结点5到结点10之间，所以可以将b给结点10的左子树，再将结点10给结点5的右子树，该旋转过程就叫作右单旋。如下图：

新增结点可分为三种情况：

第一种，当h = 1时，新增在a的左子树，旋转示例如下：

第二种情况，当h = 1时，新增在a的右子树，旋转示例如下：

第三种情况，当h = 0 时，新增在a位置，旋转示例如下：

从这三种情况，我们可以看到，在进行右单旋后，parent结点和subL结点的平衡因子都为0，而且只有这两个结点发生变化，因为想要发生右单旋的情况，b结点和c结点是必须要共同出现或消失的，有c结点时，再将b结点给parent的左孩子，那么parent的平衡因子一定为0，反之平衡因子也为0；同样的若有c结点，要想进行右单旋，新增节点必然在a的左右子树，再进行旋转后，subL两边的高度肯定会保持一致，反之若无结点c，新增结点必然在a位置，只有三个结点的旋转，旋转后sbL左右高度必然是平衡的

注：在旋转的过程中，也要注意更新旋转结点的父指针

右单旋总结：
1.将b给根结点的左子树，再将根结点给subL的右子树，将subL变成根结点
2.旋转后parent和subL结点的平衡因子都为0
3.发生右单旋的条件，parent的平衡因子为-2，parent的左子树的根的平衡因子为-1

代码如下：

//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;//subL为旋转点的左孩子
	Node* subLR = subL->_right;//subLR也就是图中的b位置

	parent->_left = subLR;//将b给旋转点的左子树
	if (subLR) //可能为空，就不需要更新父结点
		subLR->_parent = parent;

	Node* pparent = parent->_parent; //记录旋转点的父结点
	subL->_right = parent;//将subL的右指向旋转点
	parent->_parent = subL;//更新旋转点的父结点

	if (pparent == nullptr) //判断旋转前的根结点是否为旋转点
	{
		_root = subL; // 直接将subL变成树的根
		subL->_parent = nullptr;
	}
	else
	{
	//判断subL结在父结点的左子树还是右子树
		if (pparent->_left == parent)
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
		//更新subL的父结点
		subL->_parent = pparent;
	}
	//更新平衡因子
	subL->_bf = parent->_bf = 0;
}

左单旋：

左单旋的抽象图如下：

当新增结点在a位置时，树的平衡遭到破坏，此时结点10的平衡因子变成了2，就需要进行旋转处理，旋转步骤：以结点10为旋转点，由于b的范围在结点10到结点15之间，所以可以将b给结点10的右子树，再将结点10给结点15的左子树，该旋转过程就叫作左单旋。

新增结点的情况也有三种，跟右单旋一样，可以新增在a的左右子树，也可以新增在a位置，类似的旋转过程这里就省略了。左单旋也是只会影响parent和subR结点的平衡因子，以右单旋的方式类推，也可以得出左单旋中parent和subR结点的平衡因子也为0

左单旋总结：
1.将b给根结点的右子树，再将根结点给subR的左子树，将subR变成根结点
2.旋转后parent和subL结点的平衡因子都为0
3.发生左单旋的条件，parent的平衡因子为2，parent的左子树的根的平衡因子为1

代码如下：

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

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

	Node* pparent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;

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

	subR->_bf = parent->_bf = 0;
}

左右双旋：

什么情况下才会发生左右双旋，请看下图：

两种情况对比，一个新增结点在a位置，另一个新增结点在b位置，为什么新增结点在b位置的情况下，右单旋之后依旧没有保持平衡呢，看到图中被我圈起来的位置，能发生右单旋的新增结点的长度是要纯粹的左边高的，当新增结点在b位置时，它的长度不是纯粹的左边高，它是左边高即右边也高，所以不能纯粹的只进行单旋转的操作，需要进行两次单旋转操作

左右双旋核心步骤：先对parent结点的左孩子进行左单旋，也就是图中结点10的左孩子，结点5进行左单旋，因为对结点5来说它的右子树较高，所以以结点5为旋转点进行左单旋，左单旋完之后，对结点10来说左子树较高，再以结点10为旋转点进行右单旋

左右双旋，可分三种情况来讨论：

第一种，当h = 1时，新增结点在b位置的左子树，旋转操作如下：

第二种，当h = 1时，新增结点在b的右子树，旋转操作如下：

第三种，当h = 0时，新增结点在b位置，旋转操作如下：

从上面三种情况可以得知，右边高即左边高时，用左右双旋，先以父结点的左孩子为旋转点，进行左单旋，再以父结点为旋转点进行右单旋。左右双旋只会影响parent、subL和subLR结点的平衡因子，它们的平衡因子，也分三种情况。

左右双旋后的平衡因子：

1.第一种情况，当h = 1且新增结点在b的左子树时，subL的平衡因子为0，因为h为1时，subL的高度为一高一低，当把subLR的左给subL的右时，subL就平衡了，所以平衡因子为0；parent的平衡因子为1，因为此时parent的左右子树为一高一低且新增结点在b的左子树，b的右子树为空，当进行右单旋时，b的右子树给parent的左子树，给的是空树，所以parent的平衡因子为1；subLR的平衡因子为0。

2.第二种情况，当h = 1且新增结点在b的右子树时，subL的平衡因子为-1，因为h为1时，subL的高度为一高一低，进行左单旋，当把subLR的左给subL的右时，由于subLR的左子树为空，所以subL的平衡因子为-1；parent的平衡因子为0，因为此时parent的左右子树为一高一低且新增结点在subLR的右子树，当进行右单旋时，subLR的右子树给parent的左子树，所以parent的平衡因子为0；subLR的平衡因子为0。

3.第三种情况，当h = 0且新增在b位置，b的左右子树都为空，即subL、parent和subLR的平衡因子都为0。

注：根据b结点的平衡因子即可判断新增节点在哪个位置

左右双旋总结：
1.以parent结点的左孩子为旋转点进行左单旋，再以parent结点进行右单旋
2.旋转后根据b结点的平衡因子判断新增结点的位置，再判断更新平衡因子
3.发生左右双旋的条件，parent的平衡因子为-2，parent的左子树的根的平衡因子为1

代码如下：

//左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(parent->_left);//先进行左单旋
	RotateR(parent);//再进行右单旋

	if (bf == 0)//新增结点在b位置
	{
		subL->_bf = 0;
		parent->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == -1)//新增结点在b的左子树
	{
		subL->_bf = 0;
		parent->_bf = 1;
		subLR->_bf = 0;
	}
	else if (bf == 1)//新增结点在b的右子树
	{
		subL->_bf = -1;
		parent->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

右左双旋：

右左双旋的抽象图，如下：

在b位置进行新增结点，就会导致右边高及左边高，它不是纯粹的右边高，所以不能直接进行左单旋，需要先进行右单旋，降低左边的高度，再进行左单旋，降低右边的高度

右左双旋核心步骤：先对parent结点的右孩子进行右单旋，也就是图中结点10的右孩子，结点15进行右单旋，因为对结点15来说它的左子树较高，所以以结点15为旋转点进行右单旋，右单旋完之后，对结点10来说右子树较高，再以结点10为旋转点进行左单旋

右左双旋也是根据新增结点的位置，即h的高度分三种情况来讨论，与左右双旋的情况类似，这里就不做展开分析

右左双旋后平衡因子的更新，同样也是分三种情况来讨论，与左右双旋的推到过程类似，当h = 1，新增结点在b的左子树时，subR的平衡因子为1，parent的平衡因子为0，subRL的平衡因子为0；当h = 1,新增结点在b的右子树时，subR的平衡因子为0，parent的平衡因子为-1，subRL的平衡因子为0；当h = 0，新增结点在b位置时，三个结点的平衡因子都为0

注：根据b结点的平衡因子即可判断新增节点在哪个位置

右左双旋总结：
1.以parent结点的右孩子为旋转点进行右单旋，再以parent结点进行左单旋
2.旋转后根据b结点的平衡因子判断新增结点的位置，再判断更新平衡因子
3.发生右左双旋的条件，parent的平衡因子为2，parent的左子树的根的平衡因子为-1

代码如下：

//右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

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

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

完成以上三种大的步骤，插入才算完成

3.AVL树的查找

AVL树的查找，是通过key关键值查找的，比当前结点的值大就往右查找，比当前结点的值小，就左继续查找，走到空说明要查找的值不存在。想详细了解可看博主二叉搜索树那篇文章的内容，代码实现如下：

Node* find(const k& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

（三）检查一棵树是否是AVL树

方法：通过遍历每个结点，计算每个结点左右子树的高度，用右子树的高度-左子树的高度，计算结果与结点的平衡因子进行比较。可用前序、中序或者后序对整个树进行遍历一遍，进行计算和检查

代码如下：

int _Hight(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}

	int lefthight = _Hight(root->_left);
	int righthight = _Hight(root->_right);

	return lefthight > righthight ? lefthight + 1 : righthight + 1;
}

bool _IsBalanceTree(Node* root)
{
	if (root == nullptr)
	{
		return true;//空树也是AVL树
	}

	int lefthight = _Hight(root->_left);
	int righthight = _Hight(root->_right);
	int ret = righthight - lefthight;

	//若ret的绝对值>=2，或者与结点的平衡因子不相等，则说明不是AVL树
	if (abs(ret) >= 2)
	{
		cout << root->_kv.first << ":" << "高度有差异" << endl;
		return false;
	}
	if (ret != root->_bf)
	{
		cout << root->_kv.first << ":" << "平衡因子有差异" << endl;
		return false;
	}
	
	//继续往下遍历每个结点，若都是AVL树，则该树就是AVL树
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}