【.com原创文章】学过数据结构的都知道二叉树的概念，二叉树的常见类型有很多，完全二叉树，满二叉树，二叉搜索树，平衡二叉树，完美二叉树等。图片来自Pexels。我们今天要说的红黑树是一种非严格平衡的二叉树。平衡二叉树基于二叉搜索树，具有自动保持平衡的特性。插入、查找、删除的效率都比较高。高的。红黑树也是TreeMap存储结构的基石。二叉搜索树二叉搜索树也称为二叉搜索树、二叉排序树。让我们看一下典型的二叉搜索树。这样的二叉树有什么规律和特点呢？二叉搜索树具有以下特点：节点的左子树比节点本身小。节点的右子树比节点本身大。左右子树也是二叉搜索树。下图是一个典型的二叉搜索树：二叉搜索树是平衡二叉树的基础。它的搜索步骤如何。我们想从二叉树中找到值为58的节点。第一步：先找到根节点，即值为60的节点。第二步：比较我们要找的值58和节点的大小。如果相等，那么恭喜，已经找到了；如果小于，则继续寻找左子树；如果大于，则找到正确的子树。显然58<60，所以我们找到左子树的56号节点，此时我们已经定位到了56号节点。第三步：按照第二步的规则继续查找。58>56我们需要继续寻找右子树，我们已经定位到了右子树节点58，恭喜，此时已经找到了。经过三步我们就找到了。其实就是我们通常所说的二分查找。这种二叉搜索树看起来效率很高，但是它也有缺陷，比如下面的二叉搜索树。看到这样的二叉搜索树是不是很尴尬，典型的长腿瘸子，不过它也是二叉搜索树，如果我们要找一个值为50的节点，基本上和单颗没什么区别-链表查询，性能会大打折扣。这时候我们的平衡二叉树就登场了。平衡二叉树是在二叉搜索树的基础上发展起来的，具有自动保持平衡的特性。上面那个长腿瘸子的二叉搜索树自动平衡后，可能会变成像下面这样的二叉树。自动平衡后，寻找值为50的节点，搜索性能会提高很多。红黑树是一种非严格平衡的二叉搜索树。红黑树规则特点红黑树具体的规则和特点是什么？具体如下：节点被分类为红色或黑色。根节点必须是黑色的。叶节点全黑且为空。连接到红色节点的两个子节点都是黑色的（相邻的红色节点不会出现在红黑树中）。从任一节点开始，到每个叶节点的路径包含相同数量的黑色节点。新加入红黑树的节点是红色节点。好像规矩挺多的。没错，因为红黑树也是平衡二叉树，需要有自动保持平衡的性质。以上6条规则就是红黑树自动保持平衡需要具备的规则。让我们看一下典型的红黑树是什么样子的。首先，让我们解释一下规则。除了字面意义外，还有哪些隐含意义？①从根节点到叶子节点的最长路径不大于最短路径两倍于该路径的路径如何是最短路径？由规则5可知，根节点到每个叶节点的黑色节点个数相同，则纯黑色节点构成的路径为最短路径。什么样的路径是最长的路径？根据规则4和3，如果有红色节点，则必须有连接的黑色节点。当红色节点和黑色节点的个数相同时，就是最长路径，即黑色节点（或红色节点）*2。②为什么说红黑树中新加入的节点是红节点？由规则4可知，当前红黑树中从根节点到每个叶子节点的黑节点个数相同。这时，如果新节点是黑节点的话，就必须打破规则。但是并不是一定要加红节点，除非它的父节点是红节点，所以加红节点不太可能破坏规则，我们下面举个例子。什么情况下，红黑树的结构会被破坏？破坏后如何??保持平衡？维持平衡的方式主要有两种：【变色】和【旋转】。【旋转】分为【左旋】和【右旋】。这两种方法可以相互结合。让我们用插入和删除两种场景的例子来说明。红黑树节点插入当我们插入一个值为66的节点时，红黑树变成了这样：自动平衡机制调整节点平衡状态。如果往里面插入一个值为51的节点，红黑树就变成了这样：很明显，当前的结构不符合规则4，这时候就需要启动自动平衡机制来调整节点平衡状态。颜色变化我们可以通过改变颜色使结构满足红黑树的规则：首先解决结构不遵循规则4的问题（红色节点相连，节点49-51），节点49需要改为黑色。此时我们发现又违反了规则5（56-49-51-XX路径中的黑色节点超出了其他路径），那么我们将节点45改为红色节点。哈哈，姑娘，又违反了规则4（红色节点相连，节点56-45-43），那我们把56号节点和43号节点改成黑色节点。但是我们发现又违反了规则5（60-56-XX路径的黑色节点比60-68-XX多），所以我们需要将节点68调整为黑色。完成的！最后调整后的树是：但并不总是那么幸运，直接通过改变颜色就可以达到目的，大多数时候需要通过旋转来解决。例如，在下面这棵树的基础上，添加节点65：插入节点65后，执行以下步骤：这时，你会发现对于节点64，无论是红色节点还是黑色节点，都会违反规则5，路径中的黑色节点始终无法达成一致，此时仅通过[变色]已经无法达到目的。我们需要用到旋转操作，当然【旋转】操作一般需要和【变色】操作结合使用。旋转包括【左旋转】和【右旋转】。左旋转：逆时针旋转两个节点，使一个节点被其右子节点替换，该节点成为右子节点的左子节点。左手操作步骤如下：首先断开节点PL与右子节点G的关系，将其右子节点的引用指向节点C2；然后断开节点G与左子节点C2的关系，同时将G的左子节点的应用点指向节点PL。右旋转：顺时针旋转两个节点，使一个节点被其左子节点替换，该节点成为左子节点的右子节点。右手操作步骤如下：首先断开节点G与左子节点PL的关系，同时将其左子节点的引用指向节点C2；然后断开节点PL和右子节点C2的关系，同时设置节点的应用点为节点G。不能通过改变颜色旋转的场景分为以下四种：左节点和左节点rotation在这种情况下，父节点和插入的节点都是左节点，如下图所示（旋转原图1）。本例中，我们要插入65号节点，规则如下：使用祖父节点【右旋转】，搭配【变色】。根据规则，步骤如下：左右节点旋转在这种情况下，父节点是左节点，插入的节点是右节点。在旋转后的原图1中，我们要插入节点67，规则如下：先是父节点[左手]，再是祖父节点[右手]，有[变色]??。按照规则，步骤如下：左右节点旋转的情况下，父节点为右节点，插入的节点为左节点，如下图（旋转原图2).本例中，我们需要插入第68个节点，规则如下：先是父节点[右手]，再是祖父节点[左手]，有[变色]??。根据规则，步骤如下：右节点旋转这种情况下，父节点和插入的节点都是右节点，在旋转后的原图2中，我们要插入节点70。规则如下：使用祖父节点【左手】，搭配【变色】。根据规则，步骤如下：红黑树插入总结红黑树插入总结如下：红黑树节点删除比红黑树节点插入复杂。思维维度来讨论。至少一个子节点为空当待删除节点的至少一个子节点为空节点时，删除该节点后，将当前节点替换为有值的节点。如果都为null，则将当前节点设置为null。当然，如果违反了规则，就根据需要进行调整，比如【变色】、【旋转】。在子节点都是非空节点的情况下，第一步是寻找该节点的前驱或后继。Predecessor：左子树中值最大的节点（可以断定它至多有一个非空子节点，可能为空）。Successor：右子树中取值最小的节点（可以断定它至多有一个非空的子节点，可能为空）。前驱和后继都是值最接近节点值的节点，类似于node.prev=predecessor，node.next=successor。第二步：将前驱或后继的值复制到该节点，然后删除前驱或后继。如果删除左节点，则将前驱的值复制到该节点，然后删除前驱；如果删除了右节点，则将后继节点的值复制到该节点，并删除后继节点。这相当于一个“trick”的方法。删除节点的目的是为了让该节点的值不存在于红黑树中。所以围绕这个目的，我们删除的时候并不关心我们要删除的节点是否真的是我们要删除的节点，也不需要考虑树结构的变化，因为树结构本身由于自动平衡机制，经常会被调整。之前我们已经说过，我们要删除的其实是前任或者后继，所以我们就以前任为主线进行说明。后续学习可以参考前驱，包括以下几种情况：①前驱为黑节点，且有非空子节点分析：因为要删除左节点64，所以找到该节点的前驱63；然后用前身的值63替换要删除的节点的值64。此时两个节点（待删除节点和前驱节点）的值都是63；删除前身63，在上述过程中成为中间环节，但是我们发现它不符合红黑树规则4，所以需要进行自动平衡调整。这可以直接通过[更改颜色]来完成。②前驱为黑节点，子节点均为null。分析：因为要删除左边的节点64，所以找到这个节点的前驱63；然后将要删除的节点的值64替换为前任节点的值63。此时两个节点（待删除节点和前驱节点的值）为63。删除前驱63，它成为上述过程中的中间环节，但是我们发现它不符合红黑树规则5，所以需要进行自动平衡调整。这可以直接通过[更改颜色]来完成。③前驱为红色节点，子节点均为null分析：因为要删除左节点64，所以找到该节点的前驱63；然后用前驱的值63替换待删除节点的值64，此时两个节点（待删除节点和前驱的值）都是63；删除前身63、树的结构不违反规则。红黑树删除小结红黑树删除的情况很多，但也有以下几种情况：如果删除了根节点，则直接将根节点设置为null。待删除节点的左右子节点均为null，删除时将该节点设置为null。如果要删除的节点的左右子节点都有值，则用有值的节点替换该节点。如果待删除节点的左右子节点不为null，则找到前驱或后继，将前驱或后继的值复制到该节点，然后删除前驱或后继。删除节点后，红黑树可能会不平衡。这时候我们就需要通过【颜色变化】+【旋转】来调整一下，使其平衡。上面也给出了例子。建议大家多练习，不要死记硬背。.小结本文主要介绍红黑树的相关原理。一、红黑树的基本二叉搜索树。下面简单说一下二叉搜索树和搜索过程。然后根据红黑树六大规则的特点，用大量的图形说明了红黑树的插入操作和删除操作。技巧都是练出来的，有时候似是而非的地方很多，开始写的时候，其实很容易看懂。红黑树被广泛使用。比如TreeMap和TreeSet就是基于红黑树实现的。在JDK8中，HashMap在链表长度大于8时也会转为红黑树。红黑树比较复杂，我还在学习中。如有不妥之处，欢迎批评指正。我希望我们能共同进步。谢谢。作者：梁红简介：有初心的网名工匠，热爱技术，喜欢学习和分享，6年Java开发经验，关注Java和Spring生态，也喜欢研究物联网等前沿技术物联网、大数据、AI等。不到15人的小团队，做过项目管理，现在是软件公司的部门经理。【原创稿件，合作网站转载请注明原作者和出处为.com】
