红黑树

完整源代码

性质

• 树中每个节点包括了五个属性。包括color、key、left、right、p。
• 一个有n个内部节点的红黑树的高度最多是2log(n + 1)，区别于AVL树，因为红黑的所有叶子节点是哨兵（NIL），多出来了整整N个。
• 上面的解释有问题，红黑树构建时保证的是没有一条路径会比其他路径长出两倍。
• 从某一个节点到达任意一个叶子节点的任意一条简单路径上的黑色节点个数为该节点的黑高。

定义

• 每个节点或者是红色，或者是黑色。
• 根是黑色的。
• 如果一个节点是红色的，则他的子节点必须是黑色的。
• 从一个节点到一个NULL节点的路径上必须包含相同数目的黑色节点。
• 每个叶子节点（NIL）是黑色的。
• 红黑树确保没有一条路径会比其他路径长出两倍。

两种类型的旋转

• 单旋转

void leftrotate(RedBlackNode *&root, RedBlackNode *x) {
    RedBlackNode *y = x->right;
    x->right = y->left;
    if (y->left != NIL)
        y->left->parent = x;
    y->parent = x->parent;

    if (x->parent == NIL)
        root = y;
    else if (x->parent->left == x)
        x->parent->left = y;
    else if (x->parent->right == x)
        x->parent->right = y;

    y->left = x;
    x->parent = y;
}

void rightrotate(RedBlackNode *&root, RedBlackNode *x) {
    RedBlackNode *y = x->left;
    x->left = y->right;
    if (y->right != NIL)
        y->right->parent = x;
    y->parent = x->parent;

    if (x->parent == NIL)
        root = y;
    else if (x->parent->left == x)
        x->parent->left = y;
    else if (x->parent->right == x)
        x->parent->right = y;

    y->right = x;
    x->parent = y;
}

三种修复情况及对应的修复方法

• 插入节点z的叔节点y为红色：修改父节点及叔节点和祖父节点的颜色，并将z指针指向祖父节点

    if (y->Color == Red) {
        z->parent->Color = Black;
        y->Color = Black;
        z->parent->parent->Color = Red;
        z = z->parent->parent;
    }

• z的叔节点y是黑色且z是个右孩子：父节点左旋，z指针不变。

    z = z->parent;
    leftrotate(root, z);

• z的叔节点y是黑色且z是个左孩子：如第一种情况那样修改颜色，并将祖父节点右旋。

    z->parent->Color = Black;
    z->parent->parent->Color = Red;
    rightrotate(root, z->parent->parent);

其他

• 搜索树经过左旋和右旋，她的中序遍历的顺序是不变的。

插入原则

插入方法

自顶向下

• 二叉树的旋转操作，左旋和右旋。
• 单旋转、双旋转

自底向上

实现

• 数据结构

#define NegInfinity (-10000)
typedef struct RedBlackNode;
typedef enum ColorType {
    Red, Black
} ColorType;

//sentinel
RedBlackNode *NIL = NULL;

typedef struct RedBlackNode {
    int value;
    RedBlackNode *left;
    RedBlackNode *right;
    RedBlackNode *parent;
    ColorType Color;

    RedBlackNode(int value) :
            value(value), left(NIL), right(NIL), Color(Red) {

    }

};

• 初始化

RedBlackNode *init() {
    if (NIL == NULL) {
        NIL = new RedBlackNode(NegInfinity);
        NIL->left = NIL;
        NIL->right = NIL;
        NIL->Color = Black;
    }
    return NIL;
}

• 插入

void insert(RedBlackNode *&root, int value) {
    RedBlackNode *x = root;
    RedBlackNode *y = NIL;
    while (x != NIL) {
        y = x;
        if (value < x->value)
            x = x->left;
        else
            x = x->right;
    }
    RedBlackNode *z = new RedBlackNode(value);
    z->parent = y;
    if (y == NIL)
        root = z;
    else if (z->value < y->value)
        y->left = z;
    else
        y->right = z;
    fixup(root, z);
}