【数&C++】图解二叉搜索树&平衡二叉搜索树（AVL树）

向右看齐 2023-02-17 13:29 6阅读 0赞

### 目录 ###

*   *  1. 二叉搜索树
     *   *   *  1.1 概念
             *  1.2 基本操作
             *   *   *  1.2.1 查找
                     *  1.2.2 插入
                     *  1.2.3 删除
             *  3. 特殊情况
     *  2. AVL树
     *   *   *  2.1 概念
             *  2.2 性质
             *  2.3 基本操作
             *   *   *  2.3.1 插入
                     *  2.3.2 旋转 — 左单旋
                     *  2.3.3 旋转 — 右单旋
                     *  2.3.4 旋转 — 左右双旋
                     *  2.3.5 旋转 — 右左双旋

## 1. 二叉搜索树 ##

#### 1.1 概念 ####

*  二叉搜索树的概念：二叉搜索树又称二叉排序树，或者是一棵空树，或者是具有以下性质的二叉树:
    
     *  若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
     *  若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
     *  它的左右子树也分别为二叉搜索树。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70]

#### 1.2 基本操作 ####

###### 1.2.1 查找 ######

*  如下图  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 1]

###### 1.2.2 插入 ######

*  树为空，则直接插入，返回ture；
 *  树不为空，按二叉树搜索树的性质查找插入位置，插入新节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 2]

###### 1.2.3 删除 ######

*  二叉搜索树删除元素，先查找元素是否在搜索树中，若不存在则返回，若存在有以下四种情况：
    
     *  要删除的节点无孩子；
     *  要删除的节点只有左孩子节点；
     *  要删除的节点只有右孩子节点；
     *  删除的节点有左、右孩子节点。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 3]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 4]

#### 3. 特殊情况 ####

*  最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： log2^N；
 *  最差情况下，二叉搜索树退化为单支树，其平均比较次数为： N/2。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 5]

## 2. AVL树 ##

#### 2.1 概念 ####

*  二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树O(n)（两种极端情况），查找元素相当于在顺序表中搜索元素，效率低下；
 *  当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之 差的绝对值不超过1，即可降低树的高度，从而减少平均搜索长度；
 *  高度平衡二叉搜索树（高度差的绝对值不超过1）

#### 2.2 性质 ####

*  一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
    
     *  它的左右子树都是AVL树 ；
     *  左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)，平衡因子=右子树的高度-左子树的高度；  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 6]

#### 2.3 基本操作 ####

###### 2.3.1 插入 ######

*  AVL树的插入过程可以分为两步： 1. 按照二叉搜索树的方式插入新节点；2. 调整节点的平衡因子。

【调节平衡因子】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 7]

###### 2.3.2 旋转 — 左单旋 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 8]

###### 2.3.3 旋转 — 右单旋 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 9]

###### 2.3.4 旋转 — 左右双旋 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 10]

###### 2.3.5 旋转 — 右左双旋 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 11]  
**【小结】**

*  假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑：
    
     *  pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR；
        
         *  当pSubR的平衡因子为1时，执行左单旋；
         *  当pSubR的平衡因子为-1时，执行右左双旋。
     *  pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL；
        
         *  当pSubL的平衡因子为-1是，执行右单旋；
         *  当pSubL的平衡因子为1时，执行左右双旋。
 *  旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200614133847738.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/202006141340570.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200614134018198.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200614134721401.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200614134727823.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200614135219675.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200614140941901.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200614142301412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200614142410158.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/2020061414243331.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200614142723445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200614142856873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70