学编程做网站,wordpress迁移修改域名,如何创建微信公众号平台,常州淄博网站优化之前在公司组内分享了红黑树的工作原理#xff0c;今天把它整理下发出来#xff0c;希望能对大家有所帮助#xff0c;对自己也算是一个知识点的总结。这篇文章算是我写博客写公众号以来画图最多的一篇文章了#xff0c;没有之一#xff0c;我希望尽可能多地用图片来形象地…之前在公司组内分享了红黑树的工作原理今天把它整理下发出来希望能对大家有所帮助对自己也算是一个知识点的总结。这篇文章算是我写博客写公众号以来画图最多的一篇文章了没有之一我希望尽可能多地用图片来形象地描述红黑树的各种操作的前后变换原理帮助大家来理解红黑树的工作原理下面多图预警开始了。在讲红黑树之前我们首先来了解下下面几个概念二叉树排序二叉树以及平衡二叉树。二叉树二叉树指的是每个节点最多只能有两个字数的有序树。通常左边的子树称为左子树 右边的子树称为右子树 。这里说的有序树强调的是二叉树的左子树和右子树的次序不能随意颠倒。二叉树简单的示意图如下代码定义class Node {T data;Node left;Node right;
}排序二叉树所谓排序二叉树顾名思义排序二叉树是有顺序的它是一种特殊结构的二叉树我们可以对树中所有节点进行排序和检索。性质若它的左子树不空则左子树上所有节点的值均小于它的根节点的值若她的右子树不空则右子树上所有节点的值均大于它的根节点的值具有递归性排序二叉树的左子树、右子树也是排序二叉树。排序二叉树简单示意图排序二叉树退化成链表排序二叉树的左子树上所有节点的值小于根节点的值右子树上所有节点的值大于根节点的值当我们插入一组元素正好是有序的时候这时会让排序二叉树退化成链表。正常情况下排序二叉树是如下图这样的但是当插入的一组元素正好是有序的时候排序二叉树就变成了下边这样了就变成了普通的链表结构如下图所示:正常情况下的排序二叉树检索效率类似于二分查找二分查找的时间复杂度为 O(log n)但是如果排序二叉树退化成链表结构那么检索效率就变成了线性的 O(n) 的这样相对于 O(log n) 来说检索效率肯定是要差不少的。思考二分查找和正常的排序二叉树的时间复杂度都是 O(log n)那么为什么是O(log n) 关于 O(log n) 的分析下面这篇文章讲解的非常好感兴趣的可以看下这篇文章 二分查找的时间复杂度.md)文章是拿二分查找来举例的二分查找和平衡二叉树的时间复杂度是一样的理解了二分查找的时间复杂度再来理解平衡二叉树就不难了这里就不赘述了。继续回到我们的主题上为了解决排序二叉树在特殊情况下会退化成链表的问题链表的检索效率是 O(n) 相对正常二叉树来说要差不少所以有人发明了平衡二叉树和红黑树类似的平衡树。平衡二叉树平衡二叉数又被称为 AVL 树AVL 树的名字来源于它的发明作者 G.M. Adelson-Velsky 和 E.M. Landis取自两人名字的首字母。官方定义它或者是一颗空树或者具有以下性质的排序二叉树它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树。两个条件平衡二叉树必须是排序二叉树也就是说平衡二叉树他的左子树所有节点的值必须小于根节点的值它的右子树上所有节点的值必须大于它的根节点的值。左子树和右子树的深度之差的绝对值不超过1。红黑树讲了这么多概念接下来主角红黑树终于要上场了。为什么有红黑树其实红黑树和上面的平衡二叉树类似本质上都是为了解决排序二叉树在极端情况下退化成链表导致检索效率大大降低的问题红黑树最早是由 Rudolf Bayer 于 1972 年发明的。红黑树首先肯定是一个排序二叉树它在每个节点上增加了一个存储位来表示节点的颜色可以是 RED 或 BLACK 。Java 中实现红黑树大概结构图如下所示红黑树的特性性质1每个节点要么是红色要么是黑色。性质2根节点永远是黑色的。性质3所有的叶子节点都是空节点即null并且是黑色的。性质4每个红色节点的两个子节点都是黑色。从每个叶子到根的路径上不会有两个连续的红色节点。性质5从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。针对上面的 5 种性质我们简单理解下对于性质 1 和性质 2 相当于是对红黑树每个节点的约束根节点是黑色其他的节点要么是红色要么是黑色。对于性质 3 中指定红黑树的每个叶子节点都是空节点而且叶子节点都是黑色但 Java 实现的红黑树会使用 null 来代表空节点因此我们在遍历 Java里的红黑树的时候会看不到叶子节点而看到的是每个叶子节点都是红色的这一点需要注意。对于性质 5这里我们需要注意的是这里的描述是从任一节点从任一节点到它的子树的每个叶子节点黑色节点的数量都是相同的这个数量被称为这个节点的黑高。如果我们从根节点出发到每个叶子节点的路径都包含相同数量的黑色节点这个黑色节点的数量被称为树的黑色高度。树的黑色高度和节点的黑色高度是不一样的这里要注意区分。其实到这里有人可能会问了红黑树的性质说了一大堆那是不是说只要保证红黑树的节点是红黑交替就能保证树是平衡的呢其实不是这样的我们可以看来看下面这张图左边的子树都是黑色节点但是这个红黑树依然是平衡的5 条性质它都满足。这个树的黑色高度为 3从根节点到叶子节点的最短路径长度是 2该路径上全是黑色节点包括叶子节点从根节点到叶子节点最长路径为 4每个黑色节点之间会插入红色节点。通过上面的性质 4 和性质 5其实上保证了没有任何一条路径会比其他路径长出两倍所以这样的红黑树是平衡的。其实这算是一个推论红黑树在最差情况下最长的路径都不会比最短的路径长出两倍。其实红黑树并不是真正的平衡二叉树它只能保证大致是平衡的因为红黑树的高度不会无限增高在实际应用用红黑树的统计性能要高于平衡二叉树但极端性能略差。红黑树的插入想要彻底理解红黑树除了上面说到的理解红黑树的性质以外就是理解红黑树的插入操作了。红黑树的插入和普通排序二叉树的插入基本一致排序二叉树的要求是左子树上的所有节点都要比根节点小右子树上的所有节点都要比跟节点大当插入一个新的节点的时候首先要找到当前要插入的节点适合放在排序二叉树哪个位置然后插入当前节点即可。红黑树和排序二叉树不同的是红黑树需要在插入节点调整树的结构来让树保持平衡。一般情况下红黑树中新插入的节点都是红色的那么为什么说新加入到红黑树中的节点要是红色的呢这个问题可以这样理解我们从性质5中知道当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的此时假如新的黑色节点的话必然破坏规则但加入红色节点却不一定除非其父节点就是红色节点因此加入红色节点破坏规则的可能性小一些。接下来我们重点来讲红黑树插入新节点后是如何保持平衡的。给定下面这样一颗红黑树当我们插入值为66的节点的时候示意图如下很明显这个时候结构依然遵循着上述5大特性无需启动自动平衡机制调整节点平衡状态。如果再向里面插入值为51的节点呢这个时候红黑树变成了这样。这样的结构实际上是不满足性质4的红色两个子节点必须是黑色的而这里49这个红色节点现在有个51的红色节点与其相连。这个时候我们需要调整这个树的结构来保证红黑树的平衡。首先尝试将49这个节点设置为黑色如下示意图。这个时候我们发现黑高是不对的其中 60-56-45-49-51-null 这条路径有 4 个黑节点其他路径的黑色节点是 3 个。接着调整红黑树我们再次尝试把45这个节点设置为红色的如下图所示这个时候我们发现问题又来了56-45-43 都是红色节点的出现了红色节点相连的问题。于是我们需要再把 56 和 43 设置为黑色的如下图所示。于是我们把 68 这个红色节点设置为黑色的。对于这种红黑树插入节点的情况下我们可以只需要通过变色就可以保持树的平衡了。但是并不是每次都是这么幸运的当变色行不通的时候我们需要考虑另一个手段就是旋转了。例如下面这种情况同样还是拿这颗红黑树举例。现在这颗红黑树我们现在插入节点65。我们尝试把 66 这个节点设置为黑色如下图所示。这样操作之后黑高又出现不一致的情况了60-68-64-null 有 3 个黑色节点而60-68-64-66-null 这条路径有 4 个黑色节点这样的结构是不平衡的。或者我们把 68 设置为黑色把 64 设置为红色如下图所示但是同样的问题上面这颗红黑树的黑色高度还是不一致60-68-64-null 和 60-68-64-66-null 这两条路径黑色高度还是不一致。这种情况如果只通过变色的情况是不能保持红黑树的平衡的。红黑树的旋转接下来我们讲讲红黑树的旋转旋转分为左旋和右旋。左旋文字描述逆时针旋转两个节点让一个节点被其右子节点取代而该节点成为右子节点的左子节点。文字描述太抽象接下来看下图片展示。首先断开节点PL与右子节点G的关系同时将其右子节点的引用指向节点C2然后断开节点G与左子节点C2的关系同时将G的左子节点的应用指向节点PL。接下来再放下 gif 图希望能帮助大家更好地理解左旋图片来自网络。右旋文字描述顺时针旋转两个节点让一个节点被其左子节点取代而该节点成为左子节点的右子节点。右旋的图片展示首先断开节点G与左子节点PL的关系同时将其左子节点的引用指向节点C2然后断开节点PL与右子节点C2的关系同时将PL的右子节点的应用指向节点G。右旋的gif展示图片来自网络:介绍完了左旋和右旋基本操作我们来详细介绍下红黑树的几种旋转场景。左左节点旋转插入节点的父节点是左节点插入节点也是左节点如下图所示的红黑树我们插入节点是65。操作步骤如下可以围绕祖父节点 69 右旋再结合变色步骤如下所示左右节点旋转插入节点的父节点是左节点插入节点是右节点还是上面这颗红黑树我们再插入节点 67。这种情况我们可以这样操作先围绕父节点 66 左旋然后再围绕祖父节点 69 右旋最后再将 67 设置为黑色把 69 设置为红色如下图所示。右左节点旋转插入节点的父节点是右节点插入节点左节点如下图这种情况我们要插入节点68。这种情况我们可以先围绕父节点 69 右旋接着再围绕祖父节点 66 左旋最后把 68 节点设置为黑色把 66 设置为红色我们的具体操作步骤如下所示。右右节点旋转插入节点的父节点是右节点插入节点也是右节点还是来上面的图来举例我们在这颗红黑树上插入节点 70 。我们可以这样操作围绕祖父节点 66 左旋再把旋转后的根节点 69 设置为黑色把 66 这个节点设置为红色。具体可以参看下图红黑树在 Java 中的实现Java 中的红黑树实现类是 TreeMap 接下来我们尝试从源码角度来逐行解释 TreeMap 这一套机制是如何运作的。// TreeMap中使用Entry来描述每个节点static final class EntryK,V implements Map.EntryK,V {K key;V value;EntryK,V left;EntryK,V right;EntryK,V parent;boolean color BLACK;...}
复制代码TreeMap 的put方法。public V put(K key, V value) {//先以t保存链表的root节点EntryK,V t root;//如果tnull,表明是一个空链表即该TreeMap里没有任何Entry作为rootif (t null) {compare(key, key); // type (and possibly null) check//将新的key-value创建一个Entry并将该Entry作为rootroot new Entry(key, value, null);size 1;//记录修改次数加1modCount;return null;}int cmp;EntryK,V parent;// split comparator and comparable pathsComparator? super K cpr comparator;//如果比较器cpr不为null即表明采用定制排序if (cpr ! null) {do {//使用parent上次循环后的t所引用的Entryparent t;//将新插入的key和t的key进行比较cmp cpr.compare(key, t.key);//如果新插入的key小于t的keyt等于t的左边节点if (cmp 0)t t.left;//如果新插入的key大于t的keyt等于t的右边节点 else if (cmp 0)t t.right;else//如果两个key相等新value覆盖原有的value并返回原有的valuereturn t.setValue(value);} while (t ! null);}else {if (key null)throw new NullPointerException();SuppressWarnings(unchecked)Comparable? super K k (Comparable? super K) key;do {parent t;cmp k.compareTo(t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);} while (t ! null);}//将新插入的节点作为parent节点的子节点EntryK,V e new Entry(key, value, parent);//如果新插入key小于parent的key,则e作为parent的左子节点if (cmp 0)parent.left e;//如果新插入key小于parent的key则e作为parent的右子节点elseparent.right e;//修复红黑树fixAfterInsertion(e);size;modCount;return null;}
复制代码
//插入节点后修复红黑树
private void fixAfterInsertion(EntryK,V x) {x.color RED;//直到x节点的父节点不是根且x的父节点是红色while (x ! null x ! root x.parent.color RED) {//如果x的父节点是其父节点的左子节点if (parentOf(x) leftOf(parentOf(parentOf(x)))) {//获取x的父节点的兄弟节点EntryK,V y rightOf(parentOf(parentOf(x)));//如果x的父节点的兄弟节点是红色if (colorOf(y) RED) { //将x的父节点设置为黑色setColor(parentOf(x), BLACK);//将x的父节点的兄弟节点设置为黑色setColor(y, BLACK);//将x的父节点的父节点设为红色setColor(parentOf(parentOf(x)), RED);x parentOf(parentOf(x));}//如果x的父节点的兄弟节点是黑色else { //TODO 对应情况第二种左右节点旋转//如果x是其父节点的右子节点if (x rightOf(parentOf(x))) {//将x的父节点设为xx parentOf(x);//右旋转rotateLeft(x);}//把x的父节点设置为黑色setColor(parentOf(x), BLACK);//把x的父节点父节点设为红色setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}}//如果x的父节点是其父节点的右子节点else {//获取x的父节点的兄弟节点EntryK,V y leftOf(parentOf(parentOf(x)));//只着色的情况对应的是最开始例子没有旋转操作但是要对应多次变换//如果x的父节点的兄弟节点是红色 if (colorOf(y) RED) {//将x的父节点设置为黑色setColor(parentOf(x), BLACK);//将x的父节点的兄弟节点设为黑色setColor(y, BLACK);//将X的父节点的父节点G设置红色setColor(parentOf(parentOf(x)), RED);//将x设为x的父节点的节点x parentOf(parentOf(x));}//如果x的父节点的兄弟节点是黑色else {//如果x是其父节点的左子节点if (x leftOf(parentOf(x))) {//将x的父节点设为xx parentOf(x);//右旋转rotateRight(x);}//将x的父节点设为黑色setColor(parentOf(x), BLACK);//把x的父节点的父节点设为红色setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}//将根节点强制设置为黑色root.color BLACK;
}
复制代码TreeMap的插入节点和普通的排序二叉树没啥区别唯一不同的是在TreeMap 插入节点后会调用方法fixAfterInsertion(e)来重新调整红黑树的结构来让红黑树保持平衡。我们重点关注下红黑树的fixAfterInsertion(e)方法接下来我们来分别介绍两种场景来演示fixAfterInsertion(e)方法的执行流程。第一种场景只需变色即可平衡同样是拿这颗红黑树举例现在我们插入节点 51。当我们需要插入节点51的时候这个时候TreeMap 的 put 方法执行后会得到下面这张图。接着调用fixAfterInsertion(e)方法如下代码流程所示。当第一次进入循环后执行后会得到下面的红黑树结构。在把 x 重新赋值后重新进入 while 循环此时的 x 节点为 45 。执行上述流程后得到下面所示的红黑树结构。这个时候x被重新赋值为60因为60是根节点所以会退出 while 循环。在退出循序后会再次把根节点设置为黑色得到最终的结构如下图所示。最后经过两次执行while循环后我们的红黑树会调整成现在这样的结构这样的红黑树结构是平衡的所以路径的黑高一致并且没有红色节点相连的情况。第二种场景 旋转搭配变色来保持平衡接下来我们再来演示第二种场景需要结合变色和旋转一起来保持平衡。给定下面这样一颗红黑树现在我们插入节点66得到如下树结构。同样地我们进入fixAfterInsertion(e)方法。最终我们得到的红黑树结构如下图所示调整成这样的结构我们的红黑树又再次保持平衡了。演示 TreeMap 的流程就拿这两种场景举例了其他的就不一一举例了。红黑树的删除因为之前的分享只整理了红黑树的插入部分本来想着红黑树的删除就不整理了有人跟我反馈说红黑树的删除相对更复杂于是索性还是把红黑树的删除再整理下。删除相对插入来说的确是要复杂一点但是复杂的地方是因为在删除节点的这个操作情况有很多种但是插入不一样插入节点的时候实际上这个节点的位置是确定的在节点插入成功后只需要调整红黑树的平衡就可以了。但是删除不一样的是删除节点的时候我们不能简单地把这个节点设置为null因为如果这个节点有子节点的情况下不能简单地把当前删除的节点设置为null这个被删除的节点的位置需要有新的节点来填补。这样一来需要分多种情况来处理了。删除节点是根节点直接删除根节点即可。删掉节点的左子节点和右子节点都是为空直接删除当前节点即可。删除节点有一个子节点不为空这个时候需要使用子节点来代替当前需要删除的节点然后再把子节点删除即可。给定下面这棵树当我们需要删除节点69的时候。首先用子节点代替当前待删除节点然后再把子节点删除。最终的红黑树结构如下面所示这个结构的红黑树我们是不需要通过变色旋转来保持红黑树的平衡了因为将子节点删除后树已经是平衡的了。还有一种场景是当我们待删除节点是黑色的黑色的节点被删除后树的黑高就会出现不一致的情况这个时候就需要重新调整结构。还是拿上面这颗删除节点后的红黑树举例我们现在需要删除节点67。因为67 这个节点的两个子节点都是null所以直接删除,得到如下图所示结构这个时候我们树的黑高是不一致的左边黑高是3右边是2所以我们需要把64节点设置为红色来保持平衡。删除节点两个子节点都不为空删除节点两个子节点都不为空的情况下跟上面有一个节点不为空的情况下也是有点类似同样是需要找能替代当前节点的节点找到后把能替代删除节点值复制过来然后再把替代节点删除掉。先找到替代节点也就是前驱节点或者后继节点然后把前驱节点或者后继节点复制到当前待删除节点的位置然后在删除前驱节点或者后继节点。那么什么叫做前驱什么叫做后继呢 前驱是左子树中最大的节点后继则是右子树中最小的节点。前驱或者后继都是最接近当前节点的节点当我们需要删除当前节点的时候也就是找到能替代当前节点的节点能够替代当前节点肯定是最接近当前节点。在当前删除节点两个子节点不为空的场景下我们需要再进行细分主要分为以下三种情况。第一种前驱节点为黑色节点同时有一个非空节点如下面这样一棵树我们需要删除节点64首先找到前驱节点把前驱节点复制到当前节点接着删除前驱节点。这个时候63和60这个节点都是红色的我们尝试把60这个节点设置为红色即可使整个红黑树达到平衡。第二种前驱节点为黑色节点同时子节点都为空前驱节点是黑色的子节点都为空这个时候操作步骤与上面基本类似。如下操作步骤因为要删除节点64接着找到前驱节点63把63节点复制到当前位置然后将前驱节点63删除掉变色后出现黑高不一致的情况下最后把63节点设置为黑色把65节点设置为红色这样就能保证红黑树的平衡。第三种前驱节点为红色节点同时子节点都为空给定下面这颗红黑树我们需要删除节点64的时候。同样地我们找到64的前驱节点63接着把63赋值到64这个位置。然后删除前驱节点。删除节点后不需要变色也不需要旋转即可保持树的平衡。终于把红黑树的基本原理部分写完了用了很多示意图这篇文章是在之前分享的 ppt 上再整理出来我觉得自己应该算是把基本操作讲明白了整理这篇文章前前后后用了近一周左右因为平时上班基本上只有周末有时间才有时间整理如有问题请留言讨论。如果您觉得写得还可以请您帮忙点个赞您的点赞真的是对我最大的支持也是我能继续写下去的动力感谢。转自https://juejin.im/post/5df4aa...怒求一波赞能坚持看到这儿的都是努力学习的人我们相信努力奋斗终将会使我们过上自己想要的生活。我会努力更新原创干货也会收集一些精品文章供大家日常学习。不论如何如果大家觉得在我这儿能学到点东西在这儿厚着脸皮的向大家求个赞求个关注求个分享。我一定不会辜负大家为大家的学习之路添加更多精彩的文章。创作不易坚持不易大家的支持是我最大的动力再次谢谢大家。下面这篇文章是我收集的5000G的精品VIP视频的部分目录都是会免费分享给大家的大家可以点进去看看是否有自己需要的如果没有大家也可以通过公众号或者微信私聊我我也会尽力去收集。java架构师作为Java开发我是如何在一年之内让自己的月薪爆炸式提升zhuanlan.zhihu.com
