【CPP】各种各样的树（5）——AVL树

之前说到在不断地随机插入删除后，二叉树会逐渐变得偏向一边，也就是逐渐右沉，这样的状态会严重地影响二叉树的查找效率。于是乎，我们希望可以构造出一种查找二叉树能在反复插入删除后仍然保持左右平衡，也就是希望左右子树的高度相差不超过1，这种二叉树称为平衡二叉树，而这次的AVL便是要讲的第一种平衡二叉树。

AVL树是最先被发明的自平衡二叉查找树（1962年） ，得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

这里我们要引入的一个新概念就是树的旋转，在这里按照次数分为单旋转和双旋转，按方向分为左旋转和右旋转，如下图，想象树的树枝是活动的，旋转可以很轻松地让树的结点变得平衡。

仔细地理解上面的动图，就会发现树的单旋转其实就是一个交换指针的过程，树的双旋转其实就是对两个结点各自进行了两次方向相反的单旋转。二旋转的方向其实是个对称的过程。然后是声明。

最主要的是Fix函数和两种旋转（方向是对称的）。

旋转本身的编写可能有些混乱，一定要配合图片想象着编写，不要去死记硬背。然后是插入与删除的逻辑，插入与删除需要用到刷新结点高度的函数。

其中主要是要判断左右结点的高度差来判断父结点是否失衡，然后通过失衡的方向来选择旋转的方向，要记得每次改变结点后要刷新一下结点高度。然后对于删除函数，如代码可见，AVL树的删除操作需要类似插入操作的运算量，且也需要较大的编写量，所以当使用AVL树不需要用到太多删除操作时，使用懒惰删除（LazyDelete）是更好的选择，不过平衡的删除操作也要理解。

然后为了表现出树的层次，打印函数选择了带深度的递归打印。测试如下。

AVL树是最早被发明的平衡二叉树，所以它有一些缺陷，但它是很多其他平衡树的变种，这确立了它的学习意义。我们在AVL树中的思想是严格控制子树与子树之间的高度差（深度），但是这种限制使得每次插入删除都要进行复杂的操作来平衡它。一些新的平衡树不再追求这样的条件，它们允许子树有任意的深度，只保证整体的最坏查找时间可控，下次我们来介绍这种平衡树，它是AVL树的一种变种——伸展树（SplayTree）。