红黑树（Red-Black Trees）

• 1. 红黑树的概念和性质
• 2. 红黑树的操作

   

1. 红黑树的概念和性质

• 概念

  红黑树是一种高效率的自平衡二叉搜索树。 其查找，插入和删除操作的时间复杂度均为 $O(logn)$。与AVL树相比较，红黑树牺牲了部分平衡性换取了插入和删除操作时更少量的旋转操作。红黑树的整体性能优于AVL树。

• 红黑树的性质

  1. 所有节点被分为红色节点或者黑色节点。
  2. 根节点（root）是黑色的。
  3. 所有叶节点（NIL）都是黑色的（NIL节点指一个节点指向的空节点）。
  4. 一个红色节点的子节点必须都是黑色的。
  5. 从任意节点开始到其每个叶节点（叶节点是NIL节点）的路径都包含相同数量的黑色节点（注意不计算起始节点，也称为黑色高度（Black Height））。

下图是一个红黑树的例子。可以看到所有节点都是红色或者黑色的，且根节点为黑色。所有叶节点（即NIL）也为黑色。所有红色节点的子节点都是黑色的。

红黑树的节点代码实现如下

enum Colors {BLACK, RED}

class Node {
  Node parent;
  Node left;
  Node right;
  Colors color;
  int element;
}

相应的，我们需要以下操作来获取插入节点n的兄弟节点（sibling），父节点（parent），叔父节点（uncle）和祖父节点（grandparent）。

Node getParent(Node n) {
    return n.parent;
}

Node getGrandparent(Node n) {
    Node p = getParent(n);
    if (p == null) {
        return null;
    }
    return getParent(p);
}

Node getSibling(Node n) {
    Node p = getParent(n);

    if (p == null) {
        return null;
    }

    if (n == p.left) {
        return p.right;
    } else {
        return p.left;
    }
}

Node getUncle(Node n) {
    Node p = getParent(n);
    Node g = getGrandparent(n);

    if (g == null) {
        return null;
    }

    return getSibling(p);
}

 

2. 红黑树的操作

• 红黑树的旋转（Rotate）

与AVL树类似，红黑树需要用旋转来改变树的结构从而达到平衡状态。红黑树的左旋和右旋与AVL树本质上相同，只是红黑树在必要时需要调整颜色。这一部分可以结合AVL树章节的旋转部分来看。

void rotateLeft(Node n) {
    Node nnew = n.right;
    Node p = getParent(n);
    assert(nnew != null); 

    n.right = nnew.left;
    nnew.left = n;
    n.parent = nnew;

    if (n.right != null) {
        n.right.parent = n;
    }

    if (p != null) {
        if (n == p.left) {
            p.left = nnew;
        } else if (n == p.right) {
            p.right = nnew;
        }
    }
    nnew.parent = p;
}

void rotateRight(Node n) {
    Node nnew = n.left;
    Node p = getParent(n);
    assert(nnew != null);

    n.left = nnew.right;
    nnew.right = n;
    n.parent = nnew;

    if (n.left != null) {
        n.left.parent = n;
    }

    if (p != null) {
        if (n == p.left) {
            p.left = nnew;
        } else if (n == p.right) {
            p.right = nnew;
        }
    }
    nnew.parent = p;
}

• 红黑树的查找操作（Search）

因为红黑树本质上仍然是二叉搜索树，所以红黑树的查找操作与普通的二叉搜索树的查找操作完全相同。

为了表述的清晰，下图给出了关于一个节点（下图中的节点N）的父节点，祖父节点，兄弟节点，和叔父节点的位置。

• 红黑树的插入操作（Insert）

红黑树的插入操作会改变树的结构，记住所有新插入节点的初始颜色为红色。在插入节点N后会出现以下四种情况。每种情况有不同的调整方案。插入操作基本上有以下三个步骤。

1. 插入新节点N，并标记为红色。
2. 进行必要的节点颜色改变来保持红黑树的五个属性。
3. 如果仅改变颜色不足以保证红黑树的属性，则进行旋转。

情况 1. N是该红黑树的根节点。即该红黑树之前是空树，N是其第一个节点（除了NIL）。

在空红黑树中插入节点N，N是此树的唯一一个节点，也是根节点。因为N是红色的根节点，此状态违反了红黑树的性质2。所以需要将颜色变为黑色。

情况 2. N的父节点P（parent）为黑色。

如果N的父节点为黑色，因为新插入节点的初始颜色均为红色，所以N不违反性质4。同样N也不违反性质5，在下图中给出了带有NIL节点的例子。

情况 3. N的父节点P为红色（所以P不是该红黑树的根节点），且N的叔父节点U（uncle）为红色。

此时将P和U节点改为黑色，将祖父节点G变为红色。如果G是根节点，则需再将G变回黑色。注意如果G不是根节点，则不需再变为黑色。

情况 4. N的父节点为红色，且N的叔父节点为黑色

下面给出了一个需要旋转两次的例子。如果第一步的N节点插入在P的左子树位置，则只需要一次右旋。左旋和右旋本质上和AVL树一样，但是红黑树需要多一步上色操作。

插入操作的代码如下所示。

Node insert(Node root, Node n) {
    insertRecurse(root, n);
    
    insertRepairTree(n);
    root = n;
    while (getParent(root) != null) {
        root = getParent(root);
    }
    return root;
}

void insertRecurse(Node root, Node n) {
    if (root != null && n.key < root.key) {
        if (root.left != null) {
            insertRecurse(root.left, n);
            return;
        } else {
            root.left = n;
        }
    } 
    else if (root != null) {
        if (root.right != null) {
            insertRecurse(root.right, n);
            return;
        } else {
            root.right = n;
        }
    }

    n.parent = root;
    n.left = null;
    n.right = null;
    n.color = RED;
}

• 红黑树的删除操作（Delete）

因为红黑树本质上是二叉搜索树，所以在删除一个节点后，仍需保持该树的二叉搜索性质。因为红黑树的删除操作非常复杂，我们不在此讨论。