史上最易懂的红黑树动态图解！

点击蓝色“程序猿DD”关注我

回复“资源”获取独家整理的学习资料！

俺家司令买完东西后，我俩经常会发生这样的一段对话:

司令:你猜我买的这个多少钱em>我: 1000司令: 高了我: 500司令: 低了:我: 750…… 直到最后猜中

这样说大家应该已经猜到了是「二分查找法」，通过这个例子我想要引出的是 树，来看图片

二叉查找树 

二叉查找树，Binary Search Tree 「BST」，要想了解二叉查找树，我们首先看下二叉查找树有哪些特性呢/span>

1. 某节点的左子树节点值仅包含小于该节点值

2. 某节点的右子树节点值仅包含大于该节点值

3. 左右子树每个也必须是二叉查找树

看个图就轻松理解上面三句话的意思了:

上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗/span>

1. 这是一个走路一米六，一米八的树

2. 这是一个畸形的树，大风一挂很可能被折断的树

从程序的角度来说这个树不够平衡，查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长

理科生在高中学习生物时学过一个关键字「去除顶端优势」，通过去除植物顶端优势，侧芽会迅速生长，慢慢变得强壮和平衡， 红黑树其实就是去除二叉查找树顶端优势的解决方案，从而达到树的平衡

红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

1. 每个节点都有红色或黑色

2. 树的根始终是黑色的 (黑土地孕育黑树根，

3. 没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，并没有说不能出现连续的黑色节点）

4. 从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

瞬间懵逼strong style=”color:rgb(0,0,0);”>了解一下印象就行，开始玩魔方都是要照着魔方公式一点点玩的，多玩几次就熟悉了。红黑树也一样，红黑树有两大操作:

1. recolor (重新标记黑色或红色)

2. rotation (旋转，这是树达到平衡的关键)

我们会先尝试 recolor，如果 recolor 不能达到红黑树的 4 点要求，然后我们尝试 rotation，其实红黑树的关键玩法就是弄清楚 recolor 和 rotation 的规则，接下来看看详细的算法公式吧 千万别着急记忆公式，有图示会逐步说明，就像魔方一样，多玩几次就懂了:假设我们插入的新节点为 X 

• 1. 将新插入的节点标记为红色

• 2. 如果 X 是根结点(root)，则标记为黑色

• 3. 如果 X 的 parent 不是黑色，同时 X 也不是 root:

  • 3.1.1 将 parent 和 uncle 标记为黑色

  • 3.1.2 将 grand parent (祖父) 标记为红色

  • 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同，然后重复步骤 2、3

  • 3.1 如果 X 的 uncle (叔叔) 是红色

跟着上面的公式走:

1. 将新插入的 X 节点标记为红色

2. 发现 X 的 parent (P) 同样为红色，这违反了红黑树的第三条规则「不能有两个连续相邻的红色节点」

3. 发现 X 的 uncle (U) 同样为红色

4. 将 P 和 U 标记为黑色

5. 将 X 和 X 的 grand parent (G) 标记为相同的颜色，即红色，继续重复公式 2、3

6. 发现 G 是根结点，标记为黑色

7. 结束

刚刚说了 X 的 uncle 是红色的情况，接下来要说是黑色的情况

• 3. 如果 X 的 parent 不是黑色，同时 X 也不是 root:

  • 3.2.1 左左 (P 是 G 的左孩子，并且 X 是 P 的左孩子)

  • 3.2.2 左右 (P 是 G 的左孩子，并且 X 是 P 的右孩子)

  • 3.2.3 右右 (和 3.2.1 镜像过来，恰好相反)

  • 3.2.4 右左 (和 3.2.2 镜像过来，恰好相反)

  • 3.2 如果 X 的 uncle (叔叔) 是黑色，我们要分四种情况处理

当出现 uncle 是黑色的时候我们第一步要考虑的是 旋转 ，这里先请小伙伴不要关注红黑树的第 4 条规则，主要是为了演示如何旋转的，来一点点看，不要看图就慌，有解释的

左左情况

这种情况很简单，想象这是一根绳子，手提起 P 节点，然后变色即可

左右

右右

右左

你说的动图在哪里，你个大骗子，别着急，现在就为小伙伴们奉上动图演示，来说明公式的使用:

案例一

插入 10，20，30，15 到一个空树中

1. 向空树中第一次插入数字 10，肯定是 root 节点

2. root 节点标记成黑色

1. 向树中插入新节点 20，标记为红色

2. 20 > 10，并发现 10 没有叶子节点，将新节点 20 作为 10 的右孩子

1. 向树中插入新节点 30，标记为红色

2. 30 > 10，查找 10 的右子树，找到 20

3. 30 > 20，继续查找 20 的右子树，发现 20 没有叶子节点，将值插在此处

4. 30 和 20 节点都为红色，30 为右孩子，20 也为右孩子，触发了 右右情况

5. 通过一次旋转，提起 20 节点

6. 20 节点是根结点，标记为黑色

1. 向树中插入新节点 15，标记为红色

2. 通过比对大小和判断是否有叶子节点，最终插值为 10 节点的右孩子

3. 15 和 10 节点都为红色，15 的 uncle 节点 30 也为红色

4. 按照公式，将 15 的 parent 10 和 uncle 30 更改为黑色

5. 让 15 节点 grand parent 20 的颜色与 15 节点的颜色一样，变为红色

6. 20 为根结点，将其改为黑色

继续插入其他节点只不过反复应用上面的公式，上面应用到的红黑树工具，可以暂停动画效果，一帧一帧的看红黑树的转换过程，这样通过练习，查看公式，观察变化三管齐下，红黑树的入门理解应该完全不再是问题了

留言交流不过瘾/span>添加微信：zyc_enjoy

根据指引加入各种主题讨论群

每日一问

今日问题：

妈妈准备款待客人的糖果被偷吃了。妈妈很生气，盘问4个孩子，下面是他们的回答：

A：是B吃的。

B：是D吃的。

C：我没有吃。

D：B在说谎。

妈妈不知道如何惩罚这群淘气的孩子，便询问知道详情的爸爸。孩子们用哀怜的眼神看着爸爸，希望爸爸不要“出卖”他们。于是，爸爸微笑着对妈妈说：“亲爱的，不要生气了。我想他们也是一时没有管住自己的嘴。不过我不能出卖自己的孩子们，所以，我要告诉你的是，他们中有一个说了实话，有三个说了谎话。”结果，妈妈还是知道究竟是谁偷吃了糖果。你知道是谁吗/span>

（留言说说你的答案吧，明日推文公布答案）

昨日答案：312211

（昨日问题可在昨日推文的文末查看）

推荐阅读

• Spring Cloud Alibaba即将正式毕业，Netflix之后新生力量值得期待！

• RabbitMQ 延迟消息的极限是多少/span>

• Spring、Spring MVC、Spring Boot还傻傻分不清楚/span>

• 可能是全 最好的MySQL重要知识点 | 面试必备

• 开发高质量的软件要付出什么样的代价/span>

来星球聊聊技术人的斜杠生活

点一点“阅读原文”小惊喜在等你