首页 > 头条终面:手写红黑树
头像
公众号「码海」
编辑于 2021-02-07 22:32
+ 关注

头条终面:手写红黑树

前言

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

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

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

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

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

漫画采用大量的图示来展示红黑树操作的诸多细节,作者力求详尽,因此篇幅略长。附录给出了完整的二叉查找树定义 + 测试代码,以及红黑树定义 + 测试代码。两份代码均经过了若干次十万数量级随机节点插入和删除测试,结果均无误。读者可贴到自己的 IDE 中,结合本文讲解进行调试研究。

在电脑端本文阅读效果更佳。另外,读者可联系码海公众号博主(微信:geekoftaste)获取本漫画的pdf版本。

正文

全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐