前言

上一节介绍了一棵高度为h的二叉搜索树（BST），它可以支持任何一种基本动态集合操作，如SEARCH、PREDECESSOR、SUCCESSOR、MINIMUM、MAXIMUM、INSERT、DELETE等，其时间复杂度均为O(h)。如果树的高度较高时，这些集合操作可能并不比在链表上执行得快。红黑树（red-black tree）是许多“平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度为 O(lg n)。

红黑树的性质

红黑树是一棵BST，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

树中的每个结点包含5个属性：color、key、left、right 和 parent。如果一个结点没有子结点或父结点，则该结点相应指针属性的值为NULL。我们可以把这些NULL视为指向BST的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部节点。

一棵红黑树是满足下面红黑性质的二叉搜索树：

1. 每个结点或是红色的，或是黑色的。
2. 根结点是黑色的。
3. 每个叶结点（NULL）是黑色的。
4. 如果一个结点是红色的，则它的两个子结点都是黑色的。
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含数目相同的黑色结点。

引进哨兵T.null，它是一个与树中普通结点有相同属性 的对象。它的color属性为BLACK，而其他的属性parent、left、right和key可以设为任意值。所有指向NULL的指针都可以用指向哨兵T.null的指针替换。
使用哨兵后，就可以将结点x的NULL孩子视为一个普通结点，其父结点为x。使用一个哨兵T.null来代表所有的NULL：①所有的叶结点；②根结点的父结点。

通常将注意力放在红黑树的内部结点上，因为它们储存了关键字的值。而忽略外部结点。

从某个结点x出发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black-height)，记为bh(x)。定义红黑树的黑高为其根结点的黑高。

引理：一棵有n个内部结点的红黑树的高度至多为2*lg(n+1)。

以任一结点x为根的子树中至少包括2^bh(x) -1个内部结点。

旋转

搜索树的操作TREE_INSERT和TREE_DELETE在含n个关键字的红黑树上，运行花费时间为O(lg n)。由于这两个操作对树做了修改，结果可能违反红黑性质。为了维护红黑性质，必须要改变树中的某些结点的颜色以及指针结构。

指针结构的修改通过旋转(ratation)来完成的，这是一种能保持BST性质的搜索树局部操作。

左旋LEFT_ROTATE和右旋RIGHT_ROTATE。当在某个结点x上做左旋时，假设它的右孩子为y而不是T.null；x可以为 其右孩子不是T.null结点 的树内任意结点。左旋使y成为该子树新的根结点，x成为y的左孩子，y的左孩子成为x的右孩子。右旋里，y是x的左孩子（不为空），y成为该子树新的根结点，x成为y的右孩子，y的右孩子成为x的左孩子。

输入的树和修改过的树进行中序遍历，产生相同的关键字值列表。

LEFT_ROTATE和RIGHT_ROTATE都在O(1)时间内运行完成。在旋转操作中，只有指针改变，其他所有属性都保持不变。

//伪代码
LEFT_ROTATE(T,x)
  y=x.right//set y
  x.right=y.left//turn y's left subtree into x's right tree
  if y.left!=T.null
    y.left.parent=x
  y.parent=x.parent//link x's parent to y
  if x.parent==T.null
    T.root=y
  else if x==x.parent.left//x is left child
    x.parent.left=y
  else//x is right child
    x.parent.right=y
  y.left=x
  x.parent=y

RIGHT_ROTATE操作的代码是对称的。

//伪代码
RIGHT_ROTATE(T,x)
  y=x.left//set y
  x.left=y.right//turn y's right subtree into x's left tree
  if y.right!=T.null
    y.right.parent=x
  y.parent=x.parent//link x's parent to y
  if x.parent==T.null
    T.root=y
  else if x==x.parent.right
    x.parent.right=y
  else
    x.parent.left=y
  y.right=x
  x.parent=y

插入

可以在O(lg n)时间内完成向一棵含有n个结点的红黑树中插入一个新结点。辅助程序INSERT_FIXUP对结点重新着色并旋转。调用RB_INSERT(T,z)在红黑树T内插入结点z，假设z的key属性已被事先赋值。

//伪代码
RB_INSERT_FIXUP(T,z)//this function is a while loop
  while z.parent.color==RED
    if z.parent==z.parent.parent.left
      y=z.parent.parent.right
      if y.color==RED
        z.parent.color=BLACK//case 1
        y.color=BLACK//case 1
        z.parent.parent.color=RED//case 1
        z=z.parent.parent//指针z沿树上升
      else if z==z.parent.right
        z=z.parent//case 2
        LEFT_ROTATE(T,z)//case 2
      z.parent.color=BLACK//case 3
      z.parent.parent.color=RED//case 3
      RIGHT_ROTATE(T,z.parent.parent)
    else
      (same as then clause with "right" and "left" exchanged)
    T.root.color=BLACK

RB_INSERT(T,z)//插入结点z
  y=T.null
  x=T.root
  while x!=T.null
    y=x
    if z.key<x.key
      x=x.left
    else
      x=x.right
  z.parent=y
  if y==T.null//tree T is empty
    T.root=z
  else if z.key<y.key
    y.left=z
  else
    y.right=z
  z.left=T.null
  z.right=T.null
  z.color=RED
  RB_INSERT_FIXUP(T,z)//此时已按key的大小将z插入到合适的位置，接下来调用函数维持红黑性质。

情况1：z的叔结点y是红色的。
情况2：z的叔结点y是黑色的且z是一个右孩子。
情况3：z的叔结点y是黑色的且z是一个左孩子。

RB-INSERT总共花费O(lg n)时间——对于一棵有n个结点、高度为O(lg n)的红黑树而言。

删除

与插入操作相比，删除操作要稍微复杂些。

//伪代码
RB_TRANSPLANT(T，u，v)
  if u.parent==T.null//tree T is empty
    T.root=v
  else if u==u.parent.left
    u.parent.left=v
  else
    u.parent.right=v
  v.parent=u.parent//对v.parent的赋值是无条件执行：即使v为空，也要对v.parent赋值。

//伪代码
RB_DELETE_FIXUP(T,x)//通过改变颜色和执行旋转来恢复红黑性质
  while x!=T.root and x.color==BLACK
    if x==x.parent.left
      w=x.parent.right
      if w.color==RED
        w.color=BLACK//case 1
        x.parent.color=RED//case 1
        LEFT_ROTATE(T,x.parent)//case 1
        w=x.parent.right//case 1
      if w.left.color==BLACK && w.right.color==BLACK
        w.color=RED//case 2
        x=x.parent//case 2
      else if w.right.color==BLACK
        w.left.color=BLACK//case 3
        w.color=RED//case 3
        RIGHT_ROTATE(T,w)//case 3
        w=x.parent.right//case 3
      w.color=x.parent.color//case 4
      x.parent.color=BLACK//case 4
      w.right.color=BLACK//case 4
      LEFT_ROTATE(T,x.parent)//case 4
      x=T.root//case 4
    else
      (same as then clause with "right" and "left" exchanged)
  x.color=BLACK

//伪代码
RB_DELETE(T,z)
  y=z
  y_original_color=y.color//存储y发生改变前的颜色
  if z.left==T.null
    x=z.right
    RB_TRANSPLANT(T,z,z.right)
  else if z.right==T.null
    x=z.left
    RB_TRANSPLANT(T,z,z.left)
  else
    y=TREE_MINIMUM(z.right)//y是z的后继
    y_original_color=y.color
    x=y.right
    if y.parent==z
      x.parent=y
    else
      RB_TRANSPLANT(T,y,y.right)
      y.right=z.right
      y.right.parent=y
    RB_TRANSPLANT(T,z,y)
    y.left=z.left
    y.left.parent=y
    y.color=z.color
  if y_original_color==BLACK
    RB_DELETE_FIXUP(T,x)

RB_DELETE运行的总时间为O(lg n)