【C++】AVL树

AVL树

概念

• AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制⾼度差去控制平衡。

• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962 年的论⽂《Analgorithmfortheorganizationofinformation》中发表了它。

• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balancefactor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1， AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡， 就像⼀个⻛向标⼀样。

• 为什么AVL树是⾼度平衡搜索⼆叉树，要求⾼度差不超过1，⽽不是⾼度差是0呢？不是不想这样设计，⽽是有些情况是做不到⾼度差是0的。⽐ 如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法作为⾼度差是0

• AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 l o g N logN logN ，那么增删查改的效率也可以控制在 O ( l o g N ) O(logN) O(logN)，相⽐⼆叉搜索树有了本质的提升。

这个就不平衡了：

AVL树的实现

结点结构：

以前我们的树结点指针里存放值和左右孩子结点指针，现在多出了一个parent结点以及平衡因子，而且存的值是pair类型的。

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	
	AVLNodeTree<K,V>* _left;
	AVLNodeTree<K,V>* right;
	AVLNodeTree<K,V>* parent;

	int _bf;

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,bf(0)
	{}
	
};

树的大概框架：

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
//……
private:
	Node* _root = nullptr;
};

AVL树的插入

我们可以先写出和原本的区别不大的部分，比如肯定都是先比当前值小就往左走，比当前值大就往右走……

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

我们先停在这一步，接下来我们需要考虑怎么去更改原本存在的结点的平衡因子以及控制平衡的问题，因为新插入的结点的平衡因子肯定是0不需要改，直接用缺省值。

我们现在只做完了第一步。

更新方法预览：

注意更新原则的第2点，只有子树高度变化才会影响当前平衡因子。也就是说对于插入结点的某个祖先来说，如果其实左右子树高度差并没有变化，就没有影响到它的平衡因子，也就是插入一个结点并不一定会影响它的全部祖先。

比如：

对于最上面这个节点来说，原本平衡因子就为-1，插入后还是-1

下图我们可以看到更新平衡因子我们需要倒着往祖先走不断更新直到不需要再更新，所以这就是为什么要在结点里设计parent指针。

有些地方有人没有设计parent。而是通过栈或vector将路径存起来：8 10 14 13。更新的时候就在容器中不断去取。但有parent更便利。parent不是必须的。

更新原则的第3点好理解。

第4点：我们从第3点原则知道插入结点的parent结点的平衡因子是肯定会改变的，要么++要么–，但是是否会继续往上更新，得看parent所在子树的高度是否变化。

如果本来这棵树就没有变高，parent以上的结点的平衡因子就不会改变。

所以接下来的关键问题就是，怎么知道parent所在子树的高度是否变化呢？

仍然以上面这张图为例，我们看更新停止条件的第2点：

更新后parent的平衡因⼦等于1或-1，parent所在子树高度肯定变了。因为这说明parent的平衡因子的变化过程要么是0->1，要么是0->-1，因为根据我们的更新原则的第3点，这个parent的平衡因子要么是++得到的要么是–得到的，说明它原来是0.（倒推思考）因为如果不是这样的话，插入之前根本就不是AVL树了。（我们前提它是一颗AVL树，要插入后继续保持为AVL树）；所以这种情况的高度就增加了，所以**要继续往上更新平衡因子**。

怎么更新呢？

如上图，parent往上走，cur也往上走

可以看到对于现在的parent来说，插入结点是在右子树的，所以平衡因子要++，1->2。

所以现在我们来到了更新停止条件的第3种：更新后parent的平衡因子等于2或-2：同样我们进行倒推，++或者–来到2或者-2，说明原本是1->2或者-1->-2，同样只能是这两种情况，否则原本根本就不是AVL树了。这种情况说明我们的插入结点到了本来就更高的那一边，破坏了平衡，可以说是“雪上加霜”。我们需要旋转处理。旋转之后也不需要再往上继续更新了，因为旋转顶多让它的高度降低1，而原本是AVL树，降低1又变回了AVL树。

我们再来看下面这张图，parent走到3,因为插入结点在其左子树，平衡因子–，也就是**更新后parent的平衡因子等于0的情况：倒推得出是从1->0或者从-1->0的。这说明原本这棵树是一边高一边低，但是现在变成平衡了，所以也不用继续往上更新了**。这种让不平衡的树变平衡了的，可以说“雪中送炭”。

所以如果更新后parent的平衡因子为0，我们才不需要继续更新，否则就要更新。

可以说更新的继续条件是更新后parent的平衡因子为1或-1，而更新停止的条件是更新后parent的平衡因子为0或2或-2.

但在一种情况下，更新后parent的平衡因子为1或-1，却也结束了：

也就是已经更新到根结点的情况。如果parent都已经走到根了，也没法再继续往上更新了。

所以现在我们可以写出平衡因子更新的代码了：

while (parent)
{
	if (parent->_left == cur)
		parent->_bf -= 1;
	else
		parent->_bf += 1;
	if(parent->_bf)

	if (parent->_bf==0)
	{
		break;
	}
	else if (parent->_bf == 1 || parent->_bf == -1)
	{
		cur = parent;
		parent = parent->_parent
	}
	else if (parent->_bf == 2 || parent->_bf == -2)
	{
		//旋转
	}
	else//这是一定不能出现的情况，直接断死
	{
		assert(false);
	}
}

旋转

旋转的原则

1.保持搜索树的规则

2.让旋转的树从不平衡变平衡，其次降低旋转树的高度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋

右单旋

本图1展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要 求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树， 是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/ 图5进⾏了详细描述。

在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平 衡因⼦从-1变成-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要 往右边旋转，控制两棵树的平衡。

旋转核⼼步骤，因为5<b⼦树的值<10，将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新
的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原
则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。

具体来看：

情况1：

h为0

假如abc现在是这种情况，也就是都为空树，插入a后向上调整到10发现平衡因子为-2，所以需要旋转。

怎么旋转？让5的右子树也就是b变成10的左边，10变成5的右子树，就得到了最右边的这种。

相当于把10摁下去了。

这就是抽象的情况之外的具体情况1，是较为简单的一种情况：插入前abc高度都为h而h为0.

情况2：

h为1

这就已经跟抽象的那张图长得十分相似了

可以看到就是把5的右子树变为10的左子树，然后把10变为5的右子树

所以从上面我们可以看出，无论h是0还是1，旋转的逻辑都是一样的。

情况3：

h=2

这就比较复杂了。

如解释，36种情况。

情况4：

h=3

这个又复杂得多了

第三层可以有1个结点，2个，3个，各自有4 、6 、4种情况，一共14种，再加上满二叉树情况，一共15种情况。

bc各有15种情况，所以bc有15*15=256种情况。

我们再来看a的情况：a要保证的是插入了之后自己没有发生旋转（也就是在a子树以上的部分进行旋转），但是高度又变了所以往上调整。

a如果是x这种满二叉树的结构，插入位置有8个。

其次，如果a不是满二叉树的结构，a的结构最后一层必须保留3个结点，否则也无法满足我们要在a插入后自己没有发生旋转但高度又改变的条件。

比如：假设只有1个结点：

如果插入到左下角结点，自身就要旋转了；如果插入到右边3个位置则y-C这棵树的高度并没有变化，也不会引发以上的结点的平衡因子的变化。

我们可以对比一下这两种情况，左边这种是4个结点的左右孩子处都可以插入，也就是8种情况；右边这种是只能在有两个结点的位置插入，因为如果在左边要么就不会引发向上更新要么就自身旋转了。4个结点保留3个有4种情况，每种情况都在有两个结点的那边插入，有4种插入情况（因为有两个节点），所以一共有8+4*4种a的情况。

a的情况*bc的情况就是15 *15(8+4 *4)最终为5400种情况。

这个a的推论就是最复杂的。

不过不论是哪种情况，旋转逻辑都是一样的。

左单旋

是右边更高

图1：

这是一个10为根的树，有a、b、c抽象为三棵高度为h(h>0)的子树，a、b、c均符合AVL树的要求。

我们可以看到，15这个结点的平衡因子是0,10这个节点的平衡因子是1.

10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。

这是一种概括抽象表示，这代表了所有右单旋的场景，实际右单旋形态有很多种。

图2：

可以看到在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2,10为根的树左右高度差超过1，违反平衡规则。所以需要往左边旋转，控制两棵树的平衡。

旋转方式：b变成10的右子树，10变成15的左子树，15成为这棵树的新的根。因为b一定比10大，所以可以成为10的右子树；10比15小，所以可以变成15的左子树。这都满足二叉搜索树规则。

可以看到我们得到的树没有问题。

10、b、c都比15小，所以做它的左子树没有问题。

现在对于15来说，左右子树的高度就一样了。

可以想象成把10这个位置往下摁。

本文结束，下一篇文章讲解具体怎么来写旋转的代码。