树

平衡二叉树

定义

  我们知道，在利用树形查找时，树的高度会影响查找的效率。因此，在构建树的过程中，为了避免树的高度增长过快，降低二叉排序树的性能，我们通常会要求任意节点的左右子树高度之差(绝对值)不超过1。这样的树便被称为平衡二叉树，又名AVL树。

  注意:平衡二叉树是特殊的二叉排序树!

平衡因子

  左右子树高度之差，我们便称之为平衡因子，平衡二叉树的平衡因子只可能为-1 , 0 , 1。

如何区分平衡与不平衡？

  下面是一组平衡二叉树和非平衡二叉树的对比图:

  在上图的非平衡二叉树中，节点2的左子树高度为3,右子树的高度为1,两边子树高度只差(平衡因子)的绝对值为2,超过了最大值1，因此这是一颗不平衡子树。而左边的平衡二叉树中的所有节点的平衡因子都不超过1。

平衡二叉树的插入

  那么了解了AVL树的定义后，我们都能联想到一个问题:如果对AVL树进行插入操作的话，那是不是很有可能会破坏树的平衡状态?例如我在上图中的平衡二叉树中的第四层的叶子节点0下再插入一个节点，那么这棵树的平衡状态就会被破坏了，因为节点-1的左子树高度为1，而右子树的高度为3，平衡因子显然大于1。

  那么有什么办法能够既能够插入数据，插入的数据不改变二叉排序树的性质，又不影响平衡二叉树的性质呢？很遗憾，是没有的。所以我们只能在插入数据后检查是否破坏了平衡性，若是不平衡的话则对最小不平衡树进行调整。(最小不平衡树:距离插入节点最近的，且平衡因子绝对值大于1的节点，以该节点为根节点构成的子树)。然而，在不同位置插入数据，所需要进行的调整也是不同的，调整的情况分为LL,LR,RL,RR。

LL旋转 (需要向右进行一次旋转)

  在最小不平衡子树中，由于在节点A的左(L)孩子的左(L)子树上插入了新节点导致失去了平衡，因此需要进行一次向右的旋转操作。


  如图(节点旁的数字代表平衡因子):A的左孩子B向右上旋转代替A成为根节点，A向右下旋转成为B的右孩子，而B的原右子树则成为A的左子树。整个过程节点都是向右旋转，因此也叫做右旋。

  这样调整的思路是，增高高度较小的一方子树，缩小高度较高的一方子树。如何缩小高度？通过增加节点的分支(由单分支变为双分支)，再通过调整节点的位置使得其符合二叉排序树(左<根<右)的性质。

RR旋转(向左进行一次旋转)

  在最小不平衡子树中，由于节点A的右(R)孩子的右(R)子树上插入了新节点,导致以A为根节点的子树失去平衡，需要一次向左的旋转操作。


  如图，将A的右孩子向左上旋转代替A成为根节点，将A向左下旋转成为B的左孩子，而B的原左子树则作为A的右子树。

LR旋转(向左进行一次旋转后向右进行一次旋转)

  在最小不平衡子树中，由于节点A的左孩子(L)的右子树(R)插入了新的节点，导致以A节点为根的子树失去平衡，需要进行两次旋转操作，先向左旋转然后向右旋转。


  如图，先将A的左孩子B的右子树的根节点C向左上旋转至B的位置，然后把节点C向上旋转提升到A的位置。

RL旋转(先右旋后左旋)

  在最小不平衡子树中，由于在A的右(R)孩子的左(L)子树上插入新的节点，导致以A节点为根的子树失去平衡，需要进行先右旋后左旋操作哦


  先将A的右孩子B的左子树的根节点C向右旋转上升到B的位置，然后把C向左上旋转上升到A的位置

如何记忆操作流程

  总结的规律为:

    (1)所有的操作都是和字母反着来的L的话就是右旋，R的话就是左旋

    (2)LL和RR只需要重复的执行两次旋转操作就行，而LR和RL则是需要分别执行先右旋后左旋以及先左旋后右旋的操作

    (3)先调整根节点的孩子，向上调整至根节点的位置。后调整根节点，向下调整至其孩子的位置。

    (4)调整后，根节点A变为孩子节点，原根节点孩子方向上的子树调整为调整后的A的孩子，究竟是位于左孩子还是右孩子则取决于旋转时的方向(或根据二叉排序树:左<根<右的性质判断)。