红黑树数据结构与算法图解

2018-10-2209:04:16数据结构与算法Comments3,377 views字数 1949阅读模式

红黑树

红黑(Red-black)树是一种自平衡二叉查找树，1972年由Rudolf Bayer发明，它与AVL树类似，都在插入和删除操作时能通过旋转操作保持二叉查找树的平衡，以便能获得高效的查找性能。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

它可以在 ${\text{O}}(\log n)$ 时间内做查找，插入和删除等操作。红黑树是2-3-4树的一种等同，但有些红黑树设定只能左边是红树，这种情况就是2-3树的一种等同了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

红黑树性质

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

红黑树的性质也就是说树有自己特殊的规定，有了这些约束就能保证从根节点到叶子节点的最长路径不多于最短路径的两倍（因为每个叶子到根都不能有两个连续的红色节点，且任一节点到每个叶子包含相同数目的黑色节点）。于是就能保证该树大致上平衡，保证了查询的效率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

旋转和变色

红黑树因为是二叉查找树，所以在树上做查询和普通的二叉查找树相同。但对于插入和删除操作可能会导致树不符合红黑树性质，因此需要做少量( ${\text{O}}(\log n)$ )的变色和不超过三次的旋转操作(对于插入最多两次)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

插入操作

插入“A”，此时为根节点，标为黑色，另外存在两个NIL叶子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

插入“L”，“L”与“A”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“L”大于“A”，于是成为“A”节点的右子节点，“L”下有两个NIL叶子节点，此时没有破坏红黑树性质，不用进行额外操作，完成“L”的插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

插入“O”，“O”与“A”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“O”大于“A”，往右，继续与“L”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“O”大于“L”，于是成为“L”节点的右子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

此时发现“O”节点和其父节点“L”都是红色的，已经破坏了红黑树的性质了，另外“O”节点为右子节点，“L”也是一个右子节点，所以应该进行左单旋操作，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

左单旋操作主要是将“L”节点提升，原来的父节点“A”变为它的左子节点，“L”节点原来的左子节点变成“A”节点的右子节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

此时还需要将原来“O”节点的父节点“L”与祖父节点“A”之间的颜色进行对调，才能符合红黑树的性质，完成“O”的插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

插入“M”，“M”与“L”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“M”大于“L”，往右，继续与“O”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“M”小于“O”，于是成为“O”节点的左子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

此时发现“M”节点和其父节点“O”都是红色的，已经破坏了红黑树的性质了，另外因为“D”节点为右子节点，“M”为左子节点，且其父节点“O”与其叔父节点“A”都为红色，所以先将父节点和叔父节点的颜色变为黑色，然后祖父节点颜色变为红色，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

但是现在还有一个性质没满足，即根不能为红色，所以将根节点“L”再设为黑色，完成“M”的插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

插入“H”，“H”与“L”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“H”小于“L”，往左，继续与“A”比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

“H”大于“A”，于是成为“A”节点的右子节点，没有破坏红黑树性质，完成“H”插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

继续插入“E”，最终将成为“H”节点的左子节点，此时“E”节点和“H”节点都为红色，破坏了红黑树性质。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

因为“E”为左子节点，其父节点为右子节点，所以执行右单旋操作。右单旋主要是将“E”节点提升，原来的父节点“H”变为它的右子节点，“E”节点原来的右子节点变成“H”节点的左子节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

右单旋后发现“E”和“H”都为红色，此时“H”为右子节点，“E”也为右子节点，继续进行左单旋操作。将“E”提升，“A”作为“E”的左子节点，“E”原来左子节点变为“A”的右子节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

此外还需要将原来“H”节点的父节点“E”与祖父节点“A”之间的颜色进行对调，完成“E”的插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

继续插入“D”，最终将成为“A”节点的右子节点，此时“D”节点和“A”节点都为红色，破坏了红黑树性质。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

此时父节点“A”和叔父节点“H”都为红色，所以先将父节点和叔父节点的颜色变为黑色，然后祖父节点颜色变为红色，完成“D”的插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

继续插入“G”，结果如下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html

我们继续插入“F”，最终它成为“G”的左子节点，此时发现“F”节点和其父节点“G”都是红色的，已经破坏了红黑树的性质了，另外因为“F”节点为左子节点，“G”也为左子节点，且其叔父节点为空节点，所以进行右单旋操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/6930.html