vlambda博客
学习文章列表

【漫画】红黑树杀人事件始末

来源 |  作者 郭可岩

前言

漫画目录

  • 第一话:“你弱爆了,回去多读点书

  • 第二话:“看来你有点长进”

  • 第三话:“你这算什么,我七岁那年可就能手写红黑树了”

  • 第四话:“打住,我怀疑你在背书本”

  • 第五话:“你读书只读了表面,你不是我要的人”

  • 彩蛋:轮回

内容简介

本文以漫画形式讲述红黑树,第一话讲解二叉查找树的概念和基本操作,包括节点查找、插入、删除;第二话讲解二叉查找树的缺点和红黑树的概念,以及红黑树的节点旋转操作;第三话讲解红黑树的节点插入操作;第四话讲解红黑树的节点删除操作;第五话和彩蛋部分讲解红黑树在插入修正和删除修正时,对各种 CASE 所进行的调整操作背后的思想。

第一话:“你弱爆了,回去多读点书”

【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末

第二话:“看来你有点长进”

【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末

第三话:“你这算什么,我七岁那年可就能手写红黑树了”

【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末

第四话:“打住,我怀疑你在背书本”

【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末

第五话:“你读书只读了表面,你不是我要的人”

【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末

彩蛋:轮回

【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末
【漫画】红黑树杀人事件始末

后记

黑树是算法领域中一个著名的二叉查找树实现,它能够以较小的开销保持二叉查找树的平衡。具备平衡性质的二叉查找树能够极大地提高节点的查询速度。举个形象一点的例子:从一个十亿节点的红黑树中查找一个节点,所需要的查询次数不到 30,这不禁让人感叹算法的魅力。

红黑树是工程中最常见的二叉查找树的实现,例如在 Linux 的内存管理和进程管理中就用到了红黑树;Java 语言的集合包、C++语言的标准模板库中均提供了红黑树的实现类。

红黑树本身的设计很复杂,多数情况下我们也不需要自己去实现红黑树,但研究红黑树还是有意义的。一方面可以让学习者领略这种神奇的数据结构的奥妙,另一方面可以作为一种思维训练工具,提升自己的算法设计能力。

本文以漫画形式讲述红黑树,第一话讲解二叉查找树的概念和基本操作,包括节点查找、插入、删除;第二话讲解二叉查找树的缺点和红黑树的概念,以及红黑树的节点旋转操作;第三话讲解红黑树的节点插入操作;第四话讲解红黑树的节点删除操作;第五话和彩蛋部分讲解红黑树在插入修正和删除修正时,对各种 CASE 所进行的调整操作背后的思想。

红黑树的实现中,最难的部分在于实现节点的插入和删除时,要穷举所有可能的 CASE,然后对每种 CASE 进行处理。在理解节点的插入和删除的过程时,读者要把握住一个中心:每种 CASE 所进行的调整步骤都在尽量恢复插入/删除节点后所违反的红黑树特性,如果当前 CASE 解决不了,就转成另一种更接近问题解决状态的 CASE。每种 CASE 所进行的调整步骤都是为了向解决问题的出口更靠近一步,直至找到出口。