用C++来实现红黑树完整代码

黑格尔曾经说过：熟知非真知，一直在使用map和set容器，也知道它们的底层是红黑树，但是红黑树究竟是如何实现的？今天剖析了一下红黑树的底层原理，并且动手实现了一棵红黑树。
首先，红黑树的几个性质如下：
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 所有叶子都是黑色。（叶子是NULL节点！）
性质4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这个红黑树具有这样几个API接口：

1、判断节点的红、黑
2、在树上插入节点
3、根据红黑树结点的key值找到value的值
4、判断红黑树上元素的个数
5、层序遍历打印红黑树（有换行型）
在实现API接口前，需要对红黑树的结点定义一个结构体：

template <class T1, class T2>
class RBnode {
public:
    bool color;
    T1 key;
    T2 vaule;
    RBnode *left;
    RBnode *right;
    RBnode(T1 key, T2 vaule,bool c, RBnode *l, RBnode *r){
        this->key = key;
        this->vaule = vaule;
        color = c;
        left = l;
        right = r;
    }
};

这部分直接以代码的形式给出，使用类模板T1,T2，每一个结点包含属性为：key值、value值、颜色信息（红1黑0）、左右子节点。除此之外，在红黑树的类中要定义的成员变量有：元素的个数、根节点的信息、左旋右旋颜色翻转的方法：

左旋

右旋

颜色翻转

这三种方法是为了维护红黑树插入删除时规则而制定的翻转规则，需要保证红黑树的只有左侧能为红、同一节点不能连接两个红色节点、还有红黑树本身具有的性质：1、平衡树。2、查找树：左value<根value<右value的性质而制定的，在实际的插入过程中，规则如下：

红黑树插入结点时的规则

OK！具备了实现红黑树的基础知识和API设计之后我们来完成对红黑树的实际即可，下面直接上完整的红黑树实现以及测试的代码（注意模板的嵌套使用）：

#include <iostream>
using namespace std;
#include <string>
#include <queue>
template <class T1, class T2>
class RBnode {
public:
    bool color;
    T1 key;
    T2 vaule;
    RBnode *left;
    RBnode *right;
    RBnode(T1 key, T2 vaule,bool c, RBnode *l, RBnode *r){
        this->key = key;
        this->vaule = vaule;
        color = c;
        left = l;
        right = r;
    }
};
template <class T1,class T2>
class RBtree
{
public:
    RBnode<T1,T2> *root; //根节点
private:
    int N;           //树中的元素个数
    bool red = true;    
    bool black = false;


    //成员方法2：左旋
    RBnode<T1,T2>* rotate_left(RBnode<T1, T2> *x) {
        RBnode<T1, T2> *x_r = x->right;
        RBnode<T1, T2> *x_r_l = x_r->left;
        x->right = x_r_l;
        x_r->left = x;
        x_r->color = x->color;
        x->color = red;
        return x_r;
    }
    //成员方法3：右旋
    RBnode<T1, T2>* rotate_right(RBnode<T1, T2> *x) {
        RBnode<T1, T2> *x_l = x->left;
        RBnode<T1, T2> *x_r = x->right;
        RBnode<T1, T2> *x_l_r = x_l->right;
        x->left = x_l_r;
        x_l->right = x;
        x_l->color = x->color;
        x->color = red;
        return x_l;
    }
    //成员方法3： 颜色翻转
    RBnode<T1, T2>* flip_color(RBnode<T1, T2> *x) {
        x->color = red;
        x->left->color = black;
        x->right->color = black;
        return x;
    }
public:
    //成员方法1：判断节点是否为红色节点
    bool is_red(RBnode<T1, T2> *x) {
        if (x == NULL) return false; //空节点为黑色！！
        else return x->color == red;
    }
    //成员方法4： 整个树上插入
    void put(T1 key, T2 vaule) {
        root = put(root, key, vaule);
        root->color = black;
    }
    //成员方法5： 指定树插入
    RBnode<T1, T2>* put(RBnode<T1, T2> *x, T1 key, T2 vaule) {
        if (x == NULL) {
            N++;
            RBnode<T1, T2>* k = new RBnode<T1, T2> (key, vaule, red, NULL, NULL);
            return k;
        }
        if (key > x->key) x->right = put(x->right, key, vaule);
        else if (key < x->key) x->left = put(x->left, key, vaule);
        else x->vaule = vaule; //若key值相同，则更新相当节点的value值
        if (is_red(x->right) && !is_red(x->left)) x=rotate_left(x);
        if (is_red(x->left) && is_red(x->left->left)) x=rotate_right(x);
        if (is_red(x->right) && is_red(x->left)) x=flip_color(x);
        return x;
    }
    //成员方法6：根据key查找对应的值
    T2 get(T1 key) {
        return get(root, key);
    }
    T2 get(RBnode<T1, T2> *x, T1 key) {
        if (x == NULL) return NULL;
        if (key < x->key) {
            return get(x->left, key);
        }
        else if (key > x->key) {
            return get(x->right, key);
        }
        else return x->vaule;
    }
    //成员方法7：获取树中元素个数
    int size() {
        return N;
    }
public:
    void print_it(RBnode<T1, T2>*x) {
        if (x == NULL) return;
        queue<RBnode<T1, T2>*> res;
        res.push(x);
        int to_print = 1;
        int next_line = 0;
        while (res.size() != 0) {
            RBnode<T1, T2>*p = res.front();
            if (p->left != NULL) {
                res.push(p->left);
                ++next_line;
            }
            if (p->right != NULL) {
                res.push(p->right);
                ++next_line;
            }
            if (p->color)
                cout << p->key << " " << p->vaule << " " << "红色" << "       ";
            else cout << p->key << " " << p->vaule << " " << "黑色" << "       ";
            --to_print;
            res.pop();
            if (to_print == 0) {
                to_print = next_line;
                cout << endl;
                next_line = 0;
            }
        }
    }
};

int main() {
    RBtree<int, string> res ;
    res.put(3, "TJ");
    res.put(4, "NUK");
    res.put(1, "TJU");
    res.print_it(res.root);
    res.put(5, "自动化");
    res.put(2, "国工");
    cout << res.get(5) << endl;
    
    res.put(5, "湖人总冠军");
    cout << res.get(5) << endl;
    res.put(6, "0offer");
    res.put(9, "bboffer");
    cout << res.size();
    cout << endl;
    res.print_it(res.root);
    system("pause");
}

我们对每个红黑树的节点的key赋为int类型，value为string类型，我们打印一下测试结果：

红黑树的测试结果

我们将这个结果画一下显得更加直观：

测试结果手绘

我们可以看出，构造的二叉树完全符合红黑树的条件，但是要注意：红黑树虽然称他是平衡树，但是并不一定满足各个同一深度的各个子树深度差至多为1的条件，它是依靠自身的性质来自平衡。到此，一棵简易的红黑树就搭建完毕啦。