网站怎么改域名,南通网站建设推广专家,做外贸c2c网站有哪些,山东网站推广有限公司转载自 coolblog 算法与数据结构“一、红黑树简介红黑树是一种自平衡的二叉查找树#xff0c;是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明#xff0c;在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来#xff0c;在1978年被 Leo J. Guibas 和 Robert…转载自 coolblog 算法与数据结构“一、红黑树简介红黑树是一种自平衡的二叉查找树是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率它可在 O(logN) 时间内完成查找、增加、删除等操作。因此红黑树在业界应用很广泛比如 Java 中的 TreeMapJDK 1.8 中的 HashMap、C STL 中的 map 均是基于红黑树结构实现的。考虑到红黑树是一种被广泛应用的数据结构所以我们很有必要去弄懂它。“二、红黑树的性质学过二叉查找树的同学都知道普通的二叉查找树在极端情况下可退化成链表此时的增删查效率都会比较低下。为了避免这种情况就出现了一些自平衡的查找树比如 AVL红黑树等。这些自平衡的查找树通过定义一些性质将任意节点的左右子树高度差控制在规定范围内以达到平衡状态。以红黑树为例红黑树通过如下的性质定义实现自平衡
节点是红色或黑色。根是黑色。所有叶子都是黑色叶子是NIL节点。每个红色节点必须有两个黑色的子节点。从每个叶子到根的所有路径上不能有两个连续的红色节点。从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点简称黑高。
有了上面的几个性质作为限制即可避免二叉查找树退化成单链表的情况。但是仅仅避免这种情况还不够这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长那么在对这些路径上的及诶单进行增删查操作时效率也会大大降低。这个时候性质4和性质5用途就凸显了有了这两个性质作为约束即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。原因如下
当某条路径最短时这条路径必然都是由黑色节点构成。当某条路径长度最长时这条路径必然是由红色和黑色节点相间构成性质4限定了不能出现两个连续的红色节点。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时在路径最长的情况下路径上红色节点数量 黑色节点数量。该路径长度为两倍黑色节点数量也就是最短路径长度的2倍。举例说明一下请看下图上图画出了从根节点 M 出发的到其叶子节点的最长和最短路径。这里偷懒只画出了两条最长路径实际上最长路径有4条分别为
M - Q - O - N
M - Q - O - p
M - Q - Y - X
M - Q - Y - Z
长度为4最短路径为 M - E长度为2。最长路径的长度正好为最短路径长度的2倍。
前面说了关于红黑树的一些性质这里还需要补充一些其他方面的东西。在红黑树简介一节中说到红黑树被发明出来的时候并不叫红黑树而是叫做对称二叉 B 树从名字中可发现红黑树和 B 树这里指的是2-3树或许有一定的关联事实也正是如此。如果对红黑树的性质稍加修改就能让红黑树和B树形成一一对应的关系。关于红黑树和 B 树关系的细节这里不展开说明了有兴趣的同学可以参考《算法》第4版那本书上讲的很透彻。“三、红黑树操作红黑树的基本操作和其他树形结构一样一般都包括查找、插入、删除等操作。前面说到红黑树是一种自平衡的二叉查找树既然是二叉查找树的一种那么查找过程和二叉查找树一样比较简单这里不再赘述。相对于查找操作红黑树的插入和删除操作就要复杂的多。尤其是删除操作要处理的情况比较多不过大家如果静下心来去看会发现其实也没想的那么难。好了废话就说到这接下来步入正题吧。
3.1 旋转操作
在分析插入和删除操作前这里需要插个队先说明一下旋转操作这个操作在后续操作中都会用得到。旋转操作分为左旋和右旋左旋是将某个节点旋转为其右孩子的左孩子而右旋是节点旋转为其左孩子的右孩子。这话听起来有点绕所以还是请看下图上图包含了左旋和右旋的示意图这里以右旋为例进行说明右旋节点 M 的步骤如下
1、将节点 M 的左孩子引用指向节点 E 的右孩子
2、将节点 E 的右孩子引用指向节点 M完成旋转上面分析了右旋操作左旋操作与此类似大家有兴趣自己画图试试吧这里不再赘述了。旋转操作本身并不复杂这里先分析到这吧。
3.2 插入
红黑树的插入过程和二叉查找树插入过程基本类似不同的地方在于红黑树插入新节点后需要进行调整以满足红黑树的性质。性质1规定红黑树节点的颜色要么是红色要么是黑色那么在插入新节点时这个节点应该是红色还是黑色呢答案是红色原因也不难理解。如果插入的节点是黑色那么这个节点所在路径比其他路径多出一个黑色节点这个调整起来会比较麻烦参考红黑树的删除操作就知道为啥多一个或少一个黑色节点时调整起来这么麻烦了。如果插入的节点是红色此时所有路径上的黑色节点数量不变仅可能会出现两个连续的红色节点的情况。这种情况下通过变色和旋转进行调整即可比之前的简单多了。
接下来将分析插入红色节点后红黑树的情况。这里假设要插入的节点为 NN 的父节点为 P祖父节点为 G叔叔节点为 U。插入红色节点后会出现5种情况分别如下
情况一
插入的新节点 N 是红黑树的根节点这种情况下我们把节点 N 的颜色由红色变为黑色性质2根是黑色被满足。同时 N 被染成黑色后红黑树所有路径上的黑色节点数量增加一个性质5从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点仍然被满足。情况二
N 的父节点是黑色这种情况下性质4每个红色节点必须有两个黑色的子节点和性质5没有受到影响不需要调整。情况三N 的父节点是红色节点 P 为红色其父节点必然为黑色叔叔节点 U 也是红色。由于 P 和 N 均为红色所有性质4被打破此时需要进行调整。这种情况下先将 P 和 U 的颜色染成黑色再将 G 的颜色染成红色。此时经过 G 的路径上的黑色节点数量不变性质5仍然满足。但需要注意的是 G 被染成红色后可能会和它的父节点形成连续的红色节点此时需要递归向上调整。情况四
N 的父节点为红色叔叔节点为黑色。节点 N 是 P 的右孩子且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋调整 N 与 P 的位置。接下来按照情况五进行处理以恢复性质4。这里需要特别说明一下上图中的节点 N 并非是新插入的节点。当 P 为红色时P 有两个孩子节点且孩子节点均为黑色这样从 G 出发到各叶子节点路径上的黑色节点数量才能保持一致。既然 P 已经有两个孩子了所以 N 不是新插入的节点。情况四是由以 N 为根节点的子树中插入了新节点经过调整后导致 N 被变为红色进而导致了情况四的出现。考虑下面这种情况PR 节点就是上图的 N 节点如上图插入节点 N 并按情况三处理。此时 PR 被染成了红色与 P 节点形成了连续的红色节点这个时候就需按情况四再次进行调整。
情况五
N 的父节点为红色叔叔节点为黑色。N 是 P 的左孩子且节点 P 是 G 的左孩子。此时对 G 进行右旋调整 P 和 G 的位置并互换颜色。经过这样的调整后性质4被恢复同时也未破坏性质5。插入总结
上面五种情况中情况一和情况二比较简单情况三、四、五稍复杂。但如果细心观察会发现这三种情况的区别在于叔叔节点的颜色如果叔叔节点为红色直接变色即可。如果叔叔节点为黑色则需要选选择再交换颜色。当把这三种情况的图画在一起就区别就比较容易观察了如下图3.3 删除
相较于插入操作红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子如果有两个孩子不能直接删除该节点。而是要先找到该节点的前驱该节点左子树中最大的节点或者后继该节点右子树中最小的节点然后将前驱或者后继的值复制到要删除的节点中最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点只要节点里的值最终被删除就行了至于树结构如何变化这个并不重要。
红黑树删除操作的复杂度在于删除节点的颜色当删除的节点是红色时直接拿其孩子节点补空位即可。因为删除红色节点性质5从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点仍能够被满足。当删除的节点是黑色时那么所有经过该节点的路径上的黑节点数量少了一个破坏了性质5。如果该节点的孩子为红色直接拿孩子节点替换被删除的节点并将孩子节点染成黑色即可恢复性质5。但如果孩子节点为黑色处理起来就要复杂的多。分为6种情况下面会展开说明。
在展开说明之前我们先做一些假设方便说明。这里假设最终被删除的节点为X至多只有一个孩子节点其孩子节点为NX的兄弟节点为SS的左节点为 SL右节点为 SR。接下来讨论是建立在节点 X 被删除节点 N 替换X的基础上进行的。这里说明把被删除的节点X特地拎出来说一下的原因是防止大家误以为节点N会被删除不然后面就会看不明白。在上面的基础上接下来就可以展开讨论了。红黑树删除有6种情况分别是
情况一
N 是新的根。在这种情形下我们就做完了。我们从所有路径去除了一个黑色节点而新根是黑色的所以性质都保持着。上面是维基百科中关于红黑树删除的情况一说明由于没有配图看的有点晕。经过思考我觉得可能会是下面这种情形
要删除的节点 X 是根节点且左右孩子节点均为空节点此时将节点 X 用空节点替换完成删除操作。
可能还有其他情形大家如果知道烦请告知。
情况二
S 为红色其他节点为黑色。这种情况下可以对 N 的父节点进行左旋操作然后互换 P 与 S 颜色。但这并未结束经过节点 P 和 N 的路径删除前有3个黑色节点P - X - N现在只剩两个了P - N。比未经过 N 的路径少一个黑色节点性质5仍不满足还需要继续调整。不过此时可以按照情况四、五、六进行调整。情况三
N 的父节点兄弟节点 S 和 S 的孩子节点均为黑色。这种情况下可以简单的把 S 染成红色所有经过 S 的路径比之前少了一个黑色节点这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点此时需要从情况一开始对 P 进行平衡处理。情况四
N 的父节点是红色S 和 S 孩子为黑色。这种情况比较简单我们只需交换 P 和 S 颜色即可。这样所有通过 N 的路径上增加了一个黑色节点所有通过 S 的节点的路径必然也通过 P 节点由于 P 与 S 只是互换颜色并不影响这些路径。情况五
S 为黑色S 的左孩子为红色右孩子为黑色。N 的父节点颜色可红可黑且 N 是 P 左孩子。这种情况下对 S 进行右旋操作并互换 S 和 SL 的颜色。此时所有路径上的黑色数量仍然相等N 兄弟节点的由 S 变为了 SL而 SL 的右孩子变为红色。接下来我们到情况六继续分析。情况六
S 为黑色S 的右孩子为红色。N 的父节点颜色可红可黑且 N 是其父节点左孩子。这种情况下我们对 P 进行左旋操作并互换 P 和 S 的颜色并将 SR 变为黑色。因为 P 变为黑色所以经过 N 的路径多了一个黑色节点经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径则有以下两种情况
该路径经过 N 新的兄弟节点 SL 那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色对于经过 SL 的路径不影响。
该路径经过 N 新的叔叔节点 S那它之前必然经过 P、 S 和 SR而现在它只经过 S 和 SR。在对 P 进行左旋并与 S 换色后经过 SR 的路径少了一个黑色节点性质5被打破。另外由于 S 的颜色可红可黑如果 S 是红色的话会与 SR 形成连续的红色节点打破性质4每个红色节点必须有两个黑色的子节点。此时仅需将 SR 由红色变为黑色即可同时恢复性质4和性质5从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。。删除总结
红黑树删除的情况比较多大家刚开始看的时候可能会比较晕。可能会产生这样的疑问为啥红黑树会有这种删除情况为啥又会有另一种情况它们之间有什么联系和区别和大家一样我刚开始看的时候也有这样的困惑直到我把所有情况对应的图形画在一起时拨云见日一切都明了了。此时天空中出现了4个字原来如此、原来如此、原来如此。所以请看图吧四、总结
红黑树是一种重要的二叉树应用广泛但在很多数据结构相关的书本中出现的次数并不多。很多书中要么不说要么就一笔带过并不会进行详细的分析这可能是因为红黑树比较复杂的缘故。我在学习红黑树的时候也找了很多资料但总体感觉讲的都不太好。尤其是在我学习删除操作的时候很多资料是在让人看不下去看的我很痛苦。直到我看到维基百科上关于红黑树的分析时很是欣喜。这篇文章分析的很有条理言简意赅比很多资料好了太多。本文对红黑树的分析也主要参考了维基百科中的红黑树分析并对维基百科中容易让人产生疑问和误解的地方进行了说明。同时维基百科中文版红黑树文中的图片较为模糊这里我重新进行了绘制。需要说明的是维基百科中文版无法打开了文中关于维基百科的链接都是英文版的。另外在给大家推荐一个数据结构可视化的网站里面包含常见数据结构可视化过程地址为https://www.cs.usfca.edu/~galles/visualization/Algorithms.html。
另外由于红黑树本身比较复杂实现也较为复杂。在写这篇文章之前我曾尝试过用 Java 语言实现红黑树的增删操作最终只写出了新增节点操作删除没做出来。而且自己写的新增逻辑实在在太繁琐写的不好看没脸拿出来 show。所以最后把 Java 中的 TreeMap 增删相关源码拷出来按照自己的需求把源码修改了一下也勉强算是实现了红黑树吧。以下是代码RBTree.java。
package search;import java.util.*;/** * 红黑树实现该实现核心逻辑由 TreeMap 源码修改而来 * * author code4wt * date 2017-12-23 17:26:28 */public class RBTreeT extends ComparableT { private final static boolean RED true; private final static boolean BLACK false; private TreeNodeT root; public boolean contains(T value) { return Objects.nonNull(getNode(value)); } public void putAll(CollectionT collection) { collection.forEach(this::put); } public void put(T value) { if (Objects.isNull(value)) { throw new NullPointerException(); } TreeNodeT t root; if (Objects.isNull(t)) { root new TreeNode(null, null, null, value); return; } int cmp; TreeNodeT parent; do { parent t; cmp value.compareTo(t.value); if (cmp 0) { return; } else if (cmp 0) { t t.right; } else { t t.left; } } while (Objects.nonNull(t)); TreeNodeT e new TreeNode(parent, null, null, value); if (cmp 0) { parent.left e; } else { parent.right e; } fixAfterInsertion(e); } public void remove(T value) { TreeNodeT p getNode(value); if (Objects.nonNull(value)) { deleteNode(p); } } public void clear() { root null; } private TreeNodeT getNode(T value) { if (Objects.isNull(value)) { throw new NullPointerException(); } TreeNodeT p root; while (Objects.nonNull(p)) { int cmp value.compareTo(p.value); if (cmp 0) { p p.left; } else if (cmp 0) { p p.right; } else { return p; } } return null; } private void deleteNode(TreeNodeT p) { // 节点 p 有两个孩子节点时先找到 p 节点的后继节点 if (p.left ! null p.right ! null) { TreeNodeT s successor(p); p.value s.value; p s; } TreeNodeT replacement (p.left ! null ? p.left : p.right); if (replacement ! null) { replacement.parent p.parent; if (p.parent null) { root replacement; } else if (p p.parent.left) { p.parent.left replacement; } else { p.parent.right replacement; } p.left p.right p.parent null; if (p.color BLACK) { fixAfterDeletion(replacement); } } else if (p.parent null) { root null; } else { // 待删除的节点没有孩子节点 // 如果删除的节点是黑色则需要先进行修复 if (p.color BLACK) { fixAfterDeletion(p); } // 将待删除节点从树中删除 if (p.parent ! null) { if (p p.parent.left) { p.parent.left null; } else if (p p.parent.right) { p.parent.right null; } p.parent null; } } } private TreeNodeT successor(TreeNodeT t) { if (Objects.isNull(t)) { return null; } if (t.right ! null) { TreeNodeT p t.right; while (p.left ! null) { p p.left; } return p; } else { TreeNodeT p t.parent; TreeNodeT ch t; while (p ! null ch p.right) { ch p; p p.parent; } return p; } } private void rotateLeft(TreeNodeT p) { if (Objects.nonNull(p)) { TreeNodeT r p.right; p.right r.left; if (r.left ! null) { r.left.parent p; } r.parent p.parent; if (p.parent null) { root r; } else if (p.parent.left p) { p.parent.left r; } else { p.parent.right r; } r.left p; p.parent r; } } /** From CLR */ private void rotateRight(TreeNodeT p) { if (Objects.nonNull(p)) { TreeNodeT l p.left; p.left l.right; if (l.right ! null) { l.right.parent p; } l.parent p.parent; if (p.parent null) { root l; } else if (p.parent.right p) { p.parent.right l; } else { p.parent.left l; } l.right p; p.parent l; } } /** From CLR */ private void fixAfterInsertion(TreeNodeT x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { TreeNodeT y rightOf(parentOf(parentOf(x))); if (colorOf(y) RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x rightOf(parentOf(x))) { x parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { TreeNodeT y leftOf(parentOf(parentOf(x))); if (colorOf(y) RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x leftOf(parentOf(x))) { x parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color BLACK; } private void fixAfterDeletion(TreeNodeT x) { while (x ! root colorOf(x) BLACK) { if (x leftOf(parentOf(x))) { TreeNodeT sib rightOf(parentOf(x)); if (colorOf(sib) RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) BLACK colorOf(rightOf(sib)) BLACK) { setColor(sib, RED); x parentOf(x); } else { if (colorOf(rightOf(sib)) BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x root; } } else { // symmetric TreeNodeT sib leftOf(parentOf(x)); if (colorOf(sib) RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) BLACK colorOf(leftOf(sib)) BLACK) { setColor(sib, RED); x parentOf(x); } else { if (colorOf(leftOf(sib)) BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x root; } } } setColor(x, BLACK); } private boolean colorOf(TreeNodeT p) { return (p null ? BLACK : p.color); } private TreeNodeT parentOf(TreeNodeT p) { return (p null ? null: p.parent); } private void setColor(TreeNodeT p, boolean c) { if (p ! null) { p.color c; } } private TreeNodeT leftOf(TreeNodeT p) { return (p null) ? null: p.left; } private TreeNodeT rightOf(TreeNodeT p) { return (p null) ? null: p.right; } private class TreeNodeT extends ComparableT { TreeNodeT parent; TreeNodeT left; TreeNodeT right; T value; boolean color; public TreeNode(TreeNodeT parent, TreeNodeT left, TreeNodeT right, T value) { this.parent parent; this.left left; this.right right; this.value value; this.color RED; } Override public String toString() { return value , (color RED ? r : b); } }}
最后如果你也在学习红黑树希望这篇文章能够帮助到你。另外由于红黑树本身比较复杂加之本人水平有限难免会出一些错误。如果有错还望大家指出来我们共同讨论。
