红黑树是非常popular的一种self-adjusted的平衡二叉排序树。
通常他给我们的印象是很复杂,有很多case,要小心的旋转。有人说,曾将在某公司的面试时,被要求实现红黑树。他觉得这很没有道理,几乎很少有人能在不参考教科书的情况下,记清楚那么多的case。
在这一章里,我将向你展示目前我所见过的最简洁的红黑树实现。简洁到什么程度呢?我打赌你看过后能轻松通过上面的面试——Wow, 红黑树原来可以这么简单!
这个实现,来自Chris Okasaki在卡耐基梅隆大学(CMU)的博士研究成果。他启发我用同样的方法简洁地实现了AVL tree和Splay tree。
这一章我们讲红黑树,大致内容如下:
1. 简介——我们看看普通的排序二叉树致命弱点,并且给出树旋转的概念;
2. 红黑树的定义——我们看看为什么红黑树的性质能解决平衡问题,从而胜过排序二叉树;
3. 插入——我们给出红黑树插入算法的数学定义,这里是本章的精华;
4. 删除——删除本来不是个问题,但是我们要展示下删除比起插入有多复杂;
6. 传统实现——我们看看传统实现的红黑树插入算法有多复杂,并做进一步的比较分析;传统实现的删除算法我们留作练习。
7. 其他——多说两句
全文在
https://sites.google.com/site/algoxy/rbtree
附件是PDF版。
全部源代码在github可以获得:
https://github.com/liuxinyu95/AlgoXY
分享到:
相关推荐
红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...
红黑树原理详解 红黑树原理详解 红黑树原理详解 红黑树原理详解
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)...
红黑树算法,随机产生数字,动态生成红黑树,可用于演示。
红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树
通用红黑树 说明: 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树: 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者:rcyh 日期:2011年7月21日 ---------------------------------...
删除测试,删除1)中红黑树中Key=15的节点,按照 红黑树信息输出方式 输出调整后的整棵红黑树以及黑高。 3).随机产生300,000个不同自然数Key值(1-300,000),建立红黑树,查找Key=15000的节点,输出查找花费时间...
红黑树继承二叉查找树,区间树继承红黑树,main函数中写的是区间树的测试程序
红黑树和AVL树的代码实现,并显示树的形状,同时红黑树还可以输出个路径以及黑高度
红黑树的插入与删除_详细整理资料
红黑树是重要的数据结构,而其操作又很复杂,如果能够可视化地展示插入与删除过程,则学习起来会容易得多。 为了学习它们,我翻译以下文章(论文)并实现了相应算法,并放到网络上,与说中文的程序爱好者共同进步。...
红黑树
用c实现的红黑树,经典的红黑树, 速度与思维的立体化结构
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 [1] 红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-...
实验1:实现红黑树的基本算法, 对n的取值分别为 12、24、36、48、60,随机生成n 个互异的正整数(K1, K2, K3, ……, Kn)作为节点的关键字,向一棵初始空的红黑树中依次插入这n 个节点,统计算法运行所需时间 ,画...
在学习c++的过程中实现的红黑树,功能比较完善,无优化..
删除测试,删除1)中红黑树中Key=15的节点,按照 红黑树信息输出方式 输出调整后的整棵红黑树以及黑高。 3).随机产生300,000个不同自然数Key值(1-300,000,每个数出现一次,出现顺序随机),建立红黑树,查找Key...
删除测试,删除1)中红黑树中Key=15的节点,按照 红黑树信息输出方式 输出调整后的整棵红黑树以及黑高。 3).随机产生300,000个不同自然数Key值(1-300,000,每个数出现一次,出现顺序随机),建立红黑树,查找Key...
红黑树算法详细介绍