博客

一、红黑树的概念:

• 在计算机科学中，红黑树是一种自平衡二叉搜索树。每个节点存储一个表示“颜色”（“红”或“黑”）的额外位，用于确保树在插入和删除期间保持平衡。
• 当树被修改时，新树被重新排列和“重新绘制”以恢复着色属性(整个树的红黑结点会重新进行绘制，以适应红黑树的颜色排列规则)，这些属性限制了树在最坏情况下的不平衡程度。属性的设计使得这种重新排列和重新排序可以有效地执行。
• 重新平衡不是完美的(不能像平衡二叉树一样绝对平衡，只能做到相对平衡)，但保证了搜索的时间，其中是树的节点数。插入和删除操作以及树的重新排列和重新排序也会及时执行。

二、红黑树的特征：

1. 每个结点要么是黑色，要么是红色
2. 根结点是黑色的
3. 所有叶子结点都是黑色的空节点（NIL结点）
4. 如果一个结点是红色的，那么它的子结点都是黑色
5. 从给定节点到其NIL 的每条路径都经过相同数量的黑色结点
6. 不可能有连在一起的红色结点

红黑树的叶子结点（NIL结点）是不包含键或数据，通常黑色的指向NULL指针。有时候为了节省执行时间，也有可能指向一个唯一的哨兵结点指针。

• 作用: 始终平衡树，例如每个父级有两个孩子。如果它没有得到适当的平衡，在最坏的情况下，它会退化成一个链表，没有获得红黑树的好处。
• 平衡黑色高度，当你删除一个节点时，黑色高度会立即传递给孩子。

哨兵节点：是一个专门指定的节点，与链表和树一起用作遍历路径终止符。这种类型的节点不保存或引用由数据结构管理的任何数据。

三、红黑树变换规则:

①. 旋转规则:

• 左旋：两个红色结点相连，当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树，左旋。
• 右旋：两个红色结点相连，当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树，右旋

右旋后的操作：

1. 把父结点变为黑色
2. 把祖父结点变成红色（爷爷）
3. 以祖父结点旋转（爷爷）

②. 颜色变换规则：

变颜色的情况，两个相连的红色结点：

• 当结点的父亲是红色，且它的祖父结点的另外一个子结点也是红色。（叔叔结点）:

1. 把父节点设成黑色
2. 把叔叔结点也设成黑色
3. 把祖父也就是父亲的父亲也设成红色（爷爷）
4. 把指针定义到祖父结点设为当前操作的

插入结点: