红黑树-数据结构(c语言)

红黑树（Red-Black Tree）

红黑树（Red-Black Tree） 也是一种自平衡的二叉查找树，它是 1972 年由 Rudolf Bayer 发明的，而“红黑树”的名字是由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。和其他平衡二叉查找树类似，红黑树也可以在 $mathcalO(logn)$ 的时间复杂度内完成查找、插入和删除操作。红黑树相比于 AVL，牺牲了部分平衡性以在插入、删除操作时减少旋转操作，整体性能优于 AVL，也正因如此，C STL 中的 map 就是用红黑树实现的。
红黑树和其他平衡二叉查找树相比，增加了一个 颜色 属性，用来标识树上的结点是红色还是黑色；并且如果一个结点没有子结点，则该结点的子节点对应的指针为 NIL，也就是说，红黑树的所有叶子都是 NIL。基于此，我们给红黑树下一个定义——红黑树是满足如下条件的二叉查找树：

• 每个结点要么是红色，要么是黑色； 根结点是黑色； 叶结点（NIL）是黑色； 如果一个结点是红色，则它的两个子节点都是黑色的； 从根结点出发到所有叶结点的路径上，均包含相同数目的黑色结点。
  
  上图展示了一棵合法的红黑树。其中 NIL 和我们前面课程里用到的 NIL 功能类似，只是为了便于处理边界情况，因此在接下来的分析中，我们不会把 NIL 结点画在树上。把 NIL 去掉以后并不影响你对红黑树的理解，因为即使没有 NIL 结点，上述的第五条规则仍然成立。而第五条规则是红黑树平衡性的核心。 因为第四条和第五条规则的限制，使得红黑树上从根结点到每个叶结点的最长路径最多是最短路径的两倍，这也确保了整棵二叉查找树是平衡的。

插入操作

红黑树的插入操作和二叉查找树类似，在正常插入以后，要将插入的结点标为红色，并对树进行类似 AVL 和 SBTree 的旋转调整，使得树满足红黑树的第四条规则，即每个红色结点的子节点都是黑色的。为什么要标记为红色呢？因为如果将结点标记为黑色，会使得第五条规则被破坏，很难通过旋转来调整，而通过旋转可以比较容易地使得红色结点分隔开。
首先，我们给出三个定义：

• 祖父结点：父结点的父结点 兄弟结点：当前结点为父结点的左孩子时，为父结点的右孩子；当前结点为父结点的右孩子时，为父结点的左孩子 叔父结点：父结点的兄弟结点 当插入之前的树为空时，新结点会位于树的根，根据第二条规则，将新结点的颜色改为黑色就可以了。除此之外，当插入的新结点 x 的父结点是红色时，需要从新结点出发向上进行调整，直到 x 的父结点为黑色，一共有三种情况： 1） x 的叔父结点是红色的： 此时 x 的祖父结点一定是黑色的，因此将祖父结点的黑色改为红色，并将 x 的父结点和叔父结点改为黑色。之后将 x 的祖父结点作为 x 继续向上迭代。
• 
  2） x 的叔父结点是黑色的，并且 x 是一个右孩子：
  对 x 的祖父结点进行左旋（左旋操作和前面介绍的几种平衡二叉查找树一致）后，x 及其父结点仍为红色，叔父结点仍为黑色，需要继续对 x 执行第三种调整。
  
  
  3） x 的叔父结点是黑色的，并且 x 是一个左孩子：
  此时，将 x 的父结点改为黑色，祖父结点改为红色，并对 x 的祖父结点进行右旋。这时，x 的父结点为黑色，不需要再向上迭代调整了。·
  
  

删除操作

和之前所学的二叉搜索树的删除操作类似，首先找到要删除的结点，如果这个结点有两个子结点，那么可以把问题转化为删除只有一个子结点的操作。为了统一，在接下来我们只分析删除只有一个孩子的结点的情况（如果两个子结点都是 NIL，那么将其中一个 NIL 当做子结点就可以了）。
首先，我们先处理一些特殊情况。如果要删除的结点 x 为红色，那么这个结点的父结点和子结点都一定是黑色，因此，只需要把子结点直接连向父结点就可以了，不会破坏红黑树的五条规则。而如果被删除结点是黑色而其子结点是红色，也只需要把子结点替换上来，并将它的颜色改为黑色就可以了。

接下来所有情况的前提，都是待删除结点及其子结点都为黑色的情况。首先将待删除结点的子节点替换到待删除结点上，标记为 x，并将 x 的兄弟结点标记为 w。注意，此时 x 具有 双重黑色 ，也就是说，在计算路径上的黑色结点时，经过 x 要计两次数。所以在接下来的例子里，不要为图片不符合红黑树定义而困惑，原因就在于“双重黑色”的 x 结点。
1）x 的兄弟结点是红色的：
此时对 x 的父结点进行一次旋转，并改变 x 的父结点和兄弟结点的颜色。这时， x 的新兄弟结点是黑色的了，可以按照后面几种情况继续处理。


2） x 的兄弟结点是黑色的，并且 w 的两个子结点是黑色的：
这时，去掉 x 的一重黑色，并将 w 改为红色，在 x 的父结点加上额外的一重黑色（如果原来是红色，则改为黑色，否则改为双重黑色）。接下来将 x 的父结点当做 x，继续后续的调整操作。


3）x 的兄弟结点 w 是黑色的，w 的左孩子是红色的，w 的右孩子是黑色的。
此时，交换 w 和它的左孩子的颜色，然后对 w 进行右旋操作。现在 w 的右孩子为红色，可以按照情况 4 进行处理。


4）x 的兄弟结点 w 是黑色，且 w 的右孩子是红色的：
此时，调整 w 及其父结点和右孩子的颜色，并对 w 的父结点进行一次左旋，可以使 x 去掉一重黑色。这时以根结点作为 x，继续进行判断。

这篇好文章是转载于：学新通技术网