红黑树数据结构和算法图

红黑树

红黑（Red-Black）树是Rudolf Bayer于1972年发明的一种自平衡二叉搜索树。它类似于AVL二叉搜索树在插入和删除操作时，可以通过旋转操作来平衡二叉搜索树，从而实现高效搜索。

可以在 ${\text{O}}(\log n)$ 时间内执行搜索、插入和删除操作。红黑树相当于2-3-4树，但有些红黑树设置只能在左边有一棵红树。在这种情况下，它相当于一棵 2-3 树。

对于AVL树，红黑树牺牲了部分平衡性来换取插入/删除操作时少量的轮换，整体性能优于AVL树。

红黑树的特征

• 节点是红色或黑色。
• 根节点是黑色的。
• 每个叶子节点（NIL 节点）都是黑色的。
• 每个红色节点的两个子节点都是黑色的。 （从每个叶子到根的所有路径上不能有两个连续的红色节点）
• 从任何节点到其每个叶子的所有路径都包含相同数量的黑色节点。

红黑树的性质意味着该树有其特殊的规定。这些约束可以用来保证从根节点到叶子节点的最长路径不超过最短路径的两倍（因为每个叶子到根不能是两个连续的红色节点，并且每个叶子到每个叶子的每个节点都包含相同的红色节点）黑色节点的数量）。这样可以保证树大致平衡，保证查询效率。

旋转和颜色变化

因为红黑树是二叉搜索树，所以查询该树与常规二叉搜索树相同。但插入和删除操作会导致树与红黑树的属性不匹配，因此需要少量的 (${\text{O}}(\log n)$)旋转操作最多执行两次（插入操作最多两次）。

插入操作

插入“A”，此时为根节点，以黑色高亮显示。还有另外两个 NIL 叶节点。

插入“L”并将“L”与“A”进行比较，

“L”大于“A”，因此它成为节点“A”的真子节点。 “L”下方是两个 NIL 叶节点。此时红黑树的属性并没有被破坏，不需要进一步的操作就可以完成“L”的插入。

插入“O”，将“O”与“A”比较，

“O”大于“A”，向右移动，继续与“L”比较，

“O”大于“A” “L”因此成为“L”节点的右子节点。

此时，发现节点“O”及其父节点“L”都是红色的，这就破坏了红黑树的本质。另外，节点“O”是右子节点，“L”也是右子节点，因此需要进行一次向左旋转操作。

简单的左旋转操作主要支持节点“L”，原父节点“A”成为其左子节点。节点“L”原来的左子节点成为“A”的右子节点。

此时还需要将原“O”节点的父节点“L”和父节点“A”之间的颜色进行交换，以满足红黑树的属性，完成“ O”插入。

插入“M”，比较“M”与“L”，

“M”大于“L”，向右移动，继续与“O”比较，

“M”小于“O”因此成为“O”节点的左子节点。

此时，节点“M”及其父节点“O”都被发现是红色的，这就破坏了红黑树的本质。另外，由于节点“D”在右子节点，“M”是左子节点，其父节点“O”及其叔节点“A”都是红色，所以先改变父节点的颜色将叔父节点和叔父节点的颜色更改为黑色，然后将祖父母节点的颜色更改为红色。

但是还有一个属性不满足，就是根不能是红色，所以再次将根节点“L”设置为黑色，完成“M”的插入。

插入“H”，将“H”与“L”比较，

“H”小于“L”，向左移动，继续与“A”比较，

“H”大于“A”，因此成为“A”的右子节点，不破坏红黑树的属性，完成“H”的插入。

继续插入“E”，最终成为“H”节点的左子节点。此时节点“E”和节点“H”都是红色的，这就破坏了红黑树的属性。

因为“E”是左子节点，其父节点是右子节点，所以执行了一次右旋转操作。右旋转主要支持节点“E”，原父节点“H”成为其右子节点，“E”节点原右子节点成为“H”节点的左子节点。

向右转一圈后，发现“E”和“H”都是红色的。此时“H”是正确的子节点，“E”也是正确的子节点。继续向左旋转一圈的操作。提升“E”，“A”成为“E”的左孩子，“E”原来的左孩子成为“A”的右孩子。

另外，还需要将原节点“H”的父节点“E”和父节点“A”交换颜色，才能完成“E”的插入。

继续插入“D”，最终成为“A”节点的右子节点。此时节点“D”和节点“A”都是红色的，这就破坏了红黑树的属性。

此时父节点“A”和叔节点“H”都是红色，所以先将父节点和叔节点的颜色改为黑色，然后将祖父母节点的颜色改为红色完成“D”的插入。

继续插入“G”，结果如下。

我们不断插入“F”，最终它成为“G”的左子节点。此时，我们发现节点“F”及其父节点“G”都是红色的，这就破坏了红黑树的本质。而且，由于节点“F”是左子节点，“G”也是左子节点，并且其叔节点是空节点，因此执行一次右旋转操作。

单次右旋转操作主要支持“G”，“H”成为“G”的右子节点，“G”原来的右子节点成为“H”的左子节点。

此时还需要将原“F”节点的父节点“G”和父节点“H”之间的颜色进行交换，以便观察红黑树的性质。并完成插入“F”。找右边，

“F”比“G”小，向左找。

作者：超人王小健
来源：掘金