文章目录
前言
最近在学习HashMap相关内容时碰到了红黑树。在hashMap中，链表超过一定长度将会转化为红黑树，趁这个机会学习并记录一下红黑树的内容。
提示：以下是本篇文章正文内容
一、什么是红黑树
红黑树是一种自平衡二叉排序树，它属于平衡树，但是却没有平衡二叉树那么“平衡”。那么我们首先来看一下平衡二叉树。
1.1 平衡二叉树
二叉平衡树有以下规则：
- 规则1：每个节点最多只有两个子节点（二叉）
- 规则2：每个节点的值比它的左子树所有的节点大，比它的右子树所有节点小（有序）
- 规则3：每个节点左子树的高度与右子树高度之差的绝对值不超过1
平衡二叉树的构建
这里右右和右左是对应这左左和左右的，我们只讲左左和左右两种情况，另外两种依次类推：
左左
如图，如果1号是新插入的节点，在未插入之前，二叉树是平衡的，插入之后3号节点左右不平衡了，这种不平衡是3号的左孩子节点，新增了一个左孩子,我们的方法是右旋。
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：旋转
（2） 左右
右旋再左旋：如图是红黑树的一部分，8号节点的父节点为红色，叔节点为黑色。8号节点为右节点，8号节点的父节点为左节点，所以符合左右的情况。
我们进行左旋再右旋并变色：
右右和右左依次类推。
看了以上讲解还不明白？那么我们具体来构建一个红黑树就明白了。
三、红黑树插入之详解
总结
红黑树大体来说是5+2，5是 5个规则 ，这5个规则可以通过 2个操作 来满足，一个操作是变色，另一个操作是旋转。旋转的操作和平衡二叉树的四个操作一样，只是旋转之后需要加入一个变色的操作。
以上就是红黑树的相关内容。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/177268.html原文链接：https://javaforall.net
