《数据结构》—— 平衡二叉树的定义、插入及最小不平衡子树处理

清疚 2022-09-15 13:54 173阅读 0赞

### 平衡二叉树 ###

*   *  一、平衡二叉树的定义
     *  二、平衡二叉树的插入
     *  三、平衡二叉树的平衡处理
     *   *  3.1 调整最小不平衡子树（LL）
         *  3.2 调整最小不平衡子树（RR）
         *  3.3 调整最小不平衡子树（LR）
         *  3.4 调整最小不平衡子树（RL）
     *  四、ASL查找效率分析

## 一、平衡二叉树的定义 ##

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的**左、右子树高度差**的绝对值不超过1，将这样的二叉树称为平衡二叉树(Balanced Binary Tree)，简称**平衡树**。

结点的平衡因子 = 左子树高-右子树高。

定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是一-1、0或1。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]

## 二、平衡二叉树的插入 ##

我们要思考在二叉排序树中插入新结点后，如何保持平衡？  
插入新结点后，查找路径上的所有结点都有可能受到影响，使得平衡因子的值会超过1。那我们怎么办呢？

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
如上图，首先从插入点67往回找到第一个不平衡结点70，调整该结点作为根的子树，这个子树我们称为是 **“最小不平衡子树”** 。

接下来我们只需将最小不平衡子树调整为平衡即可，中序为67->68->70。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]

--------------------

## 三、平衡二叉树的平衡处理 ##

导致不平衡的插入总结有4种情况。

### 3.1 调整最小不平衡子树（LL） ###

![在这里插入图片描述][3defda0b13524fceae1a41603a5eb11f.png]  
在结点A的左孩子(L)的左子树(L)上插入了新结点，导致不平衡。如上图，插入之后 B的左子树BL高为H+1，其他子树高是H，根节点A的平衡因子为2，出现不平衡情况。这时候我们就要进行一次**向右的旋转操作：**

*  将A的左孩子B向右上旋转代替A成为根结点；
 *  将A结点向右下旋转成为B的右子树的根结点；
 *  而B的原右子树则作为A结点的左子树。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
设指针f指向根结点A，指针p指向A的左子树B结点，gf指针指向A的父结点；

实现f向右下旋转，p向右上旋转;
    其中f是爹，p为左孩子，gf为f他爹;
    f->lchild = p->rchild;
    p->rchild = f;
    gf->lchild/rchild = p;
    
    由于BL<B<BR<A<AR，左旋、右旋操作后可以保持二叉排序树的特性。

--------------------

**为什么要假定所有子树的高度都是H？**

*  假如A的右子树AR高为H+1，那当BL插入结点，使得高为H+1时，A的平衡因子=(BL+1)-AR=(H+2) - (H+1) =1，满足平衡条件！！！
 *  假如A的右子树AR高为H-1，BL本身高为H，A的平衡因子=(BL+1)-AR=(H+1) - (H-1) =2，在还没插入结点时，根节点A本身就不满足平衡条件！！
 *  综上，所有子树的高度必须都是同高H才行。

--------------------

### 3.2 调整最小不平衡子树（RR） ###

![在这里插入图片描述][70dd7ebfc7de4515a1cc6ac1494c6710.png]  
在结点A的右孩子®的右子树® 上插入了新结点，导致不平衡。如上图，插入之后 B的右子树BR高为H+1，其他子树高是H，根节点A的平衡因子=AL-(BR+1)=H-(H+1+1)=-2，出现不平衡情况。这时候我们就要进行一次**向左的旋转操作：**

*  将A的右孩子B向左上旋转代替A成为根结点；
 *  将A结点向左下旋转成为B的左子树的根结点；
 *  而B的原左子树则作为A结点的右子树。

![在这里插入图片描述][2a1fa2803ab84b8d841e17f671df1ee2.png]  
设指针f指向根结点A，指针p指向A的左子树B结点，gf指针指向A的父结点；

实现f向左下旋转， p向左上旋转;
    其中f是爹，p为右孩子，gf为f他爹;
    f->rchild = p->lchild;
    p->lchild = f;
    gf->lchild/rchild = p;
    
    由于AL<A<BL<B<BR，左旋、右旋操作后可以保持二叉排序树的特性。

--------------------

### 3.3 调整最小不平衡子树（LR） ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
如上图，在A的左孩子B的右子树(BR)上插入新结点，A的平衡因  
子=BR+1-AR=2，导致以A为根的子树失去平衡。我们可以拆分来看，以B为根节点的最小不平衡子树来看，是一个RR操作，需要一次**左旋操作**；作为根节点A的最小不平衡子树来看，是一个LL操作，需要一次**右旋操作**。

因此，调整最小不平衡子树（LR）**需要进行两次旋转操作:（先左后右双旋转):**

*  先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置；
 *  然后再把该C结点向右上旋转提升到A结点的位置。  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 5]

--------------------

### 3.4 调整最小不平衡子树（RL） ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
如上图，在A的右孩子B的左子树(BL)上插入新结点，A的平衡因  
子=AL-(BL+1)=-2，导致以A为根的子树失去平衡。我们可以拆分来看，以B为根节点的最小不平衡子树来看，是一个`LL操作`，需要一次**右旋操作**；作为根节点A的最小不平衡子树来看，是一个`RR操作`，需要一次**左旋操作**。

因此，调整最小不平衡子树（RL）**需要进行两次旋转操作:(先右后左双旋转)：**

*  先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置；
 *  然后再把该C结点向左上旋转提升到A结点的位置。

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
总之在插入操作中，只有将最小不平衡子树调整平衡，则其他祖先结点都会自然而然的恢复平衡。

--------------------

## 四、ASL查找效率分析 ##

若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O(h)。  
平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1。  
假设以 **N***h* 表示深度为h的平衡树中含有的最少结点数。则有n0 = 0, n1 = 1, n2 = 2，并且有**N***h* = **N***h-1* \+ **N***h−2* \+ 1，可以证明含有n个结点的平衡二叉树的最大深度为O(log2n) ，平衡二叉树的平均查找长度为O(log2n)。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
**例如：T4 = T3 +T2 +1 = 9+4+1 = 14**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7525525ea58e4b76a9610dc9e1403037.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e72a192d119b4961b5d007505cfa638e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/32b09bce06cf49689cf49221f31f2730.png
[3defda0b13524fceae1a41603a5eb11f.png]: /images/20220828/cc31c6c018ba4423b23b0f7369b0b40b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/097493db751242a9badd06e3e1a547b3.png
[70dd7ebfc7de4515a1cc6ac1494c6710.png]: /images/20220828/8613968daf56410b80daf7b66d961f04.png
[2a1fa2803ab84b8d841e17f671df1ee2.png]: /images/20220828/11051333026644029355474d274d9075.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/dbaf29cc92e146d0a11a3216cbbfd600.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/526c4b7cd45649a2b88b69198af33e04.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/75ced1aaabbe4e1f8852c52ec689b4c2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/972961b993674f92bf2fd8e641bb5169.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/b43a9102281a497ba59ecb3dd3f0bafc.png