C++ 红黑树原理与代码实现

2.2 红黑树结构实现

在实现了红黑树节点的结构之后，接下来我们创建一个名为 RBTree 的类，在该类内实现红黑树的结构以及各种功能，接下来就先实现结构，实现的代码如下所示：

template<class K, class V> 
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    //各种功能……
private:
    Node* root = nullptr;
};

以上我们时使用类模板的方式来创建对应的二叉树，这样就可以使得创建的二叉树内节点的数据的类型是任意的，不过要存储在红黑树内的数据类型是需要能进行大小的比较，如果默认不支持也是需要我们自己实现的。

2.3 红黑树插入实现

以上实现了红黑树的大体结构之后接下来就来实现红黑树当中的插入功能，接下来在实现插入的代码之前先来分析在红黑树当中插入新的节点会有几种情况。

在插入新的节点之后，新形成的也是要满足红黑树的 4 条规则的。

1. 在空树当中插入节点，那么新增的节点需要是红色节点。

在非空的树当中插入新的节点，此时我们就要思考应将新的节点的颜色置为黑的还是红色？

如果我们插入的节点是红色的那么就只需要在其父节点为红色是进行调整，但是如果插入的节点为黑色的，这就会使得新产生的路径内的黑色节点数比其他的路径要多一个，这时要进行调整是很困难的，因此插入的节点应该初始化为红节点。

2. 在非空树当中插入新的节点，将该节点初始化为红

在非空树内插入新节点之后接下来就要看其父节点是否为红，是的话此时的树就违背了红黑树的规则 3，就需要进行调整。调整直到没有应该红色节点的父节点为红为止。如果一开始插入的节点的父节点就为黑；那么插入完就可以停止操作。

以下就是实现的不包含调整调整代码的插入代码：

bool Insert(const pair <K, V> kv) {
    //当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
    if (root == nullptr) {
        root = new Node(kv);
        root->_col = BLACK;
        return true;
    }
    //寻找合适的插入位置
    Node* cur = root;
    Node* Parent = nullptr;
    while (cur) {
        if (cur->_val.first < kv.first) {
            Parent = cur;
            cur = cur->_right;
        } else if (cur->_val.first > kv.first) {
            Parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    //创建新节点
    cur = new Node(kv);
    if (Parent->_val.first < kv.first) {
        Parent->_right = cur;
    } else {
        Parent->_left = cur;
    }
    cur->_parent = Parent;
    cur->_col = RED;
    //进行调整使得树满足红黑树的规则……
    //无论以上是否进行调整都将根结点的颜色置为黑
    root->_col = BLACK;
    return true;
}

接下来就来讲解插入的节点的父节点为红时进行调整的 3 种情况。

注：接下来的讲解当中假设我们把新增结点标识为 c (cur)，c 的父亲标识为 p(parent)，p 的父亲标识为 g(grandfather)，p 的兄弟标识为 u（uncle）。

1. 情况 1：只需变色

当插入的节点的为父亲节点为红时，而且父亲的父亲的另一个节点也是红的，也就是 c 节点的叔叔节点 u 也为红时。因为在插入新的节点 c 之前当前的树一定是满足红黑树的规则的，那么此时 p 节点的父亲节点 f 一定是为黑，也就是 c 节点的祖父节点一定为黑。

例如以下示例：

新插入的节点为 x，此时 c、p、u 的节点颜色情况就满足以上描述的形式。那么要让该节点变回满足红黑树的规则，就只需要将 p、u 变黑；g 变红即可。这时调整完之后就可以使得树当中每条路径内的黑色节点的个数都相同。

以下是只进行变色情况的抽象表达，d/e/f 代表每条路径拥有 hb 个黑色结点的子树，a/b 代表每条路径拥有 hb-1 个黑色结点的根为红的子树，hb>=0。和之前学习 AVL 树一样接下来来通过看看几种只进行变色的情况。

那么接下来就开看看 hb==0、hb==1、hb==2 的情况，其中当 hb 等于 2 时，这里组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式一样的，变色再继续往上处理即可，所以我们只需要看抽象图即可。

通过以上的示例就可以看出在处理只需要变色的情况时，新出现的红色节点可能是新插入的也可能是下部分的节点调整上来的，此时只需要一直进行调整直到对应的 p 为黑时就停止。

实现的代码如下所示：

以下以 p 节点分别为 g 节点的左节点和右节点的两种情况分别进行分析。

bool Insert(const pair <K, V> kv) {
    //当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
    if (root == nullptr) {
        root = new Node(kv);
        root->_col = BLACK;
        return true;
    }
    //寻找合适的插入位置
    Node* cur = root;
    Node* Parent = nullptr;
    while (cur) {
        if (cur->_val.first < kv.first) {
            Parent = cur;
            cur = cur->_right;
        } else if (cur->_val.first > kv.first) {
            Parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    //创建新节点
    cur = new Node(kv);
    if (Parent->_val.first < kv.first) {
        Parent->_right = cur;
    } else {
        Parent->_left = cur;
    }
    cur->_parent = Parent;
    cur->_col = RED;
    while (Parent && Parent->_col == RED) {
        Node* grandfather = Parent->_parent;
        //父节点为祖父节点的左节点时
        // g
        // p u
        //c
        if (grandfather->_left == Parent) {
            Node* uncle = grandfather->_right;
            //叔叔存在且为红
            if (uncle && uncle->_col == RED) {
                Parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                Parent = cur->_parent;
            }
            //其他情况……
        }
        //父节点为祖父节点的右节点时
        // g
        // u p
        // c
        else {
            Node* uncle = grandfather->_left;
            //叔叔存在且为红
            if (uncle && uncle->_col == RED) {
                Parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                Parent = cur->_parent;
            }
            //其他情况……
        }
    }
    //无论以上是否进行调整都将根结点的颜色置为黑
    root->_col = BLACK;
    return true;
}

2. 情况 2：单旋 + 变色

以上情况 1 当中是叔叔存在且为红的情况，那么如果叔叔不存在或者是不为红又要怎么进行调整呢？

首先是 c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。

在此 p 是必须变为黑的，但是由于 u 为黑或者不存在，那么这就使得将 p 变为黑时 p 节点所在的路径的黑色节点的个数就与其他的路径不相同，那么这时就需要进行旋转来解决问题。

在此也是以 p 节点分别为 g 节点的左节点和右节点的两种情况分别进行分析

如果 p 是 g 的左，c 是 p 的左，那么以 g 为旋转点进行右单旋，再把 p 变黑，g 变红即可。p 变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 p 的⽗亲是黑色还是红色或者空都不违反规则。

如果 p 是 g 的右，c 是 p 的右，那么以 g 为旋转点进行左单旋，再把 p 变黑，g 变红即可。p 变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 p 的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

3. 情况 3：双旋 + 变色

以上我们分析了单旋的情，那么接下来就来分析双旋的情况，当插入 c 之后红黑树的子树结构如下所示时只使用单旋是无法实现调整之后的树满足红黑树的规则的，在此接下来要使用到双旋才能调整至满足要求。

c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。

在此 p 必须变黑，才能解决，连续红色结点的问题，u 不存在或者是⿊⾊的，但是这⾥单纯的变色⽆法解决问题，需要旋转 + 变色。

如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可。c 变成课这颗树新的根，这样子树黑⾊结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变⿊，g 变红即可。c 变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的⽗亲是黑色还是黑色还是红⾊或者空都不违反规则。

2.4 插入完整代码

以上我们就进行插入节点的三种情况的分析，那么接下来就将以上的插入代码补充完整。

bool Insert(const pair <K, V> kv) {
    //当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
    if (root == nullptr) {
        root = new Node(kv);
        root->_col = BLACK;
        return true;
    }
    //寻找合适的插入位置
    Node* cur = root;
    Node* Parent = nullptr;
    while (cur) {
        if (cur->_val.first < kv.first) {
            Parent = cur;
            cur = cur->_right;
        } else if (cur->_val.first > kv.first) {
            Parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    //创建新节点
    cur = new Node(kv);
    if (Parent->_val.first < kv.first) {
        Parent->_right = cur;
    } else {
        Parent->_left = cur;
    }
    cur->_parent = Parent;
    cur->_col = RED;
    while (Parent && Parent->_col == RED) {
        Node* grandfather = Parent->_parent;
        //父节点为祖父节点的左节点时
        // g
        // p u
        //c
        if (grandfather->_left == Parent) {
            Node* uncle = grandfather->_right;
            //叔叔存在且为红
            if (uncle && uncle->_col == RED) {
                Parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                Parent = cur->_parent;
            }
            //叔叔不存在或者为黑
            else {
                //当 c 为 p 的左节点时
                // g
                // p u
                //c
                if (Parent->_left == cur) {
                    RotateR(grandfather);
                    grandfather->_col = RED;
                    Parent->_col = BLACK;
                }
                //当 c 为 p 的右节点时
                // g
                // p u
                // c
                else {
                    RotateL(Parent);
                    RotateR(grandfather);
                    grandfather->_col = RED;
                    cur->_col = BLACK;
                }
                break;
            }
        }
        //父节点为祖父节点的右节点时
        // g
        // u p
        // c
        else {
            Node* uncle = grandfather->_left;
            //叔叔存在且为红
            if (uncle && uncle->_col == RED) {
                Parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                Parent = cur->_parent;
            }
            //叔叔不存在或者为黑
            else {
                //当 c 为 p 的右节点时
                // g
                // u p
                // c
                if (Parent->_right == cur) {
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    Parent->_col = BLACK;
                }
                //当 c 为 p 的左节点时
                // g
                // u p
                // c
                else {
                    RotateR(Parent);
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    cur->_col = BLACK;
                }
                break;
            }
        }
    }
    //无论以上是否进行调整都将根结点的颜色置为黑
    root->_col = BLACK;
    return true;
}
void RotateR(Node* Parent) {
    Node* subL = Parent->_left;
    Node* subLR = subL->_right;
    if (subLR != nullptr) {
        subLR->_parent = Parent;
    }
    Node* tmpNode = Parent->_parent;
    Parent->_left = subLR;
    Parent->_parent = subL;
    subL->_right = Parent;
    if (tmpNode != nullptr) {
        if (tmpNode->_left == Parent) {
            tmpNode->_left = subL;
        } else {
            tmpNode->_right = subL;
        }
        subL->_parent = tmpNode;
    } else {
        root = subL;
        subL->_parent = nullptr;
    }
}
void RotateL(Node* Parent) {
    Node* subR = Parent->_right;
    Node* subRL = subR->_left;
    if (subRL != nullptr) {
        subRL->_parent = Parent;
    }
    Node* tmpNode = Parent->_parent;
    Parent->_right = subRL;
    Parent->_parent = subR;
    subR->_left = Parent;
    if (tmpNode != nullptr) {
        if (tmpNode->_left == Parent) {
            tmpNode->_left = subR;
        } else {
            tmpNode->_right = subR;
        }
        subR->_parent = tmpNode;
    } else {
        root = subR;
        subR->_parent = nullptr;
    }
}

2.5 红黑树查找

在此红黑树的查找实现和之前实现的二叉搜索树和 AVL 树类似，对你来说实现查找的代码肯定是 so easy 的，在此就不再进行讲解，直接奉上代码：

Node* Find(const K& val) {
    if (root == nullptr) {
        return nullptr;
    }
    Node* cur = root;
    while (cur) {
        if (cur->_val.first < val) {
            cur = cur->_left;
        } else if (cur->_val.first > val) {
            cur = cur->_right;
        } else {
            return cur;
        }
    }
    return nullptr;
}

2.6 红黑树删除

在此红黑树的删除较为复杂且不是很重要，在此就不进行讲解。

2.7 红黑树验证

以上我们实现了红黑树的插入以及查找，那么接下来就来实现验证的代码。

首先来分析验证的代码该如何实现： 这力获取最长路径和最短路径，检查最长路径不超过最短路径的 2 倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查 4 点规则，满足这 4 点规则，⼀定能保证最长路径不超过最短路径的 2 倍。

1. 规则 1 枚举颜⾊类型，天然实现保证了颜色不是黑色就是红色。
2. 规则 2 直接检查根即可
3. 规则 3 前序遍历检查，遇到红色结点查孩子不太方便，因为孩⼦有两个，且不⼀定存在，反过来检查父亲的颜色就方便多了。
4. 规则 4 前序遍历，遍历过程中用形参记录跟到当前结点的 blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径黑色结点数量作为参考值，依次比较即可。

实现代码如下所示：

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        // 前序遍历⾛到空时，意味着⼀条路径⾛完了
        //cout << blackNum << endl;
        if (refNum != blackNum) {
            cout << "存在⿊⾊结点的数量不相等的路径" << endl;
            return false;
        }
        return true;
    }
    // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
    if (root->_col == RED && root->_parent->_col == RED) {
        cout << root->_val.first << "存在连续的红⾊结点" << endl;
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
}
bool IsBalance() {
    if (root == nullptr) return true;
    if (root->_col == RED) return false;
    // 参考值
    int refNum = 0;
    Node* cur = root;
    while (cur) {
        if (cur->_col == BLACK) {
            ++refNum;
        }
        cur = cur->_left;
    }
    return Check(root, 0, refNum);
}

测试用例：

void TestRBTree1() {
    RBTree<int, int> t;
    // 常规的测试⽤例
    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    // 特殊的带有双旋场景的测试⽤例
    //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        t.Insert({ e, e });
    }
    t.InOrder();
    //cout << t.IsBalanceTree() << endl;
    cout<<t.IsBalance();
}

运行以上代码输出如下所示：

这时只能是说明对以上示例的测试用例进行插入是没问题的，要更严谨的验证就需要有更多的测试用例，这时使用以上的代码进行验证，并且测试进行插入的效率以及查找效率。

void TestRBTree2() {
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i);
    }
    size_t begin2 = clock();
    RBTree<int, int> t;
    for (auto e : v) {
        t.Insert(make_pair(e, e));
    }
    size_t end2 = clock();
    cout << t.IsBalance() << endl;
    cout << "Insert:" << end2 - begin2 << endl;
    cout << "Height:" << t.Height() << endl;
    cout << "Size:" << t.Size() << endl;
    size_t begin1 = clock();
    // 确定在的值
    /*for (auto e : v) { t.Find(e); }*/
    // 随机值
    for (size_t i = 0; i < N; i++) {
        t.Find((rand() + i));
    }
    size_t end1 = clock();
    cout << "Find:" << end1 - begin1 << endl;
}

将 vs 的调整为 release 模式之后，通过输出的结果就可以看出我们实现的红黑树的插入代码是没问题的，并且实现的红黑树的插入效率以及查找效率都是很高的，效率基本和 AVL 树不差上下。

2.8 完整代码

RBTree.h

#pragma once
#include<iostream>
using namespace std;
enum colour { RED, BLACK };
template<class K, class V> 
struct RBTreeNode {
    pair<K, V> _val;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    colour _col;
    RBTreeNode(const pair<K, V>& val) :_val(val) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) { }
};
template<class K, class V> 
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    bool Insert(const pair <K, V> kv) {
        //当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
        if (root == nullptr) {
            root = new Node(kv);
            root->_col = BLACK;
            return true;
        }
        //寻找合适的插入位置
        Node* cur = root;
        Node* Parent = nullptr;
        while (cur) {
            if (cur->_val.first < kv.first) {
                Parent = cur;
                cur = cur->_right;
            } else if (cur->_val.first > kv.first) {
                Parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }
        //创建新节点
        cur = new Node(kv);
        if (Parent->_val.first < kv.first) {
            Parent->_right = cur;
        } else {
            Parent->_left = cur;
        }
        cur->_parent = Parent;
        cur->_col = RED;
        while (Parent && Parent->_col == RED) {
            Node* grandfather = Parent->_parent;
            //父节点为祖父节点的左节点时
            // g
            // p u
            //c
            if (grandfather->_left == Parent) {
                Node* uncle = grandfather->_right;
                //叔叔存在且为红
                if (uncle && uncle->_col == RED) {
                    Parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    Parent = cur->_parent;
                }
                //叔叔不存在或者为黑
                else {
                    //当 c 为 p 的左节点时
                    // g
                    // p u
                    //c
                    if (Parent->_left == cur) {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        Parent->_col = BLACK;
                    }
                    //当 c 为 p 的右节点时
                    // g
                    // p u
                    // c
                    else {
                        RotateL(Parent);
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;
                }
            }
            //父节点为祖父节点的右节点时
            // g
            // u p
            // c
            else {
                Node* uncle = grandfather->_left;
                //叔叔存在且为红
                if (uncle && uncle->_col == RED) {
                    Parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    Parent = cur->_parent;
                }
                //叔叔不存在或者为黑
                else {
                    //当 c 为 p 的右节点时
                    // g
                    // u p
                    // c
                    if (Parent->_right == cur) {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        Parent->_col = BLACK;
                    }
                    //当 c 为 p 的左节点时
                    // g
                    // u p
                    // c
                    else {
                        RotateR(Parent);
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;
                }
            }
        }
        //无论以上是否进行调整都将根结点的颜色置为黑
        root->_col = BLACK;
        return true;
    }
    Node* Find(const K& val) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* cur = root;
        while (cur) {
            if (cur->_val.first < val) {
                cur = cur->_left;
            } else if (cur->_val.first > val) {
                cur = cur->_right;
            } else {
                return cur;
            }
        }
        return nullptr;
    }
    void InOrder() {
        _InOrder(root);
        cout << endl;
    }
    int Height() {
        return _Height(root);
    }
    int Size() {
        return _Size(root);
    }
    bool Check(Node* root, int blackNum, const int refNum) {
        if (root == nullptr) {
            // 前序遍历⾛到空时，意味着⼀条路径⾛完了
            //cout << blackNum << endl;
            if (refNum != blackNum) {
                cout << "存在⿊⾊结点的数量不相等的路径" << endl;
                return false;
            }
            return true;
        }
        // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
        if (root->_col == RED && root->_parent->_col == RED) {
            cout << root->_val.first << "存在连续的红⾊结点" << endl;
            return false;
        }
        if (root->_col == BLACK) {
            blackNum++;
        }
        return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
    }
    bool IsBalance() {
        if (root == nullptr) return true;
        if (root->_col == RED) return false;
        // 参考值
        int refNum = 0;
        Node* cur = root;
        while (cur) {
            if (cur->_col == BLACK) {
                ++refNum;
            }
            cur = cur->_left;
        }
        return Check(root, 0, refNum);
    }
private:
    Node* root = nullptr;
    void RotateR(Node* Parent) {
        Node* subL = Parent->_left;
        Node* subLR = subL->_right;
        if (subLR != nullptr) {
            subLR->_parent = Parent;
        }
        Node* tmpNode = Parent->_parent;
        Parent->_left = subLR;
        Parent->_parent = subL;
        subL->_right = Parent;
        if (tmpNode != nullptr) {
            if (tmpNode->_left == Parent) {
                tmpNode->_left = subL;
            } else {
                tmpNode->_right = subL;
            }
            subL->_parent = tmpNode;
        } else {
            root = subL;
            subL->_parent = nullptr;
        }
    }
    void RotateL(Node* Parent) {
        Node* subR = Parent->_right;
        Node* subRL = subR->_left;
        if (subRL != nullptr) {
            subRL->_parent = Parent;
        }
        Node* tmpNode = Parent->_parent;
        Parent->_right = subRL;
        Parent->_parent = subR;
        subR->_left = Parent;
        if (tmpNode != nullptr) {
            if (tmpNode->_left == Parent) {
                tmpNode->_left = subR;
            } else {
                tmpNode->_right = subR;
            }
            subR->_parent = tmpNode;
        } else {
            root = subR;
            subR->_parent = nullptr;
        }
    }
    void _InOrder(Node* cur) {
        if (cur == nullptr) {
            return;
        }
        _InOrder(cur->_left);
        cout << cur->_val.first << ":"<<cur->_val.second<<endl;
        _InOrder(cur->_right);
    }
    int _Height(Node* cur) {
        if (cur == nullptr) {
            return 0;
        }
        int Left = _Height(cur->_left);
        int Right = _Height(cur->_right);
        return Left > Right ? Left + 1 : Right + 1;
    }
    int _Size(Node* cur) {
        if (cur == nullptr) {
            return 0;
        }
        return 1 + _Size(cur->_left) + _Size(cur->_right);
    }
};

test.cpp

#include<iostream>
#include<vector>
#include"RBTree.h"
using namespace std;
void TestRBTree1() {
    RBTree<int, int> t;
    // 常规的测试⽤例
    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    // 特殊的带有双旋场景的测试⽤例
    //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        t.Insert({ e, e });
    }
    t.InOrder();
    //cout << t.IsBalanceTree() << endl;
    cout<<t.IsBalance();
}
void TestRBTree2() {
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i);
    }
    size_t begin2 = clock();
    RBTree<int, int> t;
    for (auto e : v) {
        t.Insert(make_pair(e, e));
    }
    size_t end2 = clock();
    cout << t.IsBalance() << endl;
    cout << "Insert:" << end2 - begin2 << endl;
    cout << "Height:" << t.Height() << endl;
    cout << "Size:" << t.Size() << endl;
    size_t begin1 = clock();
    // 确定在的值
    /*for (auto e : v) { t.Find(e); }*/
    // 随机值
    for (size_t i = 0; i < N; i++) {
        t.Find((rand() + i));
    }
    size_t end1 = clock();
    cout << "Find:" << end1 - begin1 << endl;
}
int main() {
    //TestAVLTree1();
    TestRBTree2();
    return 0;
}

以上就是本篇的全部内容了，在实现了红黑树之后接下来我们就可以基于红黑树来自己实现封装 set 和 map。