c++：AVL树

1.概念

由于二叉搜索树不能确保为近似完全二叉树的结构，节点相同的情况下，高度可能会很高，高度有可能会很低，所以搜索次数不能稳定维持在logn级别。我们在二叉搜索树的基础上进行平衡调整就可以控制搜索次数稳定在logn级别。

而AVL树就是一个控制了平衡的二叉搜索树。

性质：所有子树都是AVL树，且左右子树的高度差都不超过1

平衡因子： 用当前根节点的右子树高度减去左子树高度 （也可以左减右，不过相应的逻辑也要反过来） ，得到的值可以为0/1/-1，那么这个值就是当前根节点的平衡因子大小

有了平衡因子之后我们就可以很直观的知道这棵树是不是平衡的

2.AVL树部分结构实现

2.1框架构建

（1）节点

（2）AVL树

2.2插入

2.2.1总体过程

AVL树（二叉平衡搜索树）插入的大概过程：

1.按照搜索二叉树的规则进行插入 （保证是二叉搜索树）

2.更新祖先节点的平衡因子，最坏的情况需要更新到根节点

情况1：若没有出现失衡节点 ，那么更新完平衡因子后就结束插入

情况2：若出现了失衡节点 ，那么需要根据具体情况进行旋转，旋转的本质是将高度降低，让祖先节点平衡因子不改变，从而控制平衡因子变化只在局部

2.2.2平衡因子更新

原则：

1.平衡因子 = 右子树高度 - 左子树高度

2.只有子树高度变化才会影响根节点的平衡因子

推论：

1.节点插入侧为空

2.结点右侧插入节点，根节点平衡因子++,左侧插入节点，根节点平衡因子–

3.若根节点平衡因子从-1/1变为0，则不用向上更新平衡因子

4.若根节点平衡因子从0变为1/-1，则需要向上更新平衡因子

5.更新后父节点为2/-2，则进行旋转，旋转后也不需要向上更新平衡因子

解释：

推论2： 由于平衡因子是右子树高度减左子树高度，而结点右侧插入节点会导致右子树高度++，而左子树高度没变化，从而根节点平衡因子++。左侧插入同理

图示：

推论3： 若根节点一开始平衡因子为-1/1，且插入后平衡因子变为0，说明原本有一侧存在节点，插入后左右两侧高度相同，对于根节点的祖先节点来说子树高度没变，不用更新平衡因子。

图示：

推论4： 一开始平衡因子为0，说明原本根节点两侧为空，插入后平衡因子变为-1/1，说明左右任意一侧插入了节点，高度变化了，此时对于根节点的父节点来说左右子树高度差变化，平衡因子也会变化，所以局部没有控制高度不变，需要把根节点当成新的cur节点，根节点的父节点当成新的父节点进行判断

图示：

1.

2.

2.2.3插入节点与平衡因子更新

（1）按照搜索二叉树的逻辑插入cur节点

由于我们在AVL树引入了父节点在树的节点中，所以这里插入后还需要维护_parent指针指向

（2）平衡因子更新

第一步：更新父节点平衡因子

根据插入节点cur的位置判断平衡因子++还是–

虽然理论上我们的parent只可能左侧指向cur或者右侧指向cur，但是不能确保前面的代码是否有问题，所以我们还需要assert检查一下

第二步：向上更新祖先节点的平衡因子

分三种情况：

1.父节点平衡因子为0，说明parent为根节点的树高度没变，不用向上更新

2.父节点平衡因子为1、-1，说明当前局部树高度变了，但是没失衡，向上更新。

注意：如果中途更新完了就没事，如果最后根节点也是-1/1就直接退出，所以我们的循环结束条件是parent不为nullptr

3.父节点平衡因子为2/-2，说明节点失衡，进行旋转，然后不用向上更新

2.2.4 旋转

旋转的原则：

1.旋转后满足搜索树关系

2.将树的高度变回插入前，从不平衡变平衡

（1）右单旋：父节点和cur节点都是左树高于右树

图示：

提示：所有矩形方框都表示满足AVL树结构的树

（1）插入前节点情况

整棵树的高度为h+2

(2）插入后节点情况

（3）旋转后情况

旋转之后不存在失衡因子，且整棵树的高度变回了插入前的h+2，从而局部树高度无变化，不用向上更新。

旋转方式：失衡节点往下扭，新局部根节点的右子树给到失衡节点的左子树

这种旋转方式可以满足搜索树的关系， 且可以让不平衡的树变平衡，整个树的高度也和插入之前一样。

从局部来看： 让局部树变平衡了

从全局来看： 没有继续向上影响祖先节点的平衡因子

右单旋前提：

parent的平衡因子为-2，cur的平衡因子为-1

右单旋实现：

一共分为三步

第一步：创建subl与sublr变量并改变节点的指向

subl相当于图示中的1，sublr相当于图示中的1的右子树

第二步：更新父节点指向

对于parent来说很明确，直接指向subl即可

对于sublr：由于sublr是可能为空的，所以我们需要在sublr不为空的前提下更新其父节点

对于subl：他现在变成了新的根节点，但是不确定他是局部根节点还是全局根节点。

若为全局：parentParent就为空，我们改变根节点为subl，且更新subl的父节点为nullptr

若为局部：将parentParent指向parent的那一侧指向subl

第三步：更新平衡因子

只有subl和parent的树高度发生了变化，且最后平衡因子都变为了0。

（2）左单旋：父节点和cur节点都是右树高于左树

与右单旋同理，将对应操作翻转即可

图示：

（1）插入前

（2）插入后

（3）旋转后

左单旋前提：

parent平衡因子为2，cur平衡因子为1

左单旋实现：

（3）左右双旋：父节点是左树更高，cur节点是右树更高

左右双旋分为三种情况：

总图示：

我们在这种情况下单次旋转式无法解决问题的，所以我们需要进行两次旋转，而旋转需要我们将h+1处的树展开才能进行第一次旋转

我们将1右侧的AVL树拆开后就可以根据h的大小和节点插入位置分成三种情况

情况1图示：h>0且节点插入在左侧

bf1: 1    bf2:-1   bf3：-2

左旋后：

右旋后：

bf1 : 0   bf2:0   bf3:1

情况2图示：h>0且节点插入在右侧

bf1:1 bf2:1 bf3:-2

左旋后：

右旋后：

bf1:-1 bf2:0 bf3:0

情况3图示：h==0,节点直接插入

bf1: 1   bf2: 0   bf3:-2

左旋后：

右旋后：

bf1: 0   bf2: 0   bf3:0

旋转方式：先以cur节点为根节点左旋，然后以parent为根节点右旋

左右双旋前提：

parent的平衡因子为-2，cur的平衡因子为1

左右双旋实现：

(1)进行旋转

由于三种情况中不同的部分就是sublr的平衡因子，所以我们可以先记录sublr的平衡因子，然后根据他的值将三种情况分别处理

（2）根据三种调整平衡因子

由于右旋和左旋的代码中把双旋情况下不应该置为0的平衡因子变为了0，所以我们后面需要对parent和subl，sublr的平衡因子统一修改

最后也需要把特殊情况进行处理，如果bf不是0.1.-1的这三种情况，那么我们就要报错

（4）右左双旋：父节点是右树更高，cur节点是左树更高

和左右双旋同理

右左双旋前提：

parent的平衡因子为2，cur的平衡因子为-1

代码实现：