前言

图片

内容简介

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

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

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

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

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

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

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

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

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

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

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

彩蛋:轮回

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

图片

后记

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

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

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

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

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

作者:郭可岩
来源:https://mp.weixin.qq.com/s/rYnfz2SF2qR7n_ezIxsftQ