二叉树、二叉搜索树，平衡二叉树（旋转）红黑树（红黑规则）

待我称王封你为后i 2023-10-07 19:49 73阅读 0赞

#### 文章目录 ####

*  3.数据结构
 *   *  3.1二叉树【理解】
     *  3.2 二叉查找树【理解】
     *  3.3平衡二叉树【理解】
 *  3.4 红黑树【理解】

## 3.数据结构 ##

### 3.1二叉树【理解】 ###

*  二叉树的特点
 *  二叉树中，任意一个节点的度要小于等于2  
    \- 节点：在树结构中，每一个元素称之为节点  
    \- 度：每一个节点的子节点数量称之为度
 *  二叉树结构图  
    ![在这里插入图片描述][27337ccf83394cd6b17f85a727d114a4.png]

### 3.2 二叉查找树【理解】 ###

*  二叉查找树的特点
    
     *  二叉查找树，又称二叉排序树或者二叉搜索树
     *  每一个节点上最多有两个子节点
     *  左子树上所有节点的值都小于根节点的值
     *  右子树上所有的节点的值都大于根节点的值
 *  二叉查找树结构图  
    ![在这里插入图片描述][11e9d96cadda4a84916d9cab11bef4c2.png]
 *  二叉查找树和二叉树对比结构图  
    ![在这里插入图片描述][d6bc743254ef4cc4a4f337d49448eaa8.png]
 *  二叉查找树添加节点规则
 *  小的存左边
 *  大的存右边
 *  一样的不存  
    ![在这里插入图片描述][87a861fd47104d86a0ad7e68714e5fb3.png]

### 3.3平衡二叉树【理解】 ###

*  平衡二叉树的特点
    
     *  二叉树左右两个子树的高度差不超过1
     *  任意节点的左右两个子树都是一颗平衡二叉树
 *  平衡二叉树旋转
    
     *  旋转触发时机
        
         *  当添加一个节点之后，该树不再是一颗平衡二叉树
     *  左旋
        
         *  就是将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点。  
            ![在这里插入图片描述][2df12c13436e4f81a19e86073761ffe6.png]
 *  右旋  
    \- 就是将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点  
    ![在这里插入图片描述][e4dd26ca243f4c0fbd08d554c4c01821.png]
 *  平衡二叉树和二叉查找树对比结构图  
    ![在这里插入图片描述][687a815020344fe79e9441f833f1be81.png]
 *  平衡二叉树旋转的四种情况
    
     *  左左
        
         *  左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡
         *  如何旋转：直接对整体进行右旋即可  
            ![在这里插入图片描述][8be97e061fd440a7b2ef2075226110e0.png]
 *  左右
    
     *  左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡
     *  如何旋转：先在左子树对应的节点位置进行左旋，再对整体进行右旋  
        ![在这里插入图片描述][2924a508d087453d84e40e9d9b50bd2f.png]
 *  右右
    
     *  右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡
     *  如何旋转：直接对整体进行左旋即可  
        ![在这里插入图片描述][99cf2ce97bf24a91bde2ade323a50274.png]
 *  右左
    
     *  右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡
     *  如何旋转：先在右子树的对应的节点进行右旋，再对整体进行左旋  
        ![在这里插入图片描述][9a98bcfda07e49b0a6e83889a3c9d8bf.png]

## 3.4 红黑树【理解】 ##

*  红黑树的特点
    
     *  平衡二叉树B树
     *  每一个节点可以是红或者黑
     *  红黑树不是高度平衡的，它的平衡是通过“自己的 红黑规则”进行实现的
 *  红黑树的红黑规则有哪些
    
    1.  每一个节点或是红色的，或者是黑色的。
    2.  根节点必须是黑色
    3.  如果一个节点没有子节点或者父节点，则该节点相应的指针属性为 Nil,这些 Nil 视为根叶节点，每个叶节点（Nil）是黑色的
    4.  如果某一节点是红色的，那么它的子节点必须是黑色的（不能出现两个红色节点相连的情况）
    5.  对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点  
        ![在这里插入图片描述][fb45b03bf5b44fc089e7902a4bd8aceb.png]
 *  红黑树添加节点的默认颜色
 *  添加节点时，默认为红色，红色效率高  
    ![在这里插入图片描述][68bdd3b53a6c4fa6bd6181bdf7b383e7.png]
 *  红黑树添加节点后如何保持红黑规则
    
     *  根节点位置
        
         *  直接变为黑色
     *  非根节点位置
        
         *  父节点为黑色
            
             *  不需要任何操作，默认红色即可
         *  父节点为红色
            
             *  叔叔节点为红色
                
                1.  将“父节点”设为黑色，将“叔叔节点”设为黑色
                2.  将“祖父节点”设为红色
                3.  如果“祖父节点”为根节点，则将根节点再次变成黑色
             *  叔叔节点为黑色
                
                1.  将“父节点”设为黑色
                2.  将“祖父节点”设为红色
                3.  以“祖父节点”为支点进行旋转

[27337ccf83394cd6b17f85a727d114a4.png]: https://img-blog.csdnimg.cn/27337ccf83394cd6b17f85a727d114a4.png
[11e9d96cadda4a84916d9cab11bef4c2.png]: https://img-blog.csdnimg.cn/11e9d96cadda4a84916d9cab11bef4c2.png
[d6bc743254ef4cc4a4f337d49448eaa8.png]: https://img-blog.csdnimg.cn/d6bc743254ef4cc4a4f337d49448eaa8.png
[87a861fd47104d86a0ad7e68714e5fb3.png]: https://img-blog.csdnimg.cn/87a861fd47104d86a0ad7e68714e5fb3.png
[2df12c13436e4f81a19e86073761ffe6.png]: https://img-blog.csdnimg.cn/2df12c13436e4f81a19e86073761ffe6.png
[e4dd26ca243f4c0fbd08d554c4c01821.png]: https://img-blog.csdnimg.cn/e4dd26ca243f4c0fbd08d554c4c01821.png
[687a815020344fe79e9441f833f1be81.png]: https://img-blog.csdnimg.cn/687a815020344fe79e9441f833f1be81.png
[8be97e061fd440a7b2ef2075226110e0.png]: https://img-blog.csdnimg.cn/8be97e061fd440a7b2ef2075226110e0.png
[2924a508d087453d84e40e9d9b50bd2f.png]: https://img-blog.csdnimg.cn/2924a508d087453d84e40e9d9b50bd2f.png
[99cf2ce97bf24a91bde2ade323a50274.png]: https://img-blog.csdnimg.cn/99cf2ce97bf24a91bde2ade323a50274.png
[9a98bcfda07e49b0a6e83889a3c9d8bf.png]: https://img-blog.csdnimg.cn/9a98bcfda07e49b0a6e83889a3c9d8bf.png
[fb45b03bf5b44fc089e7902a4bd8aceb.png]: https://img-blog.csdnimg.cn/fb45b03bf5b44fc089e7902a4bd8aceb.png
[68bdd3b53a6c4fa6bd6181bdf7b383e7.png]: https://img-blog.csdnimg.cn/68bdd3b53a6c4fa6bd6181bdf7b383e7.png