数据结构之动态查找树（二叉查找树，平衡二叉树，红黑树）

系统管理员 2022-11-15 11:24 277阅读 0赞

### 数据结构之树 ###

*   *  1、二叉树
     *   *  1.1、二叉树定义
         *  1.2、二叉树性质
         *  1.3、二叉树遍历方式
     *  2、二叉查找树
     *   *  2.1、查找
         *  2.2、添加
         *  2.3、删除
     *  3、平衡二叉树
     *   *  3.1、平衡调整
         *   *  3.1.1、LL型调整
             *  3.1.2、RR型调整
             *  3.1.3、LR型调整
             *  3.1.4、RL型调整
         *  3.2、查找
         *  3.3、添加
         *  3.4、删除
     *  4、红黑树
     *   *  4.1、性质
         *  4.2、查找
         *  4.3、添加
         *  4.4、删除
     *  5、往期佳文
     *   *  5.1、面试系列
         *  5.2、技术系列
         *  5.3、源码系列
         *  5.4、数据结构和算法系列

## 1、二叉树 ##

### 1.1、二叉树定义 ###

二叉树是一种每个结点至多只有两个子树（即二叉树的每个结点的度不大于2），并且二叉树的子树有左右之分，其次序不能任意颠倒。

### 1.2、二叉树性质 ###

A、在二叉树的第i层上最多有2^(i-1)个结点（i>=1）。  
       B、高度为k的二叉树，最多有2^k-1个结点（k>=0）。  
       C、对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则n = m + 1。  
       D、具有n个结点的完全二叉树的高度为logn + 1  
       E、对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右）  
              a、若i为结点编号则 如果i>1，则其父结点的编号为\[i/2\]，\[i/2\]是往下取整的；  
              b、如果2i<=N，则其左儿子（即左子树的根结点）的编号为2i；若2i>N，则无左儿子；  
              c、如果2i+1<=N，则其右儿子的结点编号为2i+1；若2i+1>N，则无右儿子。

### 1.3、二叉树遍历方式 ###

1.  先序遍历：先根节点->遍历左子树->遍历右子树
2.  中序遍历：遍历左子树->根节点->遍历右子树
3.  后序遍历：遍历左子树->遍历右子树->根节点  
    ![在这里插入图片描述][20210331162121825.png]

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

## 2、二叉查找树 ##

二叉搜索树大致定义为二叉树的左子树任意节点的值小于根节点的值，右子树任意节点的值大于根节点的值，并且左子树、右子树同样也符合二叉搜索树的定义（递归定义）。中序遍历顺序为左根右，所以二叉搜索树的典型特征是中序遍历序列有序。

### 2.1、查找 ###

二叉搜索树设计成左 < 根 < 右（中序遍历有序），一个很重要的动机就是快速查找。有过一点算法基础的应该能想到有一种搜索策略非常相似，没错就是二分搜索，每次将target与搜索区间（递增有序）的中间值mid比较，如果target < mid则缩小搜索区间为\[left, mid - 1\],如果target > mid则缩小搜索区间为\[mid + 1, right\],否则target == mid。

### 2.2、添加 ###

二叉搜索树中查找充分利用左 < 根 < 右特性，辣么插入也能用上这个特性么？答案是显然的。  
       首先思考一下，我们插入节点后是不是还需要维持二叉树仍然满足二叉搜索树特性，这是必须的，要不能你的二叉搜索树就变成一次性的了。辣么我们就先要找到它真实应该插入的位置，保证中序遍历为递增有序。

### 2.3、删除 ###

删除非叶节点可以细分为两种，第一种是删除有右子树的节点，删除节点后需要将右子树中序遍历第一个节点填充到删除节点A位置（为什么选右子树中序遍历第一个节点？因为整棵树的中序遍历序列中，节点A的下一个节点就是其右子树中序遍历的第一个节点）。  
       右子树中序遍历第一个节点为某个节点的左子节点，直接将最左的左子节点填补到已删除节点的位置。  
       其实根本不需要进行删除操作，只要寻找到这个节点中序遍历序列的下一个节点，然后直接替换即可

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

## 3、平衡二叉树 ##

平衡二叉搜索树，又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

### 3.1、平衡调整 ###

#### 3.1.1、LL型调整 ####

由于在A的左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。下面图1是LL型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]

#### 3.1.2、RR型调整 ####

由于在A的右孩子®的右子树®上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图3是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 1]

#### 3.1.3、LR型调整 ####

由于在A的左孩子(L)的右子树®上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。图5是LR型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 2]

#### 3.1.4、RL型调整 ####

由于在A的右孩子®的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图7是RL型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 3]

### 3.2、查找 ###

与二叉查找树一致

### 3.3、添加 ###

添加一个数的时候，判断该树有没有节点的平衡因子区间不在\[-1,1\]之间的，存在就需要调整。调整方式如上图4种。  
外部优秀文章：[外部链接][Link 1]

### 3.4、删除 ###

1.如果左右子树均不为空,且左子树比右子树高，找出结点的左子树中的最大结点，将最大结点的值赋值给该结点(左子树的父亲)，用结点的左子树的最大结点的值替换要删除的结点的值。  
       2.如果左右子树均不为空,且右子树比左子树高，找出结点的右子树的最小结点，将最小结点的值赋值给该结点(右子树的父亲)。  
       这样做的用意是,删除结点左子树的最大结点后,AVL树仍然满足二叉搜索树的性质:任意结点的左孩子均不大于根结点，任意结点的右孩子均不小于根结点

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

## 4、红黑树 ##

红黑树是一棵二叉搜索树，并且这棵树实现了弱平衡（严格的平衡是对于树中任意节点的左右子树高度差不超过1）。弱平衡是指任意节点到到其子树中的叶节点所经过的黑色节点数相同，也可以称为黑色平衡（因为严格平衡的二叉搜索树AVL，维护成本太高，所以退而求其次）。

### 4.1、性质 ###

1.  节点是红色或者是黑色
2.  根节点是黑色
3.  每个叶节点（NIL或空节点）是黑色
4.  每个红色节点的两个子节点都是黑色的
5.  任意节点到其子树中的叶节点（NIL节点）所经过的黑色节点数相同（黑高相同）  
    外部优秀文章：[外部链接][Link 2]

### 4.2、查找 ###

与二叉查找树一致

### 4.3、添加 ###

根据性质先调整结构，再调整颜色

### 4.4、删除 ###

与二叉查找树相同的方式，保持黑高一致或者少1，并且调整颜色。

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

## 5、往期佳文 ##

### 5.1、面试系列 ###

1、[吊打面试官之一面自我介绍][Link 1]  
2、[吊打面试官之一面项目介绍][Link 3]  
3、[吊打面试官之一面系统架构设计][Link 4]  
4、[吊打面试官之一面你负责哪一块][Link 5]  
5、[吊打面试官之一面试官提问][Link 6]

······持续更新中······

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

### 5.2、技术系列 ###

1、[吊打面试官之分布式会话][Link 7]  
2、[吊打面试官之分布式锁][Link 8]  
3、[吊打面试官之乐观锁][Link 9]  
4、[吊打面试官之幂等性问题][Link 10]  
5、[吊打面试关之分布式事务][Link 11]  
6、[吊打面试官之项目线上问题排查][Link 12]

······持续更新中······

### 5.3、源码系列 ###

1、[源码分析之SpringBoot启动流程原理][SpringBoot]  
2、[源码分析之SpringBoot自动装配原理][SpringBoot 1]  
3、[源码分析之ArrayList容器][ArrayList]  
4、[源码分析之LinkedList容器][LinkedList]

### 5.4、数据结构和算法系列 ###

1、[数据结构之八大数据结构][Link 13]

······持续更新中······

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

[20210331162121825.png]: /images/20221022/b93713171d6c40a8a6ea35439031cb74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210331220500237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210331220743846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210331220858765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210331220941271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ==,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/wtyicy/article/details/114933478
[Link 2]: https://hestyle.blog.csdn.net/article/details/105596199
[Link 3]: https://blog.csdn.net/wtyicy/article/details/114983053
[Link 4]: https://blog.csdn.net/wtyicy/article/details/115005012
[Link 5]: https://blog.csdn.net/wtyicy/article/details/115064661
[Link 6]: https://blog.csdn.net/wtyicy/article/details/115296365
[Link 7]: https://blog.csdn.net/wtyicy/article/details/114685293
[Link 8]: https://blog.csdn.net/wtyicy/article/details/114915987
[Link 9]: https://blog.csdn.net/wtyicy/article/details/114915177
[Link 10]: https://blog.csdn.net/wtyicy/article/details/114888754
[Link 11]: https://blog.csdn.net/wtyicy/article/details/115081790
[Link 12]: https://blog.csdn.net/wtyicy/article/details/115292969
[SpringBoot]: https://blog.csdn.net/wtyicy/article/details/115181539
[SpringBoot 1]: https://blog.csdn.net/wtyicy/article/details/115233701
[ArrayList]: https://blog.csdn.net/wtyicy/article/details/115244565
[LinkedList]: https://blog.csdn.net/wtyicy/article/details/115314536
[Link 13]: https://blog.csdn.net/wtyicy/article/details/115342236