【数据结构】红黑树与平衡二叉树的区别以及原理详解（附图解） 文章目录 前言一、什么是红黑树1.1 平衡二叉树1.2红黑树1.3 平衡二叉树和红黑树的区别 二、红黑树的构建过程2.1 红黑树保持平衡操作1：变色2.2 红黑树保持平衡操作2：旋转 三、红黑树插入之详解总结 前言 最近在学习HashMap相关内容时碰到了红黑树。在hashMap中，链表超过一定长度将会转化为红黑树，趁这个机会学习并记录一下红黑树的内容。 提示：以下是本篇文章正文内容 一、什么是红黑树 红黑树是一种自平衡二叉排序树，它属于平衡树，但是却没有平衡二叉树那么“平衡”。那么我们首先来看一下平衡二叉树。 1.1 平衡二叉树 二叉平衡树有以下规则： 规则1：每个节点最多只有两个子节点（二叉）规则2：每个节点的值比它的左子树所有的节点大，比它的右子树所有节点小（有序）规则3：每个节点左子树的高度与右子树高度之差的绝对值不超过1 那么我们来看看下面树的图： 符合三个规则的平衡二叉树： 
5号节点有三个孩子，违反规则1，不是平衡二叉树 
7号节点属于5号节点的左子树范围却比5大，违反规则2，不是平衡二叉树。 
5号节点的左子树高度为3，右子树高度为1，两边高度之差绝对值为2，违反了规则3，不是平衡二叉树。 
总结：平衡二叉树其实就是高度相对平衡的有两个子节点的有序树。 平衡二叉树的构建 那么平衡二叉树是如何构建呢，如果简单的按照排序的规则插入，那么很可能会使得二叉树不平衡，所以为了维持树的平衡，我们在插入和删除平衡二叉树的结点时会进行一定的操作来保持平衡，其中包括以下几种情况，以及解决方法： 左左：右旋解决 左右：先左旋再右旋 右右：左旋解决 右左：先右旋再左旋 这里右右和右左是对应这左左和左右的，我们只讲左左和左右两种情况，另外两种依次类推： 左左 如图，如果1号是新插入的节点，在未插入之前，二叉树是平衡的，插入之后3号节点左右不平衡了，这种不平衡是3号的左孩子节点，新增了一个左孩子,我们的方法是右旋。 
右旋之后，节点有平衡了，结果如下， 
左右： 如图，如果3号是新插入的节点，在未插入之前，二叉树是平衡的，插入之后4号节点左右不平衡了，这种不平衡是34号的左孩子节点，新增了一个右孩子,我们的方法是先左旋再右旋。 
结果如下： 
1.2红黑树 红黑树的规则： 规则1: 每个节点不是黑色就是红色规则2： 根节点为黑色规则3：红色节点的父节点和子节点不能为红色规则4：所有的叶子节点都是黑色（空节点视为叶子节点NIL）规则5：每个节点到叶子节点的每个路径黑色节点的个数都相等。 那么符合以上规则的就是红黑树。虽然规则读起来晦涩难懂，但是一起来看一看红黑树的构建就简单许多了。 1.3 平衡二叉树和红黑树的区别 平衡二叉树的左右子树的高度差绝对值不超过1，但是红黑树在某些时刻可能会超过1，只要符合红黑树的五个条件即可。二叉树只要不平衡就会进行旋转，而红黑树不符合规则时，有些情况只用改变颜色不用旋转，就能达到平衡。 二、红黑树的构建过程 红黑树构建时要满足以上的5个规则，那么简单的插入是不够的，因为简单的插入会造成子树两边不平衡，那么在插入时我们要进行以下两个操作，来维持红黑的规则正确： 操作1：变色操作2：旋转 2.1 红黑树保持平衡操作1：变色 为了保持路径上黑色节点个数一致，在插入时，新插入的节点我们总是认为是红色。如果插入之后某个部分符合以下规则，那么我们将采取变色的方法。如图所示，2号为红色，其父节点3和叔节点8位红色，（注意，此处是红黑树的一部分，5号节点不为根节点）， 
那么这时违反了规则三。我们可以通过变色来解决。 第一步：将父节点3和叔节点8变黑 第二步，将奶奶节点5变红。 
注意：如果5号是根节点，5号节点就不变色 2.2 红黑树保持平衡操作2：旋转 如果变色的方法不可用，那么我们需要使用旋转的方法。红黑树的旋转和平衡二叉树的旋转一样，只不过多了变色的步骤。 如果红色节点的父节点为红色，叔节点为黑色，那么我们就需要使用旋转的方法。 （1） 左左 左旋：如图是红黑树的一部分，2号节点的父节点为红色，叔节点为黑色。2号节点为左节点，2号节点的父节点为左节点，所以符合左左的情况，我们进行右旋 
右旋之后我们将原来的父节点变黑，将原来的奶奶节点变红 
因为这里是红黑树的部分图，所以看起来不平衡。其实一开始左节点的黑色节点个数为0，右节点的黑色节点个数为1。但是一开始的图所在的红黑树中是平横的，所以在旋转之后我们还是要保证左边为0，右边为1，我们的红黑树才是平衡的。 （2） 左右 右旋再左旋：如图是红黑树的一部分，8号节点的父节点为红色，叔节点为黑色。8号节点为右节点，8号节点的父节点为左节点，所以符合左右的情况。 
我们进行左旋再右旋并变色： 
右右和右左依次类推。 看了以上讲解还不明白？那么我们具体来构建一个红黑树就明白了。 三、红黑树插入之详解 前面讲的左左和左右，那么我们依次将[1, 2, 3, 4, 5, 6, 7 , 8] 插入红黑树，使用右右和右左的情况。 插入1，根节点标记为黑色。 插入2，节点为红色什么也不做。 插入3，这时3的父节点是红色，叔节点为空，视为黑色，所以采用旋转的方法平衡。该平衡的情况为右右的情况，进行左旋。 
插入4：变色，2节点为根节点不变色 
插入5： 
插入6：变色 
插入7： 
插入8：因8号的叔节点为红色，执行操作1变色，因奶奶节点6不是根节点，所以要变红。 
变色操作之后我们发现6号节点的父节点4号为红色，且6号节点的叔节点1号为黑色，以6号节点为当前节点执行左旋： 其中左旋之后4号节点的左孩子变为2号节点的右孩子 
总结 红黑树大体来说是5+2，5是 5个规则 ，这5个规则可以通过 2个操作 来满足，一个操作是变色，另一个操作是旋转。旋转的操作和平衡二叉树的四个操作一样，只是旋转之后需要加入一个变色的操作。 以上就是红黑树的相关内容。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/35887.html
