---

1.红黑树的概念

• 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black
• 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的
  

---

2.红黑树的性质

• 每个结点不是红色就是黑色
• 根节点是黑色的
• 如果一个节点是红色的，则它的两个孩子结点是黑色的 --> 树中没有连续的红色节点
• 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 --> 每条路径的黑色节点数量相等
• 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
• 为什么满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点 个数的两倍？
  • 极限最短：全黑
  • 极限最长：一黑一红

---

3.红黑树节点的定义

enum Colour
{
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;

    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv, Colour colour = RED)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(colour)
    {}
};

---

4.红黑树的结构

• 为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色
• 并且让头结点的_parent域指向红黑树的根节点，_left域指向红黑树中最小的节点，_right域指向红黑树中最大的节点
• 但是我的实现中，并没有使用头节点
  

---

5.红黑树的插入操作

• 红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
  • 按照二叉搜索的树规则插入新节点
  • 检测新节点插入后，红黑树的性质是否造到破坏
    • 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整
    • 但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论： 约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
• 注意：此处所看到的树，可能是一颗完整的树，也可能是一颗子树
• 红黑树的关键是叔叔 --> 遇事不决看叔叔
• cur为红，p为红，g为黑是固定的

1.cur为红，p为红，g为黑，u存在且为红

• 如果g是根节点，调整完成后，需要将g改为黑色
• 如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整

• 解决方式：
  • 将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

2.cur为红，p为红，g为黑，u不存在/u存在且为黑 – 单旋+变色

• u的情况有两种
  • 如果u节点不存在
    • 则cur一定是新插入节点
    • 因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同
  • 如果u节点存在，且为黑
    • 则cur节点原来的颜色一定是黑色的
    • 现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色
• 解决方式：
  • p为g的左孩子，cur为p的左孩子，则进行右单旋转
  • p为g的右孩子，cur为p的右孩子，则进行左单旋转
  • p变黑色，g变红色

3.cur为红，p为红，g为黑，u不存在/u存在且为黑 – 双旋+变色

• 解决方式：
  • p为g的左孩子，cur为p的右孩子，则针对p做左单旋转
  • p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
  • 转换成情况二
  • 再以g为轴点进行右单旋/左单旋

bool Insert(const pair<K, V> &kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node *parent = nullptr;
    Node *cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;

    // 处理颜色
    while (parent && parent->_col == RED)
    {
        Node *grandparent = parent->_parent;
        assert(grandparent);
        assert(grandparent->_col == BLACK);

        // 关键看叔叔
        if (grandparent->_left == parent)
        {
            Node *uncle = grandparent->_right;
            if (uncle && uncle->_col == RED)
            {
                // 1.uncle存在且为红
                parent->_col = uncle->_col = BLACK;
                grandparent->_col = RED;

                // 继续往上处理
                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
                // 2.uncle不存在/存在且为黑
                if (parent->_left == cur) // 情况二：右单旋 + 变色
                {
                    RotateR(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else // 情况三：左右双旋 + 变色
                {
                    RotateL(parent);
                    RotateR(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }

                break;
            }
        }
        else // grandparent->_right == parent
        {
            Node *uncle = grandparent->_left;
            if (uncle && uncle->_col == RED)
            {
                // 1.uncle存在且为红
                parent->_col = uncle->_col = BLACK;
                grandparent->_col = RED;

                // 继续往上处理
                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
                // 2.uncle不存在/存在且为黑
                if (parent->_right == cur) // 情况二：左单旋 + 变色
                {
                    RotateL(grandparent);

                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else // 情况三：右左双旋 + 变色
                {
                    RotateR(parent);
                    RotateL(grandparent);

                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }

                break;
            }
        }
    }

    _root->_col = BLACK; // 防止一直到根且根节点为红色
    return true;
}

void RotateL(Node *parent)
{
    Node *subR = parent->_right;
    Node *subRL = subR->_left;

    parent->_right = subRL;
    if (subRL) // 防止subRL本来就为空，对空指针访问
    {
        subRL->_parent = parent;
    }

    // 用于判断原来的parent是否是子树
    Node *grandParent = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

    if (_root == parent)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (grandParent->_left == parent)
        {
            grandParent->_left = subR;
        }
        else
        {
            grandParent->_right = subR;
        }
        subR->_parent = grandParent;
    }
}

void RotateR(Node *parent)
{
    Node *subL = parent->_left;
    Node *subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
    {
        subLR->_parent = parent;
    }

    Node *grandParent = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (_root == parent)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (grandParent->_left == parent)
        {
            grandParent->_left = subL;
        }
        else
        {
            grandParent->_right = subL;
        }

        subL->_parent = grandParent;
    }
}

---

6.红黑树的迭代器

1.begin()与end()

• STL明确规定
  • begin()与end()代表的是一段前闭后开的区间
  • 而对红黑树进行中序遍历后， 可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位 置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？ 能否给成nullptr呢？
    • 答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置
      

typedef __RBTree_Iterator<T, T &, T *> iterator;

iterator begin()
{
    Node *left = _root;
    while (left && left->_left) // left --> 防止空树
    {
        left = left->_left;
    }

    return iterator(left); // 匿名结构体
}

iterator end()
{
    return iterator(nullptr); // 非带头节点版本
}

2.operator++

• 右子树不为空 --> ++就是找右子树的最左节点
• 右子树为空 --> ++找现孩子不是父亲右 的那个祖先

3.operator–

• 左子树不为空 --> --就是找左子树的最右节点
• 左子树为空 --> --找现孩子不是父亲左 的那个祖先

template <class T, class Ref, class Ptr>
struct __RBTree_Iterator
{
    typedef RBTreeNode<T> Node;
    typedef __RBTree_Iterator<T, Ref, Ptr> Self;
    Node *_node;

    __RBTree_Iterator(Node *node)
        : _node(node)
    {}

    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &(operator*());
    }

    bool operator!=(const Self &s) const
    {
        return _node != s._node;
    }

    bool operator==(const Self &s) const
    {
        return _node == s._node;
    }

    Self& operator++()
    {
        if (_node->_right)
        {
            // 下一个就是右子树的最左节点
            Node *left = _node->_right;
            while (left->_left)
            {
                left = left->_left;
            }

            _node = left;
        }
        else
        {
            // 找祖先里面 孩子不是父亲的右 的那个祖先
            Node *parent = _node->_parent;
            Node *cur = _node;

            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = parent->_parent;
            }

            _node = parent;
        }

        return *this;
    }

    Self operator--()
    {
        if (_node->_left)
        {
            // 下一个节点是左子树的最右节点
            Node *right = _node->_left;
            while (right->_right)
            {
                right = right->_right;
            }

            _node = right;
        }
        else
        {
            // 找祖先里面 孩子不是父亲的左 的那个祖先
            Node *parent = _node->_parent;
            Node *cur = _node;

            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = parent->_parent;
            }

            _node = parent;
        }
    }
};

---

7.红黑树的验证

• 红黑树的检测分为两步：
  • 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  • 检测其是否满足红黑树的性质

bool IsBalance()
{
    if (_root == nullptr)
    {
        return true;
    }

    if (_root->_col == RED)
    {
        cout << "根节点不是黑色" << endl;
        return false;
    }

    // 获取黑色节点数量基准值  -->  每一条路黑色节点数量相同
    Node *cur = _root;
    int benchmark = 0;
    while (cur)
    {
        if (cur->_col == BLACK)
        {
            ++benchmark;
        }
        cur = cur->_left;
    }

    return PreCheck(_root, 0, benchmark);
}

bool PreCheck(Node *root, int blackNum, int &benchmark)
{
    if (root == nullptr)
    {
        if (blackNum != benchmark)
        {
            cout << "某条黑色节点的数量不相等" << endl;
            return false;
        }
        else
        {
            return true;
        }
    }

    if (root->_col == BLACK)
    {
        ++blackNum;
    }

    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续的红色节点" << endl;
    }

    return PreCheck(root->_left, blackNum, benchmark) && PreCheck(root->_right, blackNum, benchmark);
}

---

8.红黑树与AVL树的比较

• 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)
• 红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数
• 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多