红黑树

红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。 除了具备该特性之外，红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] (4) 如果一个节点是红色的，则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性，需要注意的是： 第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。 第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树

介绍见 hhttps://www.cnblogs.com/skywang12345/p/3624291.html

最难的部分是remove，需要好好理解。

这里是先delete后修复。还有一种是先修复，后delete，需要区分。

delete的时候因为不需要考虑是否平衡所以，在delele双子节点的情况下，不需要考虑用前驱节点代替还是后继节点代替。统一用一个就好。一般使用后继节点。

删除

分先删除后修复，下方的remove函数和先修复，后删除下方myRemove函数

原理差不多

说一下先修复后删除的逻辑

因为有双子节点的节点删除最后会演变成删除单子节点或者无子节点，（见AVL的删除逻辑）

A.删除的节点是红的 =》 正常删除(父亲的left或right指向子，子的parent指向父，delete node)

B 删除的节点是黑的

1. 是根节点 =》 正常删除 根赋给子，如过子存在，染成黑的
2. 删除的节点有1个子 =》子变黑，正常逻辑删除
3. 删除节点无子，但是兄弟是黑的，远侄子是红的,近侄子是啥颜色无所谓（如果节点不存在nill，也默认是黑的。） => 如果兄弟染成父色，父跟远侄子染黑，如果删除节点是父的左子，左旋父，反之，右旋父。正常删除、
4. 删除节点无子，但是兄弟是黑的，远侄子是黑的，近侄子是红的 =》兄弟染黑，近侄子染红，如果是父的左子，右旋兄弟，反之，左旋兄弟，继续判断。
5. 删除节点无子，但是兄弟是黑的，远侄子是黑的，近侄子是黑的 => 1.父是根或者是红的。父亲变黑，兄弟变红，正常删除 2. 父亲是黑的且不是根 ，兄弟变红，当前删除节点变成父，继续判断。
6. 删除节点无子，但是兄弟是红的。 =》父亲染红，兄弟染黑。如果是父的左子，左旋父，反之右旋父，继续判断。

/**	
 * C++ 语言: 红黑树
 *
 * @author skywang
 * @date 2013/11/07
 */

#ifndef _RED_BLACK_TREE_HPP_
#define _RED_BLACK_TREE_HPP_

#include <iomanip>
#include <iostream>
using namespace std;

enum RBTColor { RED, BLACK };

template <class T>
class RBTNode {
public:
    RBTColor color;    // 颜色
    T key;            // 关键字(键值)
    RBTNode* left;    // 左孩子
    RBTNode* right;    // 右孩子
    RBTNode* parent; // 父结点

    RBTNode(T value, RBTColor c, RBTNode* p, RBTNode* l, RBTNode* r) :
        key(value), color(c), parent(), left(l), right(r) {}
    ~RBTNode()
    {
        cout << "delete : " << key << endl;
    }
};

template <class T>
class RBTree {
private:
    RBTNode<T>* mRoot;    // 根结点

public:
    RBTree();
    ~RBTree();

    // 前序遍历"红黑树"
    void preOrder();
    // 中序遍历"红黑树"
    void inOrder();
    // 后序遍历"红黑树"
    void postOrder();

    // (递归实现)查找"红黑树"中键值为key的节点
    RBTNode<T>* search(T key);
    // (非递归实现)查找"红黑树"中键值为key的节点
    RBTNode<T>* iterativeSearch(T key);

    // 查找最小结点：返回最小结点的键值。
    T minimum();
    // 查找最大结点：返回最大结点的键值。
    T maximum();

    // 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
    RBTNode<T>* successor(RBTNode<T>* x);
    // 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
    RBTNode<T>* predecessor(RBTNode<T>* x);

    // 将结点(key为节点键值)插入到红黑树中
    void insert(T key);

    // 删除结点(key为节点键值)
    void remove(T key);

    // 销毁红黑树
    void destroy();

    // 打印红黑树
    void print();
private:
    // 前序遍历"红黑树"
    void preOrder(RBTNode<T>* tree) const;
    // 中序遍历"红黑树"
    void inOrder(RBTNode<T>* tree) const;
    // 后序遍历"红黑树"
    void postOrder(RBTNode<T>* tree) const;

    // (递归实现)查找"红黑树x"中键值为key的节点
    RBTNode<T>* search(RBTNode<T>* x, T key) const;
    // (非递归实现)查找"红黑树x"中键值为key的节点
    RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;

    // 查找最小结点：返回tree为根结点的红黑树的最小结点。
    RBTNode<T>* minimum(RBTNode<T>* tree);
    // 查找最大结点：返回tree为根结点的红黑树的最大结点。
    RBTNode<T>* maximum(RBTNode<T>* tree);

    // 左旋
    void leftRotate(RBTNode<T>*& root, RBTNode<T>* x);
    // 右旋
    void rightRotate(RBTNode<T>*& root, RBTNode<T>* y);
    // 插入函数
    void insert(RBTNode<T>*& root, RBTNode<T>* node);

    void insert(RBTNode<T>*& root, RBTNode<T>* node);
    // 插入修正函数
    void insertFixUp(RBTNode<T>*& root, RBTNode<T>* node);
    // 删除函数
    void remove(RBTNode<T>*& root, RBTNode<T>* node);
    // 先修复，再删除
    void myRemove(RBTNode<T>*& root, RBTNode<T>* node);
    // 删除修正函数
    void removeFixUp(RBTNode<T>*& root, RBTNode<T>* node, RBTNode<T>* parent);

    // 销毁红黑树
    void destroy(RBTNode<T>*& tree);

    // 打印红黑树
    void print(RBTNode<T>* tree, T key, int direction);

#define rb_parent(r)   ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r)   ((r)->color==RED)
#define rb_is_black(r)  ((r)->color==BLACK)
#define rb_set_black(r)  do { (r)->color = BLACK; } while (0)
#define rb_set_red(r)  do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c)  do { (r)->color = (c); } while (0)
};

/*
 * 构造函数
 */
template <class T>
RBTree<T>::RBTree() :mRoot(NULL)
{
    mRoot = NULL;
}

/*
 * 析构函数
 */
template <class T>
RBTree<T>::~RBTree()
{
    destroy();
}

/*
 * 前序遍历"红黑树"
 */
template <class T>
void RBTree<T>::preOrder(RBTNode<T>* tree) const
{
    if (tree != NULL)
    {
        cout << tree->key << " ";
        preOrder(tree->left);
        preOrder(tree->right);
    }
}

template <class T>
void RBTree<T>::preOrder()
{
    preOrder(mRoot);
}

/*
 * 中序遍历"红黑树"
 */
template <class T>
void RBTree<T>::inOrder(RBTNode<T>* tree) const
{
    if (tree != NULL)
    {
        inOrder(tree->left);
        cout << tree->key << " ";
        inOrder(tree->right);
    }
}

template <class T>
void RBTree<T>::inOrder()
{
    inOrder(mRoot);
}

/*
 * 后序遍历"红黑树"
 */
template <class T>
void RBTree<T>::postOrder(RBTNode<T>* tree) const
{
    if (tree != NULL)
    {
        postOrder(tree->left);
        postOrder(tree->right);
        cout << tree->key << " ";
    }
}

template <class T>
void RBTree<T>::postOrder()
{
    postOrder(mRoot);
}

/*
 * (递归实现)查找"红黑树x"中键值为key的节点
 */
template <class T>
RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const
{
    if (x == NULL || x->key == key)
        return x;

    if (key < x->key)
        return search(x->left, key);
    else
        return search(x->right, key);
}

template <class T>
RBTNode<T>* RBTree<T>::search(T key)
{
    search(mRoot, key);
}

/*
 * (非递归实现)查找"红黑树x"中键值为key的节点
 */
template <class T>
RBTNode<T>* RBTree<T>::iterativeSearch(RBTNode<T>* x, T key) const
{
    while ((x != NULL) && (x->key != key))
    {
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    return x;
}

template <class T>
RBTNode<T>* RBTree<T>::iterativeSearch(T key)
{
    iterativeSearch(mRoot, key);
}

/*
 * 查找最小结点：返回tree为根结点的红黑树的最小结点。
 */
template <class T>
RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree)
{
    if (tree == NULL)
        return NULL;

    while (tree->left != NULL)
        tree = tree->left;
    return tree;
}

template <class T>
T RBTree<T>::minimum()
{
    RBTNode<T>* p = minimum(mRoot);
    if (p != NULL)
        return p->key;

    return (T)NULL;
}

/*
 * 查找最大结点：返回tree为根结点的红黑树的最大结点。
 */
template <class T>
RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree)
{
    if (tree == NULL)
        return NULL;

    while (tree->right != NULL)
        tree = tree->right;
    return tree;
}

template <class T>
T RBTree<T>::maximum()
{
    RBTNode<T>* p = maximum(mRoot);
    if (p != NULL)
        return p->key;

    return (T)NULL;
}

/*
 * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
 */
template <class T>
RBTNode<T>* RBTree<T>::successor(RBTNode<T>* x)
{
    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
    if (x->right != NULL)
        return minimum(x->right);

    // 如果x没有右孩子。则x有以下两种可能：
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    RBTNode<T>* y = x->parent;
    while ((y != NULL) && (x == y->right))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

/*
 * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
 */
template <class T>
RBTNode<T>* RBTree<T>::predecessor(RBTNode<T>* x)
{
    // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
    if (x->left != NULL)
        return maximum(x->left);

    // 如果x没有左孩子。则x有以下两种可能：
    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    RBTNode<T>* y = x->parent;
    while ((y != NULL) && (x == y->left))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

/*
 * 对红黑树的节点(x)进行左旋转
 *
 * 左旋示意图(对节点x进行左旋)：
 *      px                              px
 *     /                               /
 *    x                               y
 *   /  \      --(左旋)-->           / \                #
 *  lx   y                          x  ry
 *     /   \                       /  \
 *    ly   ry                     lx  ly
 *
 *
 */
template <class T>
void RBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x)
{
    // 设置x的右孩子为y
    RBTNode<T>* y = x->right;

    // 将 “y的左孩子” 设为 “x的右孩子”；
    // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
    x->right = y->left;
    if (y->left != NULL)
        y->left->parent = x;

    // 将 “x的父亲” 设为 “y的父亲”
    y->parent = x->parent;

    if (x->parent == NULL)
    {
        root = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
    }
    else
    {
        if (x->parent->left == x)
            x->parent->left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
        else
            x->parent->right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
    }

    // 将 “x” 设为 “y的左孩子”
    y->left = x;
    // 将 “x的父节点” 设为 “y”
    x->parent = y;
}

/*
 * 对红黑树的节点(y)进行右旋转
 *
 * 右旋示意图(对节点y进行左旋)：
 *            py                               py
 *           /                                /
 *          y                                x
 *         /  \      --(右旋)-->            /  \                     #
 *        x   ry                           lx   y
 *       / \                                   / \                   #
 *      lx  rx                                rx  ry
 *
 */
template <class T>
void RBTree<T>::rightRotate(RBTNode<T>*& root, RBTNode<T>* y)
{
    // 设置x是当前节点的左孩子。
    RBTNode<T>* x = y->left;

    // 将 “x的右孩子” 设为 “y的左孩子”；
    // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;

    // 将 “y的父亲” 设为 “x的父亲”
    x->parent = y->parent;

    if (y->parent == NULL)
    {
        root = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
    }
    else
    {
        if (y == y->parent->right)
            y->parent->right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
        else
            y->parent->left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
    }

    // 将 “y” 设为 “x的右孩子”
    x->right = y;

    // 将 “y的父节点” 设为 “x”
    y->parent = x;
}

/*
 * 红黑树插入修正函数
 *
 * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
 * 目的是将它重新塑造成一颗红黑树。
 *
 * 参数说明：
 *     root 红黑树的根
 *     node 插入的结点        // 对应《算法导论》中的z
 */
template <class T>
void RBTree<T>::insertFixUp(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* parent, * gparent;

    // 若“父节点存在，并且父节点的颜色是红色”
    while ((parent = rb_parent(node)) && rb_is_red(parent))
    {
        gparent = rb_parent(parent);

        //若“父节点”是“祖父节点的左孩子”
        if (parent == gparent->left)
        {
            // Case 1条件：叔叔节点是红色
            {
                RBTNode<T>* uncle = gparent->right;
                if (uncle && rb_is_red(uncle))
                {
                    rb_set_black(uncle);
                    rb_set_black(parent);
                    rb_set_red(gparent);
                    node = gparent;
                    continue;
                }
            }

            // Case 2条件：叔叔是黑色，且当前节点是右孩子
            if (parent->right == node)
            {
                RBTNode<T>* tmp;
                leftRotate(root, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // Case 3条件：叔叔是黑色，且当前节点是左孩子。
            rb_set_black(parent);
            rb_set_red(gparent);
            rightRotate(root, gparent);
        }
        else//若“z的父节点”是“z的祖父节点的右孩子”
        {
            // Case 1条件：叔叔节点是红色
            {
                RBTNode<T>* uncle = gparent->left;
                if (uncle && rb_is_red(uncle))
                {
                    rb_set_black(uncle);
                    rb_set_black(parent);
                    rb_set_red(gparent);
                    node = gparent;
                    continue;
                }
            }

            // Case 2条件：叔叔是黑色，且当前节点是左孩子
            if (parent->left == node)
            {
                RBTNode<T>* tmp;
                rightRotate(root, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // Case 3条件：叔叔是黑色，且当前节点是右孩子。
            rb_set_black(parent);
            rb_set_red(gparent);
            leftRotate(root, gparent);
        }
    }

    // 将根节点设为黑色
    rb_set_black(root);
}

/*
 * 将结点插入到红黑树中
 *
 * 参数说明：
 *     root 红黑树的根结点
 *     node 插入的结点        // 对应《算法导论》中的node
 */
template <class T>
void RBTree<T>::insert(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* y = NULL;
    RBTNode<T>* x = root;

    // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
    while (x != NULL)
    {
        y = x;
        if (node->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    node->parent = y;
    if (y != NULL)
    {
        if (node->key < y->key)
            y->left = node;
        else
            y->right = node;
    }
    else
        root = node;

    // 2. 设置节点的颜色为红色
    node->color = RED;

    // 3. 将它重新修正为一颗二叉查找树
    insertFixUp(root, node);
}

/*
 * 将结点(key为节点键值)插入到红黑树中
 *
 * 参数说明：
 *     tree 红黑树的根结点
 *     key 插入结点的键值
 */
template <class T>
void RBTree<T>::insert(T key)
{
    RBTNode<T>* z = NULL;

    // 如果新建结点失败，则返回。
    if ((z = new RBTNode<T>(key, BLACK, NULL, NULL, NULL)) == NULL)
        return;

    insert(mRoot, z);
}

/*
 * 红黑树删除修正函数
 *
 * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
 * 目的是将它重新塑造成一颗红黑树。
 *
 * 参数说明：
 *     root 红黑树的根
 *     node 待修正的节点
 */
template <class T>
void RBTree<T>::removeFixUp(RBTNode<T>*& root, RBTNode<T>* node, RBTNode<T>* parent)
{
    RBTNode<T>* other;

    while ((!node || rb_is_black(node)) && node != root)
    {
        if (parent->left == node)
        {
            other = parent->right;
            if (rb_is_red(other))
            {
                // Case 1: x的兄弟w是红色的
                rb_set_black(other);
                rb_set_red(parent);
                leftRotate(root, parent);
                other = parent->right;
            }
            if ((!other->left || rb_is_black(other->left)) &&
                (!other->right || rb_is_black(other->right)))
            {
                // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
                rb_set_red(other);
                node = parent;
                parent = rb_parent(node);
            }
            else
            {
                if (!other->right || rb_is_black(other->right))
                {
                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
                    rb_set_black(other->left);
                    rb_set_red(other);
                    rightRotate(root, other);
                    other = parent->right;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                rb_set_color(other, rb_color(parent));
                rb_set_black(parent);
                rb_set_black(other->right);
                leftRotate(root, parent);
                node = root;
                break;
            }
        }
        else
        {
            other = parent->left;
            if (rb_is_red(other))
            {
                // Case 1: x的兄弟w是红色的
                rb_set_black(other);
                rb_set_red(parent);
                rightRotate(root, parent);
                other = parent->left;
            }
            if ((!other->left || rb_is_black(other->left)) &&
                (!other->right || rb_is_black(other->right)))
            {
                // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
                rb_set_red(other);
                node = parent;
                parent = rb_parent(node);
            }
            else
            {
                if (!other->left || rb_is_black(other->left))
                {
                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
                    rb_set_black(other->right);
                    rb_set_red(other);
                    leftRotate(root, other);
                    other = parent->left;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                rb_set_color(other, rb_color(parent));
                rb_set_black(parent);
                rb_set_black(other->left);
                rightRotate(root, parent);
                node = root;
                break;
            }
        }
    }
    if (node)
        rb_set_black(node);
}

/*
 * 删除结点(node)，并返回被删除的结点(先delete，再修复)
 *
 * 参数说明：
 *     root 红黑树的根结点
 *     node 删除的结点
 */
template <class T>
void RBTree<T>::remove(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* child, * parent;
    RBTColor color;

    // 被删除节点的"左右孩子都不为空"的情况。
    if ((node->left != NULL) && (node->right != NULL))
    {
        // 被删节点的后继节点。(称为"取代节点")
        // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
        RBTNode<T>* replace = node;

        // 获取后继节点
        replace = replace->right;
        while (replace->left != NULL)
            replace = replace->left;

        // "node节点"不是根节点(只有根节点不存在父节点)
        if (rb_parent(node))
        {
            if (rb_parent(node)->left == node)
                rb_parent(node)->left = replace;
            else
                rb_parent(node)->right = replace;
        }
        else
            // "node节点"是根节点，更新根节点。
            root = replace;

        // child是"取代节点"的右孩子，也是需要"调整的节点"。
        // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
        child = replace->right;
        parent = rb_parent(replace);
        // 保存"取代节点"的颜色
        color = rb_color(replace);

        // "被删除节点"是"它的后继节点的父节点"
        if (parent == node)
        {
            parent = replace;
        }
        else
        {
            // child不为空
            if (child)
                rb_set_parent(child, parent);
            parent->left = child;

            replace->right = node->right;
            rb_set_parent(node->right, replace);
        }

        replace->parent = node->parent;
        replace->color = node->color;
        replace->left = node->left;
        node->left->parent = replace;
        delete node;
        
        if (color == BLACK)
            removeFixUp(root, child, parent);
        return;
    }

    if (node->left != NULL)
        child = node->left;
    else
        child = node->right;

    parent = node->parent;
    // 保存"取代节点"的颜色
    color = node->color;

    if (child)
        child->parent = parent;

    // "node节点"不是根节点
    if (parent)
    {
        if (parent->left == node)
            parent->left = child;
        else
            parent->right = child;
    }
    else
        root = child;

    if (color == BLACK)
        removeFixUp(root, child, parent);
    delete node;
}

/*
 * 删除结点(node)，并返回被删除的结点(先修复，再del)
 *
 * 参数说明：
 *     root 红黑树的根结点
 *     node 删除的结点
 */
template<class T>
inline void RBTree<T>::myRemove(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* child = nullptr;
    RBTNode<T>* parent = nullptr;
    // 如果是有两个子节点的节点，先进行转换，找到替代节点
    if (node->left != nullptr && node->right != nullptr) {
        RBTNode<T>* replace = node->right;
        while (replace->left != nullptr) {
            replace = replace->left;
        }
        T tmpKey = replace->key;
        replace->key = node->key;
        node->key = tmpKey;
        myRemove(mRoot, replace);
    }
    else {
        // 情况1：是红的
        if (node != mRoot && rb_is_red(node)) {
            parent = node->parent;
            if (node->left != nullptr) {
                child = node->left;
            }
            else {
                child = node->right;
            }
            if (parent->left == node) {
                parent->left = child;
            }
            else {
                parent->right = child;
            }
            if (child != nullptr) {
                child->parent = parent;
            }
            delete node;
            node = nullptr;
            return;
        }
        // 情况2 ： 删除节点是黑的
        if (rb_is_black(node)) {
            // (1) 是根节点
            if (node == mRoot) {
                if (node->left != nullptr) {
                    mRoot = node->left;
                }
                else {
                    mRoot = node->right;
                }
                if (mRoot != nullptr) {
                    rb_set_black(mRoot);
                }
                delete node;
                node = nullptr;
                return;
            }
            // (2) 不是跟，且有一个子
            else if (node->left != nullptr || node->right != nullptr) {
                parent = node->parent;
                if (node->left != nullptr) {
                    child = node->left;
                }
                else {
                    child = node->right;
                }
                if (parent->left == node) {
                    parent->left = child;
                }
                else {
                    parent->right = child;
                }
                if (child != nullptr) {
                    rb_set_black(child);
                    child->parent = parent;
                }
                delete node;
                node = nullptr;
                return;
            }
            // (3) 不是跟，无字
            else if (node->left == nullptr && node->right == nullptr) {
                RBTNode<T>* slibing = nullptr;
                RBTNode<T>* slibingNearChild = nullptr;
                RBTNode<T>* slibingRemoteChild = nullptr;
                parent = node->parent;
                if (parent->left == node) {
                    slibing = parent->right;
                    if (slibing != nullptr) {
                        slibingNearChild = slibing->left;
                        slibingRemoteChild = slibing->right;
                    }
                }
                else {
                    slibing = parent->left;
                    if (slibing != nullptr) {
                        slibingNearChild = slibing->right;
                        slibingRemoteChild = slibing->left;
                    }
                }
                RBTColor slibingNearChildColor = (slibingNearChild == nullptr) ? BLACK : slibingNearChild->color;
                RBTColor slibingRemoteChildColor = (slibingRemoteChild == nullptr) ? BLACK : slibingRemoteChild->color;
                RBTColor slibingColor = (slibing == nullptr) ? BLACK : slibing->color;
                // A:黑兄弟，远红侄子
                if (slibingColor == BLACK && slibingRemoteChildColor == RED) {
                    rb_set_color(slibing, parent->color);
                    rb_set_black(parent);
                    rb_set_black(slibingRemoteChild);
                    if (node == parent->left) {
                        leftRotate(mRoot, parent);
                    }
                    else {
                        rightRotate(mRoot, parent);
                    }
                    if (node->left != nullptr) {
                        child = node->left;
                    }
                    else {
                        child = node->right;
                    }
                    if (child != nullptr) {
                        child->parent = parent;
                    }
                    if (parent->left == node) {
                        parent->left = child;
                    }
                    else {
                        parent->right = child;
                    }
                    delete node;
                    node = nullptr;
                    return;
                }
                // B 嘿兄弟，近红侄子
                else if (slibingColor == BLACK && slibingRemoteChildColor == BLACK && slibingNearChildColor == RED) {
                    rb_set_red(slibing);
                    rb_set_black(slibingNearChild);
                    if (node == parent->left) {
                        rightRotate(mRoot, slibing);
                    }
                    else {
                        leftRotate(mRoot, slibing);
                    }
                    myRemove(mRoot, node);
                }
                // C 黑兄弟，黑双侄子
                else if (slibingColor == BLACK && slibingRemoteChildColor == BLACK && slibingNearChildColor == BLACK) {
                    if (parent == mRoot || rb_is_red(parent)) {
                        if (slibing) {
                            rb_set_red(slibing);
                        }
                        rb_set_black(parent);
                        if (node->left != nullptr) {
                            child = node->left;
                        }
                        else {
                            child = node->right;
                        }
                        if (child != nullptr) {
                            child->parent = parent;
                        }
                        if (parent->left == node) {
                            parent->left = child;
                        }
                        else {
                            parent->right = child;
                        }
                        delete node;
                        node = nullptr;
                        return;
                    }
                    else if (rb_is_black(parent)) {
                        rb_set_red(slibing);
                        myRemove(mRoot, parent);
                    }
                }
                // D 红兄弟
                else if (slibingColor == RED) {
                    rb_set_black(slibing);
                    rb_set_red(parent);
                    if (parent->left == node) {
                        leftRotate(mRoot, parent);
                    }
                    else {
                        rightRotate(mRoot, parent);
                    }
                    myRemove(mRoot, node);
                }
            }
        }
    }
}

/*
 * 删除红黑树中键值为key的节点
 *
 * 参数说明：
 *     tree 红黑树的根结点
 */
template <class T>
void RBTree<T>::remove(T key)
{
    RBTNode<T>* node;

    // 查找key对应的节点(node)，找到的话就删除该节点
    if ((node = search(mRoot, key)) != NULL) {
        //remove(mRoot, node);
        myRemove(mRoot, node);
    }
}

/*
 * 销毁红黑树
 */
template <class T>
void RBTree<T>::destroy(RBTNode<T>*& tree)
{
    if (tree == NULL)
        return;

    if (tree->left != NULL)
        destroy(tree->left);
    if (tree->right != NULL)
        destroy(tree->right);

    delete tree;
    tree = NULL;
}

template <class T>
void RBTree<T>::destroy()
{
    destroy(mRoot);
}

/*
 * 打印"二叉查找树"
 *
 * key        -- 节点的键值
 * direction  --  0，表示该节点是根节点;
 *               -1，表示该节点是它的父结点的左孩子;
 *                1，表示该节点是它的父结点的右孩子。
 */
template <class T>
void RBTree<T>::print(RBTNode<T>* tree, T key, int direction)
{
    if (tree != NULL)
    {
        if (direction == 0)    // tree是根节点
            cout << setw(2) << tree->key << "(B) is root" << endl;
        else                // tree是分支节点
            cout << setw(2) << tree->key << (rb_is_red(tree) ? "(R)" : "(B)") << " is " << setw(2) << key << "'s " << setw(12) << (direction == 1 ? "right child" : "left child") << endl;

        print(tree->left, tree->key, -1);
        print(tree->right, tree->key, 1);
    }
}

template <class T>
void RBTree<T>::print()
{
    if (mRoot != NULL)
        print(mRoot, mRoot->key, 0);
}

#endif

#include "HashTable.h"
#include <cmath>

/*
* brief  创建hash表
*/
void HashTable::CreateHashTable(int num)
{
    int size = GetNextPrimer(num);
    mMaxSize = size;
    if (mRoot == nullptr) {
        mRoot = new Node[size]();
        for (int i = 0; i < size; ++i) {
            mRoot[i].mValue = i;
        }
    }
}

/*
* brief 添加数据
*/
void HashTable::Insert(int num)
{
    int index = HashIndex(num);
    Node *tmp = mRoot[index].mNextNode;
    Node* data = new Node;
    data->mValue = num;
    mRoot[index].mNextNode = data;
    data->mNextNode = tmp;
}

/*
* brief 判断是否存在
*/
bool HashTable::Contains(int num)
{
    int index = HashIndex(num);
    // 这里一定要记得引用,如果不加引用，这里会变成函数内变量，会在函数结束时，析构掉。后边再用到的时候，就崩溃了.
    Node &node = mRoot[index];
    Node* tmp = node.mNextNode;
    while (tmp) {
        if (num == tmp->mValue) {
            return true;
        }
        tmp = tmp->mNextNode;
    }
    return false;
}

/*
* brief 判断素数
*/
bool HashTable::IsPrimer(int num)
{
    // 6x - 1 or 6x + 1
    if (num == 4 || num == 1) {
        return false;
    }
    for (int i = 5; i < std::sqrt(num); i = i + 6) {
        if (num % i == 0 || (num + 2) % i == 0) {
            return false;
        }
    }
    return true;
}

/*
* brief 取得大于num的最小素数
*/
int HashTable::GetNextPrimer(int num)
{
    int tmp = num % 2 == 0 ? num + 1 : num;
    while (!IsPrimer(tmp)) {
        tmp += 2;
    }
    return tmp;
}

/*
* brief 取得num在链表中的下标
*/
int HashTable::HashIndex(int num)
{
    return num % mMaxSize;
}

void RBTTest()
{
    int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
    int check_insert = 0;    // "插入"动作的检测开关(0，关闭；1，打开)
    int check_remove = 0;    // "删除"动作的检测开关(0，关闭；1，打开)
    int i;
    int ilen = (sizeof(a)) / (sizeof(a[0]));
    RBTree<int>* tree = new RBTree<int>();

    cout << "== 原始数据: ";
    for (i = 0; i < ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    for (i = 0; i < ilen; i++)
    {
        tree->insert(a[i]);
        // 设置check_insert=1,测试"添加函数"
        if (check_insert)
        {
            cout << "== 添加节点: " << a[i] << endl;
            cout << "== 树的详细信息: " << endl;
            tree->print();
            cout << endl;
        }

    }

    cout << "== 前序遍历: ";
    tree->preOrder();

    cout << "\n== 中序遍历: ";
    tree->inOrder();

    cout << "\n== 后序遍历: ";
    tree->postOrder();
    cout << endl;

    cout << "== 最小值: " << tree->minimum() << endl;
    cout << "== 最大值: " << tree->maximum() << endl;
    cout << "== 树的详细信息: " << endl;
    tree->print();

    // 设置check_remove=1,测试"删除函数"
    if (check_remove)
    {
        for (i = 0; i < ilen; i++)
        {
            tree->remove(a[i]);

            cout << "== 删除节点: " << a[i] << endl;
            cout << "== 树的详细信息: " << endl;
            tree->print();
            cout << endl;
        }
    }

    // 销毁红黑树
    tree->destroy();
    delete tree;
}