算法 : 这可能是你看过最简洁的红黑树笔记
👈👈👈 欢迎点赞收藏关注哟
一. 前言
之前其实已经学过几次红黑树了，但是过了一段时间就忘了。
所以这一篇来把这一块好好理一下，目的是能快速回忆起知识点，希望能达到这个目的。
👉👉👉🎈好东西当然要分享 ：一个非常好的红黑树演变网站，用了就不想回来看我的了👈👈👈
这么好的网站应该配得上一个收藏吧！！
二. 红黑树的目的
红黑树的最大目的就是 ： 确保操作的时间复杂度能稳定在对数级别。
其作用主要有以下几点 ：
- 保持树的平衡 ：如果树一直在单边插入，则树会变得不平衡，去查找单边的信息时，会深入很多层，红黑树保证层数不会失衡
- 提高查询的效率 ：如果单边插入，则查询的时间复杂度会从对数级别变成线性级别。红黑树的目的是让查询一直在对数级别
补充知识点 ： 对数级别和线性级别
三. 红黑树的特性
五大规则
-
- 节点只有2种颜色 ：红色和黑色
-
- 根节点是黑色的
-
- 叶子节点是黑色的 （包括 NIL 节点和空节点）
-
- 不能有两个相连的红色节点（红色节点的子节点都是黑色的）
-
- 从任意节点到其每个叶子的路径都包含相同数量的黑色节点
目的解析
来依次解析上面的关键要点 ：
- 问题一 ： 为什么根节点一定是黑色 ?
- 根节点黑色主要是为了配合规则 5 ， 如果根节点是红色，则每个子树都得有一个红色节点或者都没有红色节点
- 规则 3 同理 ，为了保证每个路径上会有相同的黑色高度
- 问题二 ： 左右子节点有大小关系吗？
- 每个节点的 左子节点 的值必定 小于 节点本身的值
- 每个节点的 右子节点 的值必定 大于 节点本身的值
- 问题三 : 为什么不能有相连的红色节点
- 如果没有规则4 （相连红色节点）。则红色节点可能会形成红色链表（一条长红色单链，其他树都没红色节点）
- 问题四 ： 规则 5 能带来哪些好处 ？
- 有限高度 ： 规则 5 保证了根节点到任意叶子节点的路径是相等的
为了达成目的的演变
如果我们一直往右侧不停的递增，那么由于排序要求，右侧树会越来越长，那么自然就会导致平衡的变化，这个时候就会发生左旋和右旋
着重来聊一聊为什么规则5能保证有限高度，首先来看一看极端情况 ：
- S1 : 当我们插入 313 这个数据的时候，按照规约 ， 会挂在 312 的右边
- S2 : 为了保证每条路径需要有相同的黑色节点，就必然需要以红色节点的身份插入
- S3 : 但是由于红色节点不能连续 ，则需要解析变换，变换得到方式就是通过旋转
最终就会形成下面的结构 ：
四. 红黑树的演变方式
演变过程开源在这个网站上面找到，这里演示几种常见的用法 ：
4.1 初级版 ： 3位元素带来的基本变化
这里我隐藏了null节点，如果包含null节点，应该是这样的图形 ：
3个元素的红黑树，最终的效果就是如上图所示，是满足上面的5大规则得到。
同时从遍历的效率上来看，之前遍历到003需要走两步，现在左右都只需要一步就可以完成，达到平衡的要求
4.2 变化 ： 均匀插入新的节点
现在基于这3个位点，衍生出了四种插入方式 ：
由于要保证节点的有序性，所以当均匀的插入一个数据后，节点会自然的按照排序规则自然的排序到指定的位置。
4.3 旋转 ： 当部分分支插入大量的节点
触发选择的条件是红黑树变得不平衡时 ，例如我们一直插入最大的数 ：
我们可以把树形结构想象成一个手链，每个节点都有一定的重量，为了平衡我们会拿着手链的中间，让手链平衡。
- 当手环右边一直变重，为了更平衡，我就需要往右边多拿点，所以我手持的节点就会变成当前节点的右节点
- 而原本手持的节点就会变成最新节点的左节点
而这样就形成了一个旋转的效果，用一个口诀来解释 ：
- 左旋 ： 自己变成右孩子的左孩子，整体结构向左旋转一格
- 右旋 ： 自己变为左孩子的右孩子，整体结构向右旋转一格
左旋
右旋
一直右旋
如果一直往一个方向去添加数据，则会触发更大范围的右旋 ：
五. 扩展知识点
5.1 HashMap 的树形转换
为了解决 Hash 冲突 ，HashMap 在其中引入了红黑树的概念。
Hash 冲突时的数据初始会形成一个链表，当达到一定的阈值后 ，会被转换为红黑树，从而保证查询的下效率。
优势 ： 把一个长链表的查询转为树查询， 又通过红黑树的特点保证了查询的效率和复杂度均衡。
5.2 红黑树和 B+ 树的区别
// 结构
- 红黑树是二叉搜索树，只有2个节点，且有大小顺序
- B+树是多路搜索树，有 n 个节点，同样可以有大小顺序
// 存储方式 ：
- 红黑树通常每个节点都会存储全量数据，所有的键值对（因为每一个都是一个Node）
- B+树例如 MySQL 的结构，节点只会存储关键字，叶子节点才会存储全量数据
// 层级 ：
- 红黑树由于二叉结构，层级会更高，但是每一路的复杂度相同
- B+树每一层有多个节点，使结构变得更加扁平，基于关键字范围，降低了高度提高了查询的效率
总结
好好学习天天向上 ，写的不易且行且珍惜。