当前位置:   article > 正文

从无到有构建红黑树_1 2 3 4 5 6 7依次插入红黑树

1 2 3 4 5 6 7依次插入红黑树

链接:https://blog.csdn.net/jimoshuicao/article/details/8618043
红黑树是60年代中期计算机科学界找寻一种算法复杂度稳定,容易实现的数据存储算法的产物。在优先级队列、字典等实用领域都有广泛地应用,更是70年代提出的关系数据库模型–B树的鼻祖。在Linux kernel中,高精度定时器也工作在红黑树之上。为便于初学者掌握其基本算法,本文一步一步地演示了红黑树的创建过程。
首先回顾一下红黑树的基本性质:

1. 红黑树本质上是一个二叉查找树(BST),但是它从根到最远叶子的长度不会超过到最近叶子长度的两倍,因此是近似平衡的。

2. 红黑树的节点不是黑的就是红的,不会有第三种颜色。

3. 树根必须是黑色。

4. 叶子所指的空节点必须是黑色。

5. 如果某个节点是红色,那么它的两个儿子必须都是黑色。

6. 从任意节点出发的所有向下的路径上包含相同个数的黑节点。这个个数我们称为黑高度Bh。

有了上面的认识,我们要从无到有构造一颗红黑树的话,心里就有底了。这个构造的过程可以分两步:

第一步:执行BST的插入算法;

第二步:对节点着色;

第一步不会有什么问题,关键是第二步怎么对节点着色才不会违反红黑树的基本性质;

这是一个难点,我在写这篇文章的时候脑子也卡了一下,节点不多的时候好办,但是如果节点很多了,就必须找到一种普遍适用的算法来处理。通过这两天的观察,我发现这六条性质中最关键的其实是最后一条---从任意结点出发的任意路径黑高度相等!这才是红黑树算法保持近似平衡的精华所在!其它性质要么是这条性质的产物,要么就是为这条性质服务的。

现在我演示一下怎么从无到有生成一棵红黑树。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

例如我们有一组数:{9,7,15,6,11,19},现在按照从左到右的顺序存放在一颗红黑树中。

第一个数是9,很自然地成为了树根,如图:

图-1

每个新节点都默认地被渲染成了红色,为什么要这么做呢?后面我们将会看到它的好处!现在先忽略不谈。



根节点9是红色,这违背了性质3,所以必须改成黑色,如图:
  • 1
  • 2
  • 3
  • 4
  • 5

图-2

下一个数字是7,显然要被插入到9的左边,并且这时满足红黑树的所有性质,如图:

图-3

下一个数字是15,要插入到9的右边,并且也满足红黑树的所有性质,如图:

在这里插入图片描述
下一个数字是6,要插入到7的左边,这回似乎有麻烦了,性质5被违背了,如图:

图-5

可能有人会说,那很简单,既然违背了性质5,那我改一下6的颜色不就OK了?

在这里插入图片描述

现在,恭喜你---也走进了我曾经走过的误区:)你的无意之举改变了新增节点路径上面的黑高度,这棵树已经不是红黑树了!

写代码的人都知道,对树的遍历,最简单的方法就是递归,那么树的数学模型就是一个可穷举的递归式。递归式中每一步的正确性都建立在前一步正确的基础之上。现在我们回过头来想想为什么每次插入的新节点都被渲染成红色呢?你肯定猜到了,因为我们要保证红黑树的核心性质--黑高度不发生变化,虽然牺牲了性质5,但这是可以补救的,并且代价很小。再来看看图-5
  • 1
  • 2
  • 3

在这里插入图片描述
既然我们不能通过改变新插入节点的颜色来维持红黑树的性质,那么就只好从原来的树结构入手了。

我们注意到新插入的节点的父亲是一个红节点,其叔叔也是一个红节点。那么假如我把它的父亲改成黑色,则恢复了性质5,可是从树根出发的黑高度还是不相等,干脆把它的叔叔也改成黑色吧!结果如下:
  • 1

图-7

现在它满足红黑树所有的性质。好了,我们继续。

插入数字11和19的过程平淡无奇,不深入探讨,最终的树如图:

在这里插入图片描述

如果现在要插入数字10怎么办?它肯定会是11的左节点:

在这里插入图片描述

明显违背了性质5!难道依葫芦画瓢,把11和19都改成黑色?这样从树根出发的左边路径黑高度还是2,而右边两条路径的黑高度将变成了3,老办法失效了!

图-10

其实不然,改了新增节点的父亲和叔叔的颜色以后,右边路径黑高度全加一,但我们只要把它的爷爷改成红色不就又减去了多出来的黑高度吗?
  • 1

在这里插入图片描述

如果你认真看到这里,我想你的潜意识一定告诉你—这里存在某种规律等着我们去发现。

让我们再仔细审视一下图-5

在这里插入图片描述

在生成树的过程中,我们已经两次遇到类似情况了,归纳一下,这个场景就是:新节点的父亲是红色,叔叔也是红色。



至于别的节点,我们大可不必关心,因为很显然,这个场景是原子的。



我们的处理办法是把7和15渲染成黑色,就像图-7那样,可是因为这是一个普遍适用的场景,所以要做一个扩展:假设在这个原子树的每个节点上还有别的分支。那么图-7就不能保证所有路径的黑高度相等了,即使把9改成红色也无济于事,因为9也许还有父节点,所以也许它的父节点又是红色,这就再次违反了性质5。我最喜欢的作家之一--柯南.道尔,曾说过:“历史就像车轮的辐条,每一根都终将再次转回来。”眼前的场景正是如此---我们设计的原子场景再次出现。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

一个清晰的递归算法呈现在我们面前:

  1. 新增节点渲染成红色;

  2. 如果它的父亲是红色,则违反了性质5;

  3. 如果它的叔叔也是红色,则通过同时修改其父亲和叔叔的颜色为黑色来恢复性质5;

  4. 如果它的爷爷不是根节点,则有可能在另外的路径上再次违反性质5,于是我们把它的爷爷改成红色;

  5. 可是如果他的太爷爷也是红色呢?很自然地,我们重新回到步骤2;

  6. 不断循环,直到第二步满足就可以结束。

最后留给感兴趣的同学两个问题:

  1. 如果新增节点的父亲是红色,但它的叔叔是黑色,该怎么办?(提示:使用旋转)

  2. 有人说,下面这种场景,我设计的算法就失效了,真的吗?(粉色的6是新插入的节点,插入前就不是一棵合法的红黑树)

在这里插入图片描述

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号