装修公司做自己网站,wordpress 排除置顶文章,保定企业建网站,it外包公司可以进吗红黑树 —— 原理和算法详细介绍
R-B Tree简介
R-B Tree#xff0c;全称是Red-Black Tree#xff0c;又称为“红黑树”#xff0c;它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色#xff0c;可以是红(Red)或黑(Black)。
红黑树的特性:
每个节点或…红黑树 —— 原理和算法详细介绍
R-B Tree简介
R-B Tree全称是Red-Black Tree又称为“红黑树”它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色可以是红(Red)或黑(Black)。
红黑树的特性:
每个节点或者是黑色或者是红色。根节点是黑色。每个叶子节点NIL是黑色。 [注意这里叶子节点是指为空(NIL或NULL)的叶子节点]如果一个节点是红色的则它的子节点必须是黑色的。从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意 (01) 特性(3)中的叶子节点是只为空(NIL或null)的节点。 (02) 特性(5)确保没有一条路径会比其他路径长出俩倍。因而红黑树是相对是接近平衡的二叉树。
红黑树示意图如下
红黑树的应用
红黑树的应用比较广泛主要是用它来存储有序的数据它的时间复杂度是O(lgn)效率非常之高。 例如Java集合中的TreeSet和TreeMapC STL中的set、map以及Linux虚拟内存的管理都是通过红黑树去实现的。
红黑树的时间复杂度和相关证明
红黑树的时间复杂度为: O(lgn) 下面通过“数学归纳法”对红黑树的时间复杂度进行证明。
定理一棵含有n个节点的红黑树的高度至多为2log(n1).
证明 “一棵含有n个节点的红黑树的高度至多为2log(n1)” 的逆否命题是 “高度为h的红黑树它的包含的内节点个数至少为 2h/2-1个”。 我们只需要证明逆否命题即可证明原命题为真即只需证明 “高度为h的红黑树它的包含的内节点个数至少为 2h/2-1个”。
从某个节点x出发不包括该节点到达一个叶节点的任意一条路径上黑色节点的个数称为该节点的黑高度(x’s black height)记为bh(x)。关于bh(x)有两点需要说明 第1点根据红黑树的特性(5) 即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点可知从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着bh(x)的值是唯一的 第2点根据红黑色的特性(4)即如果一个节点是红色的则它的子节点必须是黑色的可知从节点x出发达到叶节点所经历的黑节点数目 “所经历的红节点的数目”。假设x是根节点则可以得出结论bh(x) h/2。进而我们只需证明 高度为h的红黑树它的包含的黑节点个数至少为 2bh(x)-1个即可。
到这里我们将需要证明的定理已经由 “一棵含有n个节点的红黑树的高度至多为2log(n1)” 转变成只需要证明 “高度为h的红黑树它的包含的内节点个数至少为 2bh(x)-1个”。
下面通过数学归纳法开始论证高度为h的红黑树它的包含的内节点个数至少为 2bh(x)-1个。
(01) 当树的高度h0时 内节点个数是0bh(x) 为02bh(x)-1 也为 0。显然原命题成立。
(02) 当h0且树的高度为 h-1 时它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的 下面由树的高度为 h-1 的已知条件推出“树的高度为 h 时它所包含的节点树为 2bh(x)-1”。 当树的高度为 h 时 对于节点x(x为根节点)其黑高度为bh(x)。 对于节点x的左右子树它们黑高度为 bh(x) 或者 bh(x)-1。 根据(02)的已知条件我们已知 “x的左右子树即高度为 h-1 的节点它包含的节点至少为 2bh(x)-1-1 个” 所以节点x所包含的节点至少为 ( 2bh(x)-1-1 ) ( 2bh(x)-1-1 ) 1 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。 因此原命题成立。
由(01)、(02)得出“高度为h的红黑树它的包含的内节点个数至少为 2^bh(x)-1个”。 因此“一棵含有n个节点的红黑树的高度至多为2log(n1)”。
红黑树的基本操作(一) 左旋和右旋
红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后都会用到旋转方法。为什么呢道理很简单添加或删除红黑树中的节点之后红黑树就发生了变化可能不满足红黑树的5条性质也就不再是一颗红黑树了而是一颗普通的树。而通过旋转可以使这颗树重新成为红黑树。简单点说旋转的目的是让树保持红黑树的特性。 旋转包括两种左旋 和 右旋。下面分别对它们进行介绍。
1. 左旋 对x进行左旋意味着将x变成一个左节点。
左旋的伪代码《算法导论》参考上面的示意图和下面的伪代码理解“红黑树T的节点x进行左旋”是如何进行的。
LEFT-ROTATE(T, x) y ← right[x] // 前提这里假设x的右孩子为y。下面开始正式操作right[x] ← left[y] // 将 “y的左孩子” 设为 “x的右孩子”即 将β设为x的右孩子p[left[y]] ← x // 将 “x” 设为 “y的左孩子的父亲”即 将β的父亲设为xp[y] ← p[x] // 将 “x的父亲” 设为 “y的父亲”if p[x] nil[T] then root[T] ← y // 情况1如果 “x的父亲” 是空节点则将y设为根节点else if x left[p[x]] then left[p[x]] ← y // 情况2如果 x是它父节点的左孩子则将y设为“x的父节点的左孩子”else right[p[x]] ← y // 情况3(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”left[y] ← x // 将 “x” 设为 “y的左孩子”p[x] ← y // 将 “x的父节点” 设为 “y”理解左旋之后看看下面一个更鲜明的例子。你可以先不看右边的结果自己尝试一下。
2. 右旋 对x进行左旋意味着将x变成一个左节点。
右旋的伪代码《算法导论》参考上面的示意图和下面的伪代码理解“红黑树T的节点y进行右旋”是如何进行的。
RIGHT-ROTATE(T, y) x ← left[y] // 前提这里假设y的左孩子为x。下面开始正式操作left[y] ← right[x] // 将 “x的右孩子” 设为 “y的左孩子”即 将β设为y的左孩子p[right[x]] ← y // 将 “y” 设为 “x的右孩子的父亲”即 将β的父亲设为yp[x] ← p[y] // 将 “y的父亲” 设为 “x的父亲”if p[y] nil[T] then root[T] ← x // 情况1如果 “y的父亲” 是空节点则将x设为根节点else if y right[p[y]] then right[p[y]] ← x // 情况2如果 y是它父节点的右孩子则将x设为“y的父节点的左孩子”else left[p[y]] ← x // 情况3(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”right[x] ← y // 将 “y” 设为 “x的右孩子”p[y] ← x // 将 “y的父节点” 设为 “x”理解右旋之后看看下面一个更鲜明的例子。你可以先不看右边的结果自己尝试一下。 旋转总结
(01) 左旋 和 右旋 是相对的两个概念原理类似。理解一个也就理解了另一个。
(02) 下面谈谈如何区分 左旋 和 右旋。 在实际应用中若没有彻底理解 左旋 和 右旋可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。
3. 区分 左旋 和 右旋
仔细观察上面左旋和右旋的示意图。我们能清晰的发现它们是对称的。无论是左旋还是右旋被旋转的树在旋转前是二叉查找树并且旋转之后仍然是一颗二叉查找树。 左旋示例图(以x为节点进行左旋) zx / / \ --(左旋)-- xy z /y对x进行左旋意味着将“x的右孩子”设为“x的父亲节点”即将 x变成了一个左节点(x成了为z的左孩子)。 因此左旋中的“左”意味着“被旋转的节点将变成一个左节点”。
右旋示例图(以x为节点进行右旋) yx \ / \ --(右旋)-- xy z \z对x进行右旋意味着将“x的左孩子”设为“x的父亲节点”即将 x变成了一个右节点(x成了为y的右孩子) 因此右旋中的“右”意味着“被旋转的节点将变成一个右节点”。
红黑树的基本操作(二) 添加
将一个节点插入到红黑树中需要执行哪些步骤呢首先将红黑树当作一颗二叉查找树将节点插入然后将节点着色为红色最后通过旋转和重新着色等方法来修正该树使之重新成为一颗红黑树。详细描述如下
第一步: 将红黑树当作一颗二叉查找树将节点插入。 红黑树本身就是一颗二叉查找树将节点插入后该树仍然是一颗二叉查找树。也就意味着树的键值仍然是有序的。此外无论是左旋还是右旋若旋转之前这棵树是二叉查找树旋转之后它一定还是二叉查找树。这也就意味着任何的旋转和重新着色操作都不会改变它仍然是一颗二叉查找树的事实。 好吧那接下来我们就来想方设法的旋转以及重新着色使这颗树重新成为红黑树
第二步将插入的节点着色为红色。 为什么着色成红色而不是黑色呢为什么呢在回答之前我们需要重新温习一下红黑树的特性 (1) 每个节点或者是黑色或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意这里叶子节点是指为空的叶子节点] (4) 如果一个节点是红色的则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 将插入的节点着色为红色不会违背特性(5)少违背一条特性就意味着我们需要处理的情况越少。接下来就要努力的让这棵树满足其它性质即可满足了的话它就又是一颗红黑树了。o(∩∩)o…哈哈
第三步: 通过一系列的旋转或着色等操作使之重新成为一颗红黑树。 第二步中将插入节点着色为红色之后不会违背特性(5)。那它到底会违背哪些特性呢 对于特性(1)显然不会违背了。因为我们已经将它涂成红色了。 对于特性(2)显然也不会违背。在第一步中我们是将红黑树当作二叉查找树然后执行的插入操作。而根据二叉查找数的特点插入操作不会改变根节点。所以根节点仍然是黑色。 对于特性(3)显然不会违背了。这里的叶子节点是指的空叶子节点插入非空节点并不会对它们造成影响。 对于特性(4)是有可能违背的 那接下来想办法使之满足特性(4)就可以将树重新构造成红黑树了。
下面看看代码到底是怎样实现这三步的。
添加操作的伪代码《算法导论》
RB-INSERT(T, z) y ← nil[T] // 新建节点“y”将y设为空节点。x ← root[T] // 设“红黑树T”的根节点为“x”while x ≠ nil[T] // 找出要插入的节点“z”在二叉树T中的位置“y”do y ← x if key[z] key[x] then x ← left[x] else x ← right[x] p[z] ← y // 设置 “z的父亲” 为 “y”if y nil[T] then root[T] ← z // 情况1若y是空节点则将z设为根else if key[z] key[y] then left[y] ← z // 情况2若“z所包含的值” “y所包含的值”则将z设为“y的左孩子”else right[y] ← z // 情况3(“z所包含的值” “y所包含的值”)将z设为“y的右孩子” left[z] ← nil[T] // z的左孩子设为空right[z] ← nil[T] // z的右孩子设为空。至此已经完成将“节点z插入到二叉树”中了。color[z] ← RED // 将z着色为“红色”RB-INSERT-FIXUP(T, z) // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转让树T仍然是一颗红黑树结合伪代码以及为代码上面的说明先理解RB-INSERT。理解了RB-INSERT之后我们接着对 RB-INSERT-FIXUP的伪代码进行说明。
添加修正操作的伪代码《算法导论》
RB-INSERT-FIXUP(T, z)while color[p[z]] RED // 若“当前节点(z)的父节点是红色”则进行以下处理。do if p[z] left[p[p[z]]] // 若“z的父节点”是“z的祖父节点的左孩子”则进行以下处理。then y ← right[p[p[z]]] // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”if color[y] RED // Case 1条件叔叔是红色then color[p[z]] ← BLACK ▹ Case 1 // (01) 将“父节点”设为黑色。color[y] ← BLACK ▹ Case 1 // (02) 将“叔叔节点”设为黑色。color[p[p[z]]] ← RED ▹ Case 1 // (03) 将“祖父节点”设为“红色”。z ← p[p[z]] ▹ Case 1 // (04) 将“祖父节点”设为“当前节点”(红色节点)else if z right[p[z]] // Case 2条件叔叔是黑色且当前节点是右孩子then z ← p[z] ▹ Case 2 // (01) 将“父节点”作为“新的当前节点”。LEFT-ROTATE(T, z) ▹ Case 2 // (02) 以“新的当前节点”为支点进行左旋。color[p[z]] ← BLACK ▹ Case 3 // Case 3条件叔叔是黑色且当前节点是左孩子。(01) 将“父节点”设为“黑色”。color[p[p[z]]] ← RED ▹ Case 3 // (02) 将“祖父节点”设为“红色”。RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) 以“祖父节点”为支点进行右旋。else (same as then clause with right and left exchanged) // 若“z的父节点”是“z的祖父节点的右孩子”将上面的操作中“right”和“left”交换位置然后依次执行。
16 color[root[T]] ← BLACK根据被插入节点的父节点的情况可以将当节点z被着色为红色节点并插入二叉树划分为三种情况来处理。 ① 情况说明被插入的节点是根节点。 处理方法直接把此节点涂为黑色。 ② 情况说明被插入的节点的父节点是黑色。 处理方法什么也不需要做。节点被插入后仍然是红黑树。 ③ 情况说明被插入的节点的父节点是红色。 处理方法那么该情况与红黑树的“特性(5)”相冲突。这种情况下被插入节点是一定存在非空祖父节点的进一步的讲被插入节点也一定存在叔叔节点(即使叔叔节点为空我们也视之为存在空节点本身就是黑色节点)。理解这点之后我们依据叔叔节点的情况将这种情况进一步划分为3种情况(Case)。 上面三种情况(Case)处理问题的核心思路都是将红色的节点移到根节点然后将根节点设为黑色。下面对它们详细进行介绍。
1. (Case 1)叔叔是红色
1.1 现象说明
当前节点(即被插入节点)的父节点是红色且当前节点的祖父节点的另一个子节点叔叔节点也是红色。
1.2 处理策略
(01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。 (03) 将“祖父节点”设为“红色”。 (04) 将“祖父节点”设为“当前节点”(红色节点)即之后继续对“当前节点”进行操作。
下面谈谈为什么要这样处理。(建议理解的时候通过下面的图进行对比) “当前节点”和“父节点”都是红色违背“特性(4)”。所以将“父节点”设置“黑色”以解决这个问题。 但是将“父节点”由“红色”变成“黑色”之后违背了“特性(5)”因为包含“父节点”的分支的黑色节点的总数增加了1。 解决这个问题的办法是将“祖父节点”由“黑色”变成红色同时将“叔叔节点”由“红色”变成“黑色”。关于这里说明几点第一为什么“祖父节点”之前是黑色这个应该很容易想明白因为在变换操作之前该树是红黑树“父节点”是红色那么“祖父节点”一定是黑色。 第二为什么将“祖父节点”由“黑色”变成红色同时将“叔叔节点”由“红色”变成“黑色”能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”既然这样我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题 但是这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”现在我们已知“叔叔节点”是“红色”将“叔叔节点”设为“黑色”就能解决这个问题。 所以将“祖父节点”由“黑色”变成红色同时将“叔叔节点”由“红色”变成“黑色”就解决了该问题。 按照上面的步骤处理之后当前节点、父节点、叔叔节点之间都不会违背红黑树特性但祖父节点却不一定。若此时祖父节点是根节点直接将祖父节点设为“黑色”那就完全解决这个问题了若祖父节点不是根节点那我们需要将“祖父节点”设为“新的当前节点”接着对“新的当前节点”进行分析。
1.3 示意图 2. (Case 2)叔叔是黑色且当前节点是右孩子
2.1 现象说明
当前节点(即被插入节点)的父节点是红色叔叔节点是黑色且当前节点是其父节点的右孩子
2.2 处理策略
(01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。 **下面谈谈为什么要这样处理。**(建议理解的时候通过下面的图进行对比)首先将“父节点”作为“新的当前节点”接着以“新的当前节点”为支点进行左旋。 为了便于理解我们先说明第(02)步再说明第(01)步为了便于说明我们设置“父节点”的代号为F(Father)“当前节点”的代号为S(Son)。为什么要“以F为支点进行左旋”呢根据已知条件可知S是F的右孩子。而之前我们说过我们处理红黑树的核心思想将红色的节点移到根节点然后将根节点设为黑色。既然是“将红色的节点移到根节点”那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子因此我们可以通过“左旋”来将S上移 按照上面的步骤(以F为支点进行左旋)处理之后若S变成了根节点那么直接将其设为“黑色”就完全解决问题了若S不是根节点那我们需要执行步骤(01)即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理而需要以F为新的当前节点来进行处理呢这是因为“左旋”之后F变成了S的“子节点”即S变成了F的父节点而我们处理问题的时候需要从下至上(由叶到根)方向进行处理也就是说必须先解决“孩子”的问题再解决“父亲”的问题所以我们执行步骤(01)将“父节点”作为“新的当前节点”。
2.2 示意图 3. (Case 3)叔叔是黑色且当前节点是左孩子
3.1 现象说明
当前节点(即被插入节点)的父节点是红色叔叔节点是黑色且当前节点是其父节点的左孩子
3.2 处理策略
(01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。
下面谈谈为什么要这样处理。(建议理解的时候通过下面的图进行对比) 为了便于说明我们设置“当前节点”为S(Original Son)“兄弟节点”为B(Brother)“叔叔节点”为U(Uncle)“父节点”为F(Father)祖父节点为G(Grand-Father)。 S和F都是红色违背了红黑树的“特性(4)”我们可以将F由“红色”变为“黑色”就解决了“违背‘特性(4)’”的问题但却引起了其它问题违背特性(5)因为将F由红色改为黑色之后所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢 我们可以通过“将G由黑色变成红色”同时“以G为支点进行右旋”来解决。
2.3 示意图 提示上面的进行Case 3处理之后再将节点120当作当前节点就变成了Case 2的情况。
红黑树的基本操作(三) 删除
将红黑树内的某一个节点删除。需要执行的操作依次是首先将红黑树当作一颗二叉查找树将该节点从二叉查找树中删除然后通过旋转和重新着色等一系列来修正该树使之重新成为一棵红黑树。详细描述如下
第一步将红黑树当作一颗二叉查找树将节点删除。 这和删除常规二叉查找树中删除节点的方法是一样的。分3种情况 ① 被删除节点没有儿子即为叶节点。那么直接将该节点删除就OK了。 ② 被删除节点只有一个儿子。那么直接删除该节点并用该节点的唯一子节点顶替它的位置。 ③ 被删除节点有两个儿子。那么先找出它的后继节点然后把“它的后继节点的内容”复制给“该节点的内容”之后删除“它的后继节点”。在这里后继节点相当于替身在将后继节点的内容复制给被删除节点之后再将后继节点删除。这样就巧妙的将问题转换为删除后继节点的情况了下面就考虑后继节点。 在被删除节点有两个非空子节点的情况下它的后继节点不可能是双子非空。既然的后继节点不可能双子都非空就意味着该节点的后继节点要么没有儿子要么只有一个儿子。若没有儿子则按情况① 进行处理若只有一个儿子则按情况② 进行处理。
第二步通过旋转和重新着色等一系列来修正该树使之重新成为一棵红黑树。 因为第一步中删除节点之后可能会违背红黑树的特性。所以需要通过旋转和重新着色来修正该树使之重新成为一棵红黑树。
删除操作的伪代码《算法导论》
RB-DELETE(T, z)if left[z] nil[T] or right[z] nil[T] then y ← z // 若“z的左孩子” 或 “z的右孩子”为空则将“z”赋值给 “y”else y ← TREE-SUCCESSOR(z) // 否则将“z的后继节点”赋值给 “y”。if left[y] ≠ nil[T]then x ← left[y] // 若“y的左孩子” 不为空则将“y的左孩子” 赋值给 “x”else x ← right[y] // 否则“y的右孩子” 赋值给 “x”。p[x] ← p[y] // 将“y的父节点” 设置为 “x的父节点”if p[y] nil[T] then root[T] ← x // 情况1若“y的父节点” 为空则设置“x” 为 “根节点”。else if y left[p[y]] then left[p[y]] ← x // 情况2若“y是它父节点的左孩子”则设置“x” 为 “y的父节点的左孩子”else right[p[y]] ← x // 情况3若“y是它父节点的右孩子”则设置“x” 为 “y的父节点的右孩子”if y ≠ z then key[z] ← key[y] // 若“y的值” 赋值给 “z”。注意这里只拷贝z的值给y而没有拷贝z的颜色copy ys satellite data into z if color[y] BLACK then RB-DELETE-FIXUP(T, x) // 若“y为黑节点”则调用return y结合伪代码以及为代码上面的说明先理解RB-DELETE。理解了RB-DELETE之后接着对 RB-DELETE-FIXUP的伪代码进行说明
RB-DELETE-FIXUP(T, x)while x ≠ root[T] and color[x] BLACK do if x left[p[x]] then w ← right[p[x]] // 若 “x”是“它父节点的左孩子”则设置 “w”为“x的叔叔”(即x为它父节点的右孩子) if color[w] RED // Case 1: x是“黑黑”节点x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。then color[w] ← BLACK ▹ Case 1 // (01) 将x的兄弟节点设为“黑色”。color[p[x]] ← RED ▹ Case 1 // (02) 将x的父节点设为“红色”。LEFT-ROTATE(T, p[x]) ▹ Case 1 // (03) 对x的父节点进行左旋。w ← right[p[x]] ▹ Case 1 // (04) 左旋后重新设置x的兄弟节点。if color[left[w]] BLACK and color[right[w]] BLACK // Case 2: x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的两个孩子都是黑色。then color[w] ← RED ▹ Case 2 // (01) 将x的兄弟节点设为“红色”。x ← p[x] ▹ Case 2 // (02) 设置“x的父节点”为“新的x节点”。else if color[right[w]] BLACK // Case 3: x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的左孩子是红色右孩子是黑色的。then color[left[w]] ← BLACK ▹ Case 3 // (01) 将x兄弟节点的左孩子设为“黑色”。color[w] ← RED ▹ Case 3 // (02) 将x兄弟节点设为“红色”。RIGHT-ROTATE(T, w) ▹ Case 3 // (03) 对x的兄弟节点进行右旋。w ← right[p[x]] ▹ Case 3 // (04) 右旋后重新设置x的兄弟节点。color[w] ← color[p[x]] ▹ Case 4 // Case 4: x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。color[p[x]] ← BLACK ▹ Case 4 // (02) 将x父节点设为“黑色”。color[right[w]] ← BLACK ▹ Case 4 // (03) 将x兄弟节点的右子节设为“黑色”。LEFT-ROTATE(T, p[x]) ▹ Case 4 // (04) 对x的父节点进行左旋。x ← root[T] ▹ Case 4 // (05) 设置“x”为“根节点”。else (same as then clause with right and left exchanged) // 若 “x”是“它父节点的右孩子”将上面的操作中“right”和“left”交换位置然后依次执行。color[x] ← BLACK下面对删除函数进行分析。在分析之前我们再次温习一下红黑树的几个特性 (1) 每个节点或者是黑色或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意这里叶子节点是指为空的叶子节点] (4) 如果一个节点是红色的则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
前面我们将删除红黑树中的节点大致分为两步在第一步中将红黑树当作一颗二叉查找树将节点删除后可能违反特性(2)、(4)、(5)“三个特性。第二步需要解决上面的三个问题进而保持红黑树的全部特性。 为了便于分析我们假设x包含一个额外的黑色”(x原本的颜色还存在)这样就不会违反特性(5)。为什么呢 通过RB-DELETE算法我们知道删除节点y之后x占据了原来节点y的位置。 既然删除y(y是黑色)意味着减少一个黑色节点那么再在该位置上增加一个黑色即可。这样当我们假设x包含一个额外的黑色就正好弥补了删除y所丢失的黑色节点也就不会违反特性(5)。 因此假设x包含一个额外的黑色(x原本的颜色还存在)这样就不会违反特性(5)。 现在x不仅包含它原本的颜色属性x还包含一个额外的黑色。即x的颜色属性是红黑或黑黑它违反了特性(1)。
现在我们面临的问题由解决违反了特性(2)、(4)、(5)三个特性转换成了解决违反特性(1)、(2)、(4)三个特性。RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是将x所包含的额外的黑色不断沿树上移(向根方向移动)直到出现下面的姿态 a) x指向一个红黑节点。此时将x设为一个黑节点即可。 b) x指向根。此时将x设为一个黑节点即可。 c) 非前面两种姿态。
将上面的姿态可以概括为3种情况。 ① 情况说明x是“红黑”节点。 处理方法直接把x设为黑色结束。此时红黑树性质全部恢复。 ② 情况说明x是“黑黑”节点且x是根。 处理方法什么都不做结束。此时红黑树性质全部恢复。 ③ 情况说明x是“黑黑”节点且x不是根。 处理方法这种情况又可以划分为4种子情况。这4种子情况如下表所示
1. (Case 1)x是黑黑节点x的兄弟节点是红色
1.1 现象说明
x是黑黑节点x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
1.2 处理策略
(01) 将x的兄弟节点设为“黑色”。 (02) 将x的父节点设为“红色”。 (03) 对x的父节点进行左旋。 (04) 左旋后重新设置x的兄弟节点。
下面谈谈为什么要这样处理。(建议理解的时候通过下面的图进行对比) 这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”从而进行进一步的处理。对x的父节点进行左旋左旋后为了保持红黑树特性就需要在左旋前“将x的兄弟节点设为黑色”同时“将x的父节点设为红色”左旋后由于x的兄弟节点发生了变化需要更新x的兄弟节点从而进行后续处理。
1.3 示意图 2. (Case 2) x是黑黑节点x的兄弟节点是黑色x的兄弟节点的两个孩子都是黑色
2.1 现象说明
x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的两个孩子都是黑色。
2.2 处理策略
(01) 将x的兄弟节点设为“红色”。 (02) 设置“x的父节点”为“新的x节点”。
下面谈谈为什么要这样处理。(建议理解的时候通过下面的图进行对比) 这个情况的处理思想是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑黑”节点我们将x由“黑黑”节点 变成 “黑”节点多余的一个“黑”属性移到x的父节点中即x的父节点多出了一个黑属性(若x的父节点原先是“黑”则此时变成了“黑黑”若x的父节点原先时“红”则此时变成了“红黑”)。 此时需要注意的是所有经过x的分支中黑节点个数没变化但是所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)为了解决这个问题我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。 经过上面的步骤(将x的兄弟节点设为红色)多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑红”直接将“新的x节点”设为黑色即可完全解决该问题若“新的x节点”是“黑黑”则需要对“新的x节点”进行进一步处理。
2.3 示意图 3. (Case 3)x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的左孩子是红色右孩子是黑色的
3.1 现象说明
x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的左孩子是红色右孩子是黑色的。
3.2 处理策略
(01) 将x兄弟节点的左孩子设为“黑色”。 (02) 将x兄弟节点设为“红色”。 (03) 对x的兄弟节点进行右旋。 (04) 右旋后重新设置x的兄弟节点。
下面谈谈为什么要这样处理。(建议理解的时候通过下面的图进行对比) 我们处理“Case 3”的目的是为了将“Case 3”进行转换转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋为了保证右旋后它仍然是红黑树就需要在右旋前“将x的兄弟节点的左孩子设为黑色”同时“将x的兄弟节点设为红色”右旋后由于x的兄弟节点发生了变化需要更新x的兄弟节点从而进行后续处理。
3.3 示意图 4. (Case 4)x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的右孩子是红色的x的兄弟节点的左孩子任意颜色
4.1 现象说明
x是“黑黑”节点x的兄弟节点是黑色x的兄弟节点的右孩子是红色的x的兄弟节点的左孩子任意颜色。
4.2 处理策略
(01) 将x父节点颜色 赋值给 x的兄弟节点。 (02) 将x父节点设为“黑色”。 (03) 将x兄弟节点的右子节设为“黑色”。 (04) 对x的父节点进行左旋。 (05) 设置“x”为“根节点”。
下面谈谈为什么要这样处理。(建议理解的时候通过下面的图进行对比) 我们处理“Case 4”的目的是去掉x中额外的黑色将x变成单独的黑色。处理的方式是“进行颜色修改然后对x的父节点进行左旋。下面我们来分析是如何实现的。 为了便于说明我们设置“当前节点”为S(Original Son)“兄弟节点”为B(Brother)“兄弟节点的左孩子”为BLS(Brother’s Left Son)“兄弟节点的右孩子”为BRS(Brother’s Right Son)“父节点”为F(Father)。 我们要对F进行左旋。但在左旋前我们需要调换F和B的颜色并设置BRS为黑色。为什么需要这里处理呢因为左旋后F和BLS是父子关系而我们已知BL是红色如果F是红色则违背了“特性(4)”为了解决这一问题我们将“F设置为黑色”。 但是F设置为黑色之后为了保证满足“特性(5)”即为了保证左旋之后 第一“同时经过根节点和S的分支的黑色节点个数不变”。 若满足“第一”只需要S丢弃它多余的颜色即可。因为S的颜色是“黑黑”而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1现在只需将S由“黑黑”变成单独的“黑”节点即可满足“第一”。 第二“同时经过根节点和BLS的分支的黑色节点数不变”。 若满足“第二”只需要将“F的原始颜色”赋值给B即可。之前我们已经将“F设置为黑色”(即将B的颜色黑色赋值给了F)。至此我们算是调换了F和B的颜色。 第三“同时经过根节点和BRS的分支的黑色节点数不变”。 在“第二”已经满足的情况下若要满足“第三”只需要将BRS设置为“黑色”即可。 经过上面的处理之后。红黑树的特性全部得到的满足接着我们将x设为根节点就可以跳出while循环(参考伪代码)即完成了全部处理。
至此我们就完成了Case 4的处理。理解Case 4的核心是了解如何“去掉当前节点额外的黑色”。
4.3 示意图 OK至此红黑树的理论知识差不多讲完了。后续再更新红黑树的实现代码
