红黑树

插入和删除节点时要遵守红黑规则：

1. 每一个节点节点都有颜色，不是红色的就是黑色的。
2. 根总是黑色的。
3. 不能有连续的红色节点（如果节点是红色的，则它的子节点必须是黑色的），但是可以有连续的黑色节点。
4. 从根到叶子节点的每条路径，必须包含相同数目的黑色节点。

在insert新的节点的时候，动态进行平衡，左子树和右子树节点差不多，动态调整根节点。最有名的就是红黑树。

每次新插入的节点都是红的，因为插入红色节点不容易违反规则，如果插入的红色违反了规则，就对红黑树进行修正。对节点变颜色和旋转，在旋转中移动子树，重新使树平衡。

使用C++设计红黑树

使用C++的类模版，代码都写在.h文件中。

//先做两个前置声明

//定义一个红黑树类
template <class Comparable>
class RedBlackTree;

//定义一个红黑树的节点类
template <class Comparable>
class RedBlackNode;

红黑节点

1. 颜色（红色或者黑色）
2. 红黑树是二叉树，所以有左子节点指针、右子节点指针。
3. 节点保存的数据（模版类型）

template <class Comparable>
class RedBlackNode
{
    private: //为了测试，临时改成puglic
    Comparable element;
    RedBlackNode *left;
    RedBlackNode *right;
    int color;

    //节点的构造函数：
    //4个参数，对应四个成员变量
    //第一个参数是树传进来的`-99999`，保持到该节点的数据
    //左子节点（默认NULL）
    //右子节点（默认NULL）
    //颜色：默认黑色
    RedBlackNode(const Comparable & theElement = Comparable(),
                 RedBlackNode *lt = NULL,
                 RedBlackNode *rt = NULL,
                 int c = RedBlackTree<Comparable>::BLACK)
    : element(theElement),left(lt),right(rt),color(c){}//构造函数 颜色默认黑色

    //因为4个变量都是私有的，所以要把树做成节点的友元类。这样树就可以操作节点的数据成员了。
    friend class RedBlackTree<Comparable>;
};

红黑树

//类的完整定义
template <class Comparable>
class RedBlackTree
{
public:
    RedBlackTree(const Comparable & negInf);//构造函数
    ~RedBlackTree();//析构函数

    //对已经做好的红黑树增加一些操作，添加新的成员函数：
    //找指定的数
    Cref<Comparable> find(const Comparable & x) const;//找的数是x。 如果返回指针（找不到就返回空指针） 如果返回引用（找不到怎么办 C++引用必须引用对象 不能是空的，所以自己做引用类型Cref,Cref也是模版）
    Cref<Comparable> findMin() const;//查找最小的数。（最左边的叶子节点就是最小的）
    Cref<Comparable> findMax() const;//查找最大的数。（最右边的叶子节点就是最大的）

    //判断是不是空树
    bool isEmpty() const;
    //把二叉树置空，清空
    void makeEmpty() const;
    void reclaimMemory(Node *t) const;//清除节点 清空函数会用到

    enum {RED,BLACK};//节点颜色，红色，黑色。

    void insert(const Comparable & x);//插入 会创建新的节点

    typedef RedBlackNode<Comparable> Node;//节点的类型名字太长，定义一个别名Node。

//private: //为了测试，临时改成puglic
public:
    //两个重要的私有成员
    //红黑树的头header（伪根）。是一个指针，指向红黑树的头。右子是树的根。
    Node *header;//红黑树的头 -∞
    //nullNode空节点。子结点有的是空的，叶子节点的子结点也是空的，header的左子结点也是空的。
    Node *nullNode;

    //插入最重要的是平衡，平衡的时候需要几个新的指针：
    Node *current;  //指向当前节点
    Node *parent;   //指向当前节点的父节点
    Node *grand;    //指向当前节点的祖父节点
    Node *great;    //指向当前节点的曾祖父节点

    //带着左孩子 向右转
    void rotateWithLeftChild(Node * & k2) const;
    //带着右孩子 向左转
    void rotateWithRightChild(Node * & k1) const;

    ///双旋转
    //带着左孩子向右转
    void doubleRotateWithLeftChild(Node * & k3) const;
    //带着右孩子向左转
    void doubleRotateWithRightChild(Node * & k1) const;

    //通用的函数 改变颜色和旋转
    void handleReorient(const Comparable & item);//重新调整

    /// 旋转通用函数
    /// @param item 被转节点
    /// @param parent 被转的父节点
    RedBlackNode<Comparable> * rotate(const Comparable & item, Node *parent) const;
};

构造函数

对树的两个数据成员进行初始化。

空节点：其左子节点右子节点都是空的。

头header：构造函数的参数传进来的-99999，创建一个节点（伪根），这个节点的左子和右子都是空null，右指针以后指向根。

//构造函数
template <class Comparable>
RedBlackTree<Comparable>::RedBlackTree(const Comparable & negInf)
{
    //初始化
    nullNode = new Node();
    nullNode->left = nullNode->right = nullNode;//左子右子都是空的
    header = new Node(negInf);
    header->left = header->right = nullNode;
}

析构函数

构造函数中用了new，析构函数中要写上对应的delete。

//析构函数
template <class Comparable>
RedBlackTree<Comparable>::~RedBlackTree()
{
    //makeEmpty清空。makeEmpty在后面会了解。
    makeEmpty();
    //构造函数用的new 析构要delete
    delete nullNode;
    delete header;
}

Insert

insert是红黑树最重要的操作，插入数据的时候会创建节点，插入节点过程中要动态调整 保证红黑树平衡。

• 单旋转（单旋转有时候有问题，需要双旋转）
• rotateWithLeftChild() 带着左孩子转 就是向右转
• rotateWithRightChild() 带着右孩子转就是向左转

• 双旋转

• 处理有两个红色孩子的节点

• 插入节点后，处理红色的父节点

从空的红黑树插入节点，插入的节点就是根，以后继续插入insert新的节点。

插入的是模版类型，插入之后，创建节点放到红黑树里。

算法：

• 循环：

循环就是从根开始不断的向左向右查找插入的新的节点的位置。查找的时候可能会遇到一个节点的两个孩子都是红色的，需要做处理调整（单旋转或者双旋转）。

循环结束有两个情况：

1. 有相等的数据结束循环，二叉树不允许有重复的。

2. 找到最后current是nullNode（最后的子节点）。

3. 如果current不等于nullNode，则有重复的，抛出异常。

4. current等于nullNode，则找到了位置，current是空节点，那么创建current节点，把它挂在父节点上。

5. 挂在父节点，然后找位置：根据值和父节点的值大小，判断是左子还是右子。

其中父节点在循环的时候已经找到了。

template <class Comparable>
void RedBlackTree<Comparable>::insert(const Comparable &x)
{
    //开始插入的时候，current，parent，grand三个节点都等于header。
    current = parent = grand = header;
    //空指针的数据为传入的数据。把要插入的数据先放到空指针里
    nullNode->element = x;

    //找合适的位置  开始的时候current等于header 从根开始不断的向左向右找位置
    //使用循环查找新的节点插入的位置。
    while (current->element != x) {
        great = grand;
        grand = parent;
        parent = current;
        //做平衡的时候要用到上面的几个节点

        //小就找左子 大就找右子
        current = x < current->element ? current->left : current->right;

        //在循环中可能遇到一个节点的两个孩子都是红色的，需要做处理
        //变成左儿子是红色的 右儿子是黑色的
        if (current->left->color == RED && current->right->color == RED) {
            handleReorient(x);
        }
    }

    //找到了相等了 找到了重复的抛出异常
    if (current != nullNode) {
        throw DuplicateItemException();
    }
    current = new Node(x,nullNode,nullNode);
    //新节点插入
    if (x < parent->element) {
        parent->left = current;
    } else {
        parent->right = current;
    }

    //最后还要使用一下handleReorient(x)，父节点是红的，新插入的也是红的。需要再做一个处理
    handleReorient(x);//这个函数是通用的函数，改变颜色，旋转

}

自动平衡

insert有自动平衡才是红黑树，没有自动平衡则只是普通的二叉查找树。自动平衡代码是红黑树重点。

需要用到旋转：改变不同子树的深度，让所有子树深度差不多。一个平衡的二叉树，所有子树深度都要差不多。

旋转

旋转调整红黑树的高度，节点有上升和下降。

需要写两个函数实现向左转，向右转。

适应这两种情况：

1. 节点下面有子子孙孙的。
2. 节点下面没有子子孙孙的，叶子节点。

1、向右转

K2根下降，K1儿子上升，外侧孙子A上升，内侧孙子B横向移动。

如果K1下面还有子节点，子子孙孙，会跟着一起旋转。

内侧孙子子树横向移动。

k2是参数指定的，k1是k2的左子。

k2的左边就是k1的右边（横向移动）。

k1的右边就是k2。

K2 变成k1，k1替代k2的位置变成根。

k1的左边和k2的右边不变，还是原来的子节点。

代码：

//旋转 向右转
template <class Comparable>
void RedBlackTree<Comparable>::rotateWithLeftChild(Node * & k2) const
{
    Node *k1 = k2->left;//k1是k2的左子
    k2->left = k1->right;//横向移动
    k1->right = k2;//旋转之后k1的右边就是k2
    k2 = k1;//k1上升，变成了根
}

2、向左转

K2 是新定义的节点，k1是传进来的。k2是k1的右子节点。

旋转以后：

• K1的right就是原来k2的left。（横向移动）
• k2的left就等于k1。
• k2接替了k1，变成了根。

代码：

//向左转
template <class Comparable>
void RedBlackTree<Comparable>::rotateWithRightChild(Node * & k1) const
{
    Node *k2 = k1->right;
    k1->right = k2->left;//横向移动
    k2->left = k1;//旋转之后的k2的left是k1
    k1 = k2;//
}

双旋转

单旋转有时候有问题，如下图：

Q原来是k1右子树，旋转之后变成了k2的左子树，但是Q子树比较深，深度并没有发生变化。此时使用双旋转。

双旋转：旋转了以后，把深的子树给分开了，B留在左边，C去到右边，这样就比原来的深度少了。要实现这种旋转，需要旋转两次。

带着左孩子向右转：

第一次k2转到k1位置，k1右子树是B，k2左子树是k1。

第二次k2再旋转到k3根那里。

相当于两次单旋转

1. 第一次向左转：左儿子和孙子向左转。
2. 第二次向右转：当前节点和当前左儿子节点向右转

代码：

///带着左孩子向右转
template <class Comparable>
void RedBlackTree<Comparable>::doubleRotateWithLeftChild(Node * & k3) const
{
    rotateWithRightChild(k3->left);
    rotateWithLeftChild(k3);
}

带着右孩子向左转：

节点的右儿子和孙子向右转，然后节点和儿子再向左转。

template <class Comparable>
void RedBlackTree<Comparable>::doubleRotateWithRightChild(Node *&k1) const
{
    rotateWithLeftChild(k1->right);
    rotateWithRightChild(k1);
}

双旋转总结：

双旋转实际上是两个单旋转。

1. 第一次旋转：节点的儿子和孙子进行旋转，
2. 第二次旋转：节点和它新的儿子进行旋转。

双旋转和单旋转都是给insert用的。根据红黑规则，插入的时候要自动平衡，自动平衡需要用到旋转（单旋转或双旋转）和改变颜色。

改变结点颜色

下图每一个分支都是3个黑色节点。而且没有连续两个红色的节点。

• 新插入的节点红色的，因为不会破坏红黑规则。
• 如果新插16节点，应该插入20的左子，并且规定所有新插入的节点都是红色的，因为如果是黑色的，那么新插入的节点的那个路径多一个，破坏了红黑树规则。所以新插入的节点都是红色的。
• 插入节点55。和节点16一样，从根节点开始找到位置，并且是红色节点，完全符合红黑规则。
• 新插入节点是红色的，它的父节点也是红的，破坏红黑规则。这个时候需要调整：旋转（单旋转，双旋转），改变颜色
• 插入节点82，新插入的节点是红色的，但是它的父节点80也是红色的。破坏了红色规则，这时候就需要调整（旋转，改变颜色）。

insert函数节点处理情况总结：

1. 新插入的节点是红色的，如果父节点是黑色的，则直接插入。

2. 新插入的节点是红色的，如果父节点是红色的，则需要做单旋转或双旋转。

什么时候需要单旋转，什么时候需要双旋转：

• 新插入的节点X是爷爷结点G的外部孙子。那么就做一次单旋转。

• 新插入的节点X是爷爷结点G的内部孙子，那么就做双旋转。

• 如果一个节点有两个红色孩子的节点，则这个节点也需要处理。

rotate通用的旋转函数

记录旋转节点的父节点P，然后整个旋转相当于P的子树的旋转。

子树可能是P的左子，可能是P的右子。并且子树可能向左转也可能向右转。一共有四种情况：

1. 左子树向右转 -> LL
2. 左子树向左转 -> LR
3. 右子树向右转 -> RL
4. 右子树向左转 -> RR

写一个函数实现这四种旋转，并且它返回一个结果（根节点）。

第一个参数：被旋转的节点

第二个参数：父节点P

根据大小来判断：

比父节点小，则左边。否则右边。

左子树向左转：

左子树向右转：

如果比左边的小，则向右转。

rotate在内部判断大小，决定怎么转。

template <class Comparable>
/// 旋转通用函数 根据大小 自动旋转
/// @param item 被旋转节点
/// @param theParent 父节点
RedBlackNode<Comparable> * RedBlackTree<Comparable>::rotate(const Comparable &item, Node *theParent) const
{
    //分四种情况
    //根据大小判断，红黑树是二叉树
    //左子向左转 向右转
    //左子树
    if (item < theParent->element) {
        //向左转向右转 根据大小判断
        //比左边的小 向右转。
        item < theParent->left->element ? 
        rotateWithLeftChild(theParent->left) :
        rotateWithRightChild(theParent->left);
        return theParent->left;
    }
    //右子树
    else {
        item < theParent->right->element ?
        rotateWithLeftChild(theParent->right) :
        rotateWithRightChild(theParent->right);
        return theParent->right;
    }
}

handleReorient调整函数

改变颜色，单旋转或者双旋转。

首先变色

新插入的是红色的。

insert的while循环中找到节点的两个子节点红的，那么需要变色，current是insert两个子节点是红色的需要变色的节点。

///这个函数在insert函数调了两次
template <class Comparable>
void RedBlackTree<Comparable>::handleReorient(const Comparable &item)
{
    //1. 变色
    current->color = RED;//变红色 遇到节点有两个红色的孩子 则节点要变色
    //左右两个孩子变黑色
    current->left->color = BLACK;
    current->right->color = BLACK;

    //2. 旋转
    //如果父节点是红色的 需要旋转。因为新插入的也是红的。
    if (parent->color == RED) {
        //2.1 先把爷爷节点的颜色变成红色
        grand->color = RED;
        //2.2 然后判断新插入的节点是 内部孙子 外部孙子
        //内部孙子：小于爷爷 大于爸爸 或者 大于爷爷 小于爸爸。
        //内部孙子不会同时比爷爷和爸爸小 不会比爷爷和爸爸同时大
        if (item < grand->element != item < parent->element) {//不会同时大 同时小
            //2.2.1如果是内部孙子，加多一次旋转 双旋转
            parent = rotate(item, grand);
        }
        //2.2.2外部孙子 只做一次旋转
        current = rotate(item, great);

        //旋转之后，把当前节点变成黑的。因为父节点是红的。
        current->color = BLACK;

        //如果一个节点比爷爷小 比爸爸小 则是左外部孙子
        //如果一个节点比爷爷大 比爸爸大 则是右外部孙子
    }

    //最后把根节点变黑的。根节点必须是黑的
    header->right->color = BLACK;
}

这个函数在insert的时候调用了两次。

isEmpty

判断二叉树是不是空树

template <class Comparable>
bool RedBlackTree<Comparable>::isEmpty() const
{
    //是否是空的红黑树 判断伪根header右子节点（真正的根）是不是空节点
    return header->right == nullNode;
    //创建的时候就是nullNode 如果等于nullNode就是空的
}

makeEmpty

清空。所有节点清空之后，header的右子要置为空。

//清空
template <class Comparable>
void RedBlackTree<Comparable>::makeEmpty() const
{
    //红黑树里所有的节点删除 节点是insert函数里new创建出来的 按照C++要求就需要delete删除
    //delete删除所有的节点 节点数可能多可能少
    //使用reclaimMemory函数从根节点开始清除
    reclaimMemory(header->right);
    header->right = nullNode;
}

私有函数：

makeEmpty中要用，清除节点。

把红黑树所有节点全部删除，节点都是insert中new创建出来的。

把节点全部清除。使用delete。

函数做成通用函数，全部节点如论多少，全部delete。

定义一个函数从根开始清除。从根开始全部清除。

reclaimMemory里面是递归：

左子节点清除，右子节点清除。不断的递归。就可以把所有的清除。

递归必须要有停止条件：如果t== t->left则停止，right也一样。

到了叶子节点停止递归。

template <class Comparable>
void RedBlackTree<Comparable>::reclaimMemory(Node *t) const//参数t是节点
{
    //使用递归设计 所有的子子孙孙清除
    if (t != t->left) {//到叶子节点t == t->left或者t == t->right 停止递归。因为叶子结点的子结点是空的，子结点和子结点也是空的，所以如果都是空的则停止递归。
        reclaimMemory(t->left);//左子节点清除
        reclaimMemory(t->right);//右子节点清除
        delete t;//清除
    }
}

查找

返回指针还是引用：

找到了可以返回引用，找不到的话 引用不能返回空的。返回指针可以返回空指针。

自己做一个引用类型Cref。Cref也是一个类模版。它可以是一个空引用。不是C++语言的引用，C++语言不允许引用为空。

创建一个单独的文件Warpper.h包装类，去定义Cref类。

Cref类内部其实还是指针。只是把指针包装了成了引用。

显式的构造函数 初始化指针。没有参数的构造函数就是传NULL。

把指针包装成了一个类，使用这个类的引用。

//自定义引用类型
template <class Object>
class Cref
{
public:
    //没有参数的构造函数
    Cref() : obj(NULL) {}//指针传NULL
    //显示的构造函数
    explicit Cref(const Object & x) : obj(&x) {} //初始化

    //通过引用操作数据
    const Object & get() const
    {
        if (isNull()) {
            throw NullPointerException(); //如果引用是空的，则抛出一个异常
        } else {
            return *obj;//如果引用不是空的，则返回数据
        }
    }

    //成员函数
    //判断引用是不是空的 如果指针是空的 则引用是空的
    bool isNull() const
    {
        return obj == NULL;
    }

private:
    const Object *obj;//指针
};

findMin

查找红黑树中最小的数

如果树是空的，则返回一个空引用。

如果不是空的，则从根开始，一直向左查找。然后用引用返回找到的数据。

//查找最小的
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::findMin() const
{
    //红黑树是不是空的。是空的就返回空引用
    if (isEmpty()) {
        return Cref<Comparable>();
    }
    //不是空的就从根节点一直向左最找最小的，找到最后的时候 左右子都是nullNode
    Node *itr = header->right;
    while (itr->left != nullNode) {
        itr = itr->left;
    }
    return Cref<Comparable>(itr->element);
}

findMax

查找最大的，查找最大的和查找最小的算法一样，只是查找的方向不一样。

找最大的是向右找。

//查找最大的 向右
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::findMax() const
{
    //红黑树是不是空的。是空的就返回空引用
    if (isEmpty()) {
        return Cref<Comparable>();
    }
    //不是空的就从根节点开始一直向右找右子节点最大的，找到最后的时候 左右子都是nullNode
    Node *itr = header->right;
    while (itr->right != nullNode) {
        itr = itr->right;
    }
    return Cref<Comparable>(itr->element);
}

find

找指定的一个数，从根开始，根据大小一直向左向右查找。

红黑树是一个二叉查找树，所以是一个典型的二叉查找算法。

二叉树的很多算法都可以在红黑树中使用。先序遍历，中序遍历，后序遍历等。

要找的是一个数。使用一个节点保存这个数。

创建一个当前的节点，从根节点开始，根据要找的数和当前节点的数的大小比较判断向左向右的找。

当前节点一直向左向右。如果当前节点不等于nullNode，则找到了，返回。否则就是没找到，返回一个空引用。

//查找指定的数
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::find(const Comparable &x) const
{
    //要找的数是x
    nullNode->element = x;
    Node *curr = header->right;//节点指针 从根节点开始
    for (; ;) {
        if (x < curr->element) {
            curr = curr->left;
        } else if (x > curr->element) {
            curr = curr->right;
        } else if (curr != nullNode) {
            //找到了
            return Cref<Comparable>(curr->element);
        } else {
            //没找到 返回空引用
            return Cref<Comparable>();
        }
    }
}

自定义异常类

#pragma mark - 异常类
class DSException
{
public:
    //构造函数
    DSException(const string & msg = "") : message(msg){}
    //析构函数
    virtual ~DSException(){}
    virtual string toString() const
    {
        return "Exception " + string(": ") + what();
    }
    virtual string what() const
    {
        return message;
    }
private:
    string message;
};

//重复异常
class DuplicateItemException : public DSException
{
public:
    DuplicateItemException(const string & msg = "") : DSException(msg){}
};
//空异常
class NullPointerException : public DSException
{
public:
    //构造函数 参数是字符串
    NullPointerException(const string & msg = "") : DSException(msg) {}
};

调用测试

//测试
void test()
{
    const int NEG_INF = -99999;
    RedBlackTree<int> t(NEG_INF);//很大的负数，一个节点都没有 是空的。一个特殊的节点。伪根。
    t.insert(50);
    t.insert(40);
    t.insert(30); //如果这里不是红黑树 就退化成链表的。
    //动态调整 红黑树根动态变化 保证根的左子树右子树深度基本一致 红色节点数一致
    //如果是普通的二叉查找树 根是50 不变
    //红黑树会自动调整平衡

    //根
    cout << t.header->right->element << endl;

    //是不是空的
    if (!t.isEmpty()) {
        cout << "红黑树不是空的" << endl;
    }

    //清空
    t.makeEmpty();
    if (t.isEmpty()) {
        cout << "红黑树是空的" << endl;
    }

    //查找
    Cref<int> r = t.find(66);
    if (r.isNull()) {
        cout << "没找到";
    } else {
        cout << "找到：" << r.get() << endl;
    }

    t.insert(200);
    t.insert(100);
    t.insert(90);
    t.insert(50);
    t.insert(80);
    t.insert(70);
    t.insert(60);

    if (t.findMin().get() == 50) {
        cout << "找到了最小的数" << endl;
    }
    cout << "最大的：" << t.findMax().get() << endl;

//    cout << t.header->right->element << endl;
//    cout << t.header->right->right->left->element << endl;
//
//    //向左转
//    t.rotateWithRightChild(t.header->right);
}

现在做的只是红黑树基本的函数，最重要的是insert。

还可以给做好的红黑树增加更多算法（如：遍历函数），加到类里。

总结

红黑树的根会动态的变化。因为要保证根左右子树的深度基本一致。

重点在插入的时候做了两次平衡调整。

旋转的时候外侧的会上升，内侧的是平移。所以内侧的深度高时就需要双旋转。

红黑树的使用

在C++标准库容器（STL）中的map 、multimap、set、 multiset等内部的数据结构都是红黑树。

#include <set>
#include <map>
using namespace std;//要导入名称空间 因为这几个都在std名称空间里

//测试
void test()
{
    //这些都是红黑树
    //C++标准库容器
    set<int>                    a;
    multiset<int>               b;
    map<int, int>               c;
    multimap<int, int>          d;

    a.insert(50);
    a.insert(40);
    a.insert(30);

}

红黑树之所以被广泛使用，是因为它能保证在插入、删除和查找操作中的时间复杂度为 O(log n)，使得性能表现稳定。