红黑树，超强动静图详解，简单易懂

2019-08-29 14:25:52 浏览数 (1)

写在前面

红黑树，对很多童鞋来说，是既熟悉又陌生。学校中学过，只了解大概；工作中不怎么使用，但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。没错，本文内容就是要解决这个问题，用简单的语言，搭配静图和动图(利用大脑图形记忆方式)，让你对红黑树有更深入的了解和更清晰的记忆，希望小伙伴们再次遇到红黑树的问题不至于头大，建议读该文章姿势: 打开两个页面，一个页面看图片和内容，一个页面看公式，像玩魔方一样，多玩几次就明白了

通过工具动态感受红黑树的转换过程

俺家司令买完东西后，我俩经常会发生这样的一段对话: 司令:你猜我买的这个多少钱？我: 1000司令: 高了我: 500司令: 低了:我: 750...... 直到最后猜中

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

程序中的树其实是我们日常看到的树的倒影，或者发挥一下想象，倒影也可以是树根

二叉查找树

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

  1. 某节点的左子树节点值仅包含小于该节点值
  2. 某节点的右子树节点值仅包含大于该节点值
  3. 左右子树每个也必须是二叉查找树

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

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

  1. 这是一个走路一米六，一米八的树
  2. 这是一个畸形的树，大风一挂很可能被折断的树

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

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

红黑树

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

  1. 每个节点都有红色或黑色
  2. 树的根始终是黑色的 (黑土地孕育黑树根，?)
  3. 没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，并没有说不能出现连续的黑色节点）
  4. 从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

瞬间懵逼？了解一下印象就行，开始玩魔方都是要照着魔方公式一点点玩的，多玩几次就熟悉了。红黑树也一样，红黑树有两大操作:

  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 节点，然后变色即可

左右

左旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的左孩子，然后再应用 左左情况

右右

与左左情况一样，想象成一根绳子

右左

右旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况

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

案例一

插入 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 为根结点，将其改为黑色

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

灵魂追问

  1. jdk 1.8 HashMap 中有使用到红黑树，你知道触发条件是什么吗？有读过源码是如何 put 和 remove 的吗？
  2. 这里讲的是红黑树的 insert，delete 又是什么规则呢？
  3. 哪些场景可以应用红黑树？
  4. 你了解各种树的时间复杂度吗？
  5. 留个小作业，应用工具将 [10 70 32 34 13 56 32 56 21 3 62 4 ] 逐个插入到树中，理解红黑树 recolor 和 rotation 的转换规则

（完）

parent root rotation

0 人点赞