红黑树

一、前言

在普通平衡二叉树中我们知道平衡条件苛刻，平衡条件很容易被打破，因此需要频繁的调整全树的结构，代价太大了，应用并不广。下面介绍一种平衡条件放宽的数据结构，它的所有操作都在对数时间内完成。

二、2-3查找树

2.1 定义

一颗2-3查找树或为一颗空树，或由下列结点组成：
2-结点：只有一个键，两条链接的结点，如图1-1。
3-结点：有两个键，三条链接的结点，如图1-2。

图1-1

图1-2

如图1-3是一颗标准的2-3查找树：

图1-3

2.2 查找

假设我们可以很好的操作上面定义的结构，那么我们怎样查找一个元素？

树上的结点划分了不同的区间，树越深区间划分的越细，我们查找的是某个以被查找的元素作为端点的区间，如果找到则查找成功，如果永远的落入到一个区间中（非端点），这个区间没有被继续分割（遇到空结点），则查找失败。

例如，我们在图1-3中的树上查找C和M：

查找C元素（成功）：

查找M元素（失败）：

2.3 插入

2.3.1 在一个2-结点上插入

就像在上面查找M元素过程中，最后停到了K结点，K结点是一个2-结点，即未命中查找结束在一个2-结点上，这种情况如何处理？

很简单，直接将这个2-结点变为3-结点，插入要插入的键。如图2-1:

2.3.2 只有一个3-结点的树中插入

插入H：

这里的4-结点是非常重要的中间结点，后续的操作都离不开它。

2.3.3 向父结点为2-结点的3-结点中插入

插入Z：

2.3.4 向父结点为3-结点的3-结点中插入

插入N：

2.3.5 分解根结点

如果2.3.4步骤中向上分解到根结点都没有遇到2-结点怎么办？

其实很简单，前面的分解都是2.3.4的步骤，到达根结点后执行2.3.2的步骤就行了。

2.4 分析

上述定义的2-3树操作很直白，容易理解，但是实现起来很复杂，我们需要维护两种结点，实现它们之间的转换，情况还非常多，这不是一件容易的事，代码量会很多。而下面的红黑树是2-3查找树的一种表达，实现起来并不难。

三、红黑树

3.1 定义

王道的定义：

一棵红黑树是满足如下红黑性质的二叉排序树：

每个结点或是红色，或是黑色的。
根结点是黑色的。
叶结点（虚构的外部结点、NULL结点）都是黑色的。
不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。

另一种定义是我们将讨论的颜色对象换为链接而非结点（颜色的变量在结点中，但是我们使用的时候是这样使用的node.left.color，就好像是链接颜色一样）：

红链接均为左链接
没有结点同时和两条红链接相连
完美黑色平衡

2-3查找树定义红黑树：

红链接将两个2-结点连接起来构成3-结点，都是左斜的
黑链接是2-3树中的普通链接

如果我们将一棵红黑树的红链接画平，那么所有空链接到根链接的距离都是相同的。我们将图1-3中的2-3树转换为红黑树：

如上图将红链接画平后树是完美平衡的。

3.2 实现

3.2.1 结点定义及颜色表示

  
//定义颜色
#define RED true;
#define BLACK false;
using Color = bool;

template <class Key, class Value> 
class RBNode{
private:
    Key key;
    Value value;
    RBNode<Key,Value> left;
    RBNode<Key,Value> right;
    int N;
    Color color;

public:
    RBNode(Key &ikey, Value &ivalue, int inum, Color &c){
        Key = ikey;
        Value = ivalue;
        N = inum;
        color = c;
        left = right = nullptr;
    }
};

上述结点定义还是挺直观的。除此之外还需要一个测试结点与父结点之间链接颜色的函数isRed()和得到以该结点为根的子树的子结点数目size()，实现如下。

  
bool isRed(RBNode<Key,Value> &h){
    if(h == nullptr) return false;
    return h.color == RED;
}

int size(RBNode<Key,Value> &h){
    if(h == nullptr) {
        return 0;
    }else{
        return h.N;
    }; 
}

3.2.2 旋转

左旋转

  
//左转
RBNode<Key,Value> rotateLeft(RBNode<Key,Value> &h){
    RBNode<Key,Value> x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

右旋转

右旋转是将上面左旋实现进行镜像，left改为right，right改为left。

  
//右转
RBNode<Key,Value> rotateRight(RBNode<Key,Value> &h){
    RBNode<Key,Value> = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

颜色变化

  
//改变颜色
void flipColor(RBNode<Key,Value> &h){
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

插入的总体实现

  
//...
public:
    //...
    void put(Key &key,Value &value){
        root = put(root, key, value);
        root.color = BLACK;
    }
    //...
private:
    //...
    //插入
    RBNode<Key,Value> put(RBNode<Key,Value> &h, Key &key, Value &value){
        if(h == nullptr){
            temp = new RBNode<Key, Value>(Key, Value, 1, RED);
            return temp;
        }
        if(key > h.key){
            h.right = put(h.right, key, value);
        }else if(key < h.key){
            h.left = put(h.left, key, value);
        }else{
            h.value = value;
        }

        if(isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h);
        if(isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);
        if(isRed(h.left) && isRed(h.right))
            flipColor(h);

        h.N = 1 + size(h.left) + size(h.right);
        return h;
    }
    //...
//...