平衡二叉树的定义

二叉查找树的性能要达到最高，树的高度就要最小；满二叉树和完全二叉树的高度都是最小，但是在插入或删除结点后维护其最小高度的代价较大。而平衡二叉树可以说是一种折中的办法，可以兼顾查找和维护性能。

平衡二叉树全称平衡二叉查找树，他是一颗满足一下条件的二叉查找树：

  • 平衡因子的绝对值不超过1
  • 左子树和右子树也满足上面的条件

    解释： 平衡二叉树的平衡因子=左子树高度-右子树高度

IMG_20211116_092631_edit_698356889232778.jpg

平衡二叉树的失衡及调整

当平衡二叉树插入一个结点后，如果导致了某个结点发生了失衡（即平衡因子的绝对值大于1），这时候就需要对这颗进行调整使其继续满足平衡二叉树的特征。一般可以分为下面四种情况：

LL型 - 右旋调整

LL型是指在最小失衡子树（如图中结点A）的左孩子的左子树上插入了新的结点。其调整方案如图所示：
image.png
这种方式也被叫做右旋调整。

算法实现：

  1. void R_Rotate(BBSTree &p) {
  2.     BBSTree lc = p->lchild;  // lc指向p结点的左孩子
  3.     p->lchild = lc->rchild;  // lc结点的右子树置为p结点的左子树
  4.     lc->rchild = p;          // 置p结点为lc结点的右孩子
  5.     p = lc;                  // p指向新的根结点
  6. }

效果图：
image.png

RR型 - 左旋调整

对于RR型，正好与LL型对称，对以A为根的最小失衡子树进行逆时针旋转（也称左旋调整)，如图所示：
image.png
算法实现：

  1. void L_Rotate(BBSTree &p) {   
  2.     BBSTree rc = p->rchild;  //rc指向p结点的右孩子 
  3.     p->rchild = rc->lchild;  //rc结点的左子树置为p结点的右子树 
  4.     rc->lchild = p;          //置p结点为rc结点的左孩子 
  5.     p = rc;                  //p指向新的根结点 
  6. }

效果图：
image.png

LR型 - 左旋右旋调整

LR型指的是最小失衡子树的左孩子的右子树上插入了新的结点。处理办法：首先找到以A为根的最小失衡子树，以该子树的左孩子结点B为轴，对右子树结点C进行左旋调整，使之变为LL型。再以C为轴，对不平衡结点A进行右旋调整。
image.png
效果图：
image.png

RL型 - 右旋左旋调整

LR型指的是最小失衡子树的左孩子的右子树上插入了新的结点。处理办法如图所示，首先找到以A为根的最小失衡子树，以该子树的左孩子结点B为轴，对右子树结点C进行左旋调整，使之变为LL型。再以C为轴，对不平衡结点A进行右旋调整。
image.png
效果图：
image.png

对于上面这四种调整方案，最重要的是记住它们的调整思路而不是算法实现，算法实现其实是比较简单的，只是改变指针的指向即可。

平衡二叉树的插入

有了前面失衡及其调整的基础，在向平衡二叉树插入结点的时候就可以用来调整这颗平衡二叉树了，或者用来构建一棵新的平衡二叉树。构建或插入结点的递归算法思路如下：

  1. 若是空树，则插入的结点作为根结点，树的高度增加1
  2. 若插入的结点和根结点相等，则不能插入，直接返回
  3. 若插入结点小于根结点，并且左子树中的结点的值不等于当前要插入的值，那么就可以把这个结点插入到根结点的左子树，且左子树高度增加1，至于插入后是否需要调整平衡，需要分情况讨论：
  • 若插入前根结点的平衡因子为-1，插入后变为0，整颗树的高度不变，无需调整
  • 若插入前根结点的平衡因子为0，插入后变为1，整颗树的高度+1，无需调整

  • 若插入前根结点的平衡因子为1，插入后变为2，需要调整，而且调整需要分2种情形： 

    1. (1)若左子树的根结点平衡因子为1，则属于LL型，需要右旋调整<br />      (2)若左子树的根结点平衡因子为-1