红黑树 红黑树的时间复杂度

先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。

排序二叉树是一种特殊结构的二叉树,可以非常方便地对树中所有节点进行排序和检索。

排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树:

红黑树

排序二叉树虽然可以快速检索,但在最坏的情况下:如果插入的节点集本身就是有序的,要么是由小到大排列,要么是由大到小排列,那么最后得到的排序二叉树将变成链表:所有节点只有左节点(如果插入节点集本身是大到小排列);或所有节点只有右节点(如果插入节点集本身是小到大排列)。在这种情况下,排序二叉树就变成了普通链表,其检索效率就会很差。

为了改变排序二叉树存在的不足,Rudolf Bayer 与 1972年发明了另一种改进后的排序二叉树:红黑树,他将这种排序二叉树称为“对称二叉 B 树”,而红黑树这个名字则由 Leo J. Guibas和 Robert Sedgewick 于 1978 年首次提出。

红黑树是一个更高效的检索二叉树,因此常常用来实现关联数组。典型地,JDK 提供的集合类 TreeMap本身就是一个红黑树的实现。

红黑树在原有的排序二叉树增加了如下几个要求:

Java 实现的红黑树

上面的性质 3 中指定红黑树的每个叶子节点都是空节点,而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null来代表空节点,因此遍历红黑树时将看不到黑色的叶子节点,反而看到每个叶子节点都是红色的。

Java 中实现的红黑树可能有如图 6 所示结构:


图 6. Java红黑树的示意
红黑树 红黑树的时间复杂度

备注:本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。

根据性质5:红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点,因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度(black-height)”。

性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3的红黑树:从根节点到叶节点的最短路径长度是 2,该路径上全是黑色节点(黑节点 - 黑节点 - 黑节点)。最长路径也只可能为4,在每个黑色节点之间插入一个红色节点(黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点),性质 4保证绝不可能插入更多的红色节点。由此可见,红黑树中最长路径就是一条红黑交替的路径。

红黑树和平衡二叉树

红黑树并不是真正的平衡二叉树,但在实际应用中,红黑树的统计性能要高于平衡二叉树,但极端性能略差。

由此我们可以得出结论:对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 *(N-1)。

提示:排序二叉树的深度直接影响了检索的性能,正如前面指出,当插入节点本身就是由小到大排列时,排序二叉树将变成一个链表,这种排序二叉树的检索性能最低:N个节点的二叉树深度就是 N-1。

红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的情况。

由于红黑树只是一个特殊的排序二叉树,因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同,只是红黑树保持了大致平衡,因此检索性能比排序二叉树要好很多。

但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征,因此插入操作和删除操作都需要进行一定的维护,以保证插入节点、删除节点后的树依然是红黑树。

  

爱华网本文地址 » http://www.413yy.cn/a/25101016/293134.html

更多阅读

发财树的养殖方法和注意事项 发财树摆放禁忌

发财树的养殖方法和注意事项——简介发财树的养殖方法和注意事项,特点:耐阴,耐旱要诀:防湿,防冻发财树的养殖方法和注意事项——工具/原料盆土水肥料发财树的养殖方法和注意事项——方法/步骤发财树的养殖方法和注意事项 1、一、环境的

金钱树的养殖方法 金钱树叶子发黄怎么办

最近2至3年,有一种被称作金钱树的观叶植物,从南到北闪亮登场,售价不菲,每株价格高达数百元,且销路颇好。它于1997年从荷兰引进在广州芳村和顺德 陈村露面,1999年昆明世博会上,人们还不清楚其姓啥名甚,仅以其外部形态特征将其称作“金钱树”

红纹石的功效 蛋白石的功效与作用

红纹石的功效——简介红纹石的学名叫菱锰矿Rhodochrosite,来自两个希腊字,分别指玫瑰(Rose)和颜色(Color),以象征它特殊的色彩。天然红纹石还有一个动听的名字叫做印加玫瑰,因为多数的红纹石都产于印加帝国的繁荣地安地斯山脉,色泽通透精美,

大转移后DNF黑硬的物质怎么得 dnf大转移剧情

大转移后DNF黑硬的物质怎么得——简介黑硬的物质,原来是在凯莉压缩机任务里得到的,大转移后改到莎兰德魔法胶囊任务里去了大转移后DNF黑硬的物质怎么得——工具/原料1个白色大晶体,20个混沌魔石碎片,10个最下级砥石大转移后DNF黑硬的物

排气管冒黑烟的原因及解决之道 排气管冒黑烟

可能见过车的人都知道,排气管冒黑烟经常看到,如果你是司机的话,对这个异常的现象不了解的话,说明你对柴油机的维修养护方面很欠缺。一般来说,排气管冒黑烟、蓝烟或者灰白烟,基本都是燃料在燃烧室没有得到充分的燃烧所致的。如果柴油机工作

声明:《红黑树 红黑树的时间复杂度》为网友淡蓝色的经典分享!如侵犯到您的合法权益请联系我们删除