【数据结构与算法之美】树，二叉树，二叉查找树，平衡二叉查找树（红黑树）

╰半夏微凉° 2023-06-24 08:24 39阅读 0赞

# 树 #

极客时间王争的《数据结构与算法之美》树相关课程笔记

## 节点 ##

根节点，父节点，子节点，兄弟节点，叶子节点/叶节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70]

## 二叉树 ##

每个节点最多两个子节点：左子节点，右子节点  
**满二叉树**  
**完全二叉树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 1]  
满二叉树就是一种完全二叉树

二叉树的存储分两种：**链式存储** 和 **数组存储**

完全二叉树的优势在于用数组存储不浪费空间。  
数组的第0个空着，从第1位开始存根节点，然后每一层从左到右依次存储，每个节点的左子节点在数组中的下标位置是自己下标*2，右子节点自然就是*2+1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 2]  
如上图，一棵完全二叉树，仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 3]

## 遍历 ##

前序，中序，后续遍历  
怎么记住呢，这个前中后就是父节点在前，在中还是在后  
从根节点出发：

*  **前序遍历：** 对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
 *  **中序遍历：** 对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
 *  **后序遍历：** 对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

需要注意，上面描述中不是左节点，右节点，而是**左子树**和**右子树**，这就体现出一个递归的概念了。结合下面的例子理解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 4]

## 二叉查找树 ##

为快速搜索，插入，删除而生  
**每个节点的左子节点必须比自己小，右子节点必须比自己大**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 5]

*  **查找** 从根节点往下一个一个找啦，比节点小就往左，否则往右，数有多少层，最多比较多少次，所以查找的效率完全取决于数的深度。
 *  **插入** 太简单了不说了
 *  **删除**
    
     *  先通过查找定位到节点
     *  如果节点没有子节点：直接删掉
     *  如果节点只有一个子节点：用子节点替代父节点即可
     *  如果有两个子节点，取右子树的最小值代替当前节点
     *  有个通用的取巧的办法，不要删除节点，而是标记删除，这样就是浪费一点空间，但是不增加查找和插入的复杂度，同时大大减小删除的复杂度。

#### 时间复杂度 ####

前面说了查找效率和树的深度有关，最完美的情况就是完全二叉树（深度最小），那怎么知道一棵有n个节点的完全二叉树的深度？  
下面n是节点个数，L是层数，为啥有大于和小于呢，因为最后一层的节点数量在1个到2^(L-1)个之间啦

n >= 1+2+4+8+...+2^(L-2)+1
    n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

反正最后算出来**插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。** 至于怎么算出来的，什么等比数列公式啥的，恕我直言忘得差不多了。

## 二叉查找树 VS 散列表 ##

*  对于二叉查找树，只要你是用中序遍历，就可以有序输出。散列表完全无序。
 *  只要把二叉查找树进化为平衡二叉树，那么它各种操作的复杂度就是稳定的。但散列表不好说，当有很多冲突的时候，性能会下降。
 *  hash函数也是一种消耗
 *  hash表实现难度大，需要考虑冲突，扩容缩容等

## 红黑树 ##

##### 平衡二叉查找树 #####

想想上面的二叉查找数，如果按照从小到大，或者从大到小的顺序插入数据，那画面就很美丽了，直接退化为链表：  
![在这里插入图片描述][2019122210485230.png]  
所以出现了平衡二叉查找树，目的是确保数的深度不会太大，严格的平衡二叉树定义是：  
**任何节点的左右子树高度相差不超过 1**

但是一秒打脸，大名鼎鼎的**红黑树 （R-B Tree）** 并不严格符合平衡二叉树的定义，因为二叉树的维护（插入，删除）和查找效率是需要平衡的，如果严格按照平衡二叉树的定义来做（例如AVL树），虽然查询效率贼高，但是维护的代价很大。红黑树平衡了这两者，所以是另一种含义的“平衡”二叉树了。

**红黑树的定义：**

*  根节点是黑色
 *  红色节点不能相邻
 *  每个节点到它可达叶子节点的路径上，包含相同的黑色节点数量
 *  叶子节点都是黑色，且为null（方便红黑树的实现，图片忽略了这个）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 6]  
    先不论维护的复杂度，先看看如果完全满足红黑树的要求，查找的复杂度如何？  
    先把所有的红色节点干掉，由于定律：**每个节点到它可达叶子节点的路径上，包含相同的黑色节点数量**，干掉红色节点之后会变成一个完全平衡的四叉树，高度肯定比同等节点数量的二叉树低，复杂度也肯定是小于等于log2n。  
    那如果再把红色节点加回来，由于**红色节点不能相邻**，每层黑色节点中间最多夹一层红色节点，所以树的高度最多翻个倍，那复杂度也最多翻倍变成2\*log2n。

## 红黑树的实现 ##

未完待续

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191222091102409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191222091252189.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191222092728124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191222092711285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191222093527806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191222093949875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70
[2019122210485230.png]: https://img-blog.csdnimg.cn/2019122210485230.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191222105710150.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1ODgyNjI=,size_16,color_FFFFFF,t_70