跳转至

红黑树

一、红黑树

（一）红黑树的概念

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

（二） 红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

问：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？

答：

最短路径：全部为黑色的

最长路径：一黑一红

所以满足最短路径恰好等于最长路径的二倍。

（三）红黑树节点的定义

首先我们定义一个枚举类型，来区分红色和黑色

enum color {
    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;
    color _col;
    RBTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_kv(kv)
        ,_col(RED)
    {}
};

二、红黑树的插入

首先找到cur该插入的位置，这里和AVL树的插入是一样的，唯一不一样的就是以前是平衡因子改变，变成了颜色改变，所以就不再介绍。代码如下：

template<class K, class V> 
struct RBTree {
public:
    typedef RBTreeNode<K, V> Node;
    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->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->right;
            }
            else
                return false;
        }
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;      
    }
private:
    Node* _root;
};

正式进入插入环节：

插入新节点的颜色：红色

1.插入位置父亲的颜色是黑色，不需要处理，插入结束

2.插入位置的父亲颜色是红色，出现了连续的红色节点，需要处理

这里定义爷爷(g)的另外一个结点为叔叔节点，简称uncle/u

情况一：u存在且为红

p/u变黑、g变红（如果g是root，再把g变成黑）=> c变成g，p变成c的父亲（传递上去）

注：

p/u是g的左右都不影响

cur是p的左右也不影响

由于根节点永远是黑色，所以我们在外面定义一下_root->_col = BLACK

代码如下：

while (parent && parent->_col == RED) {
    Node* grandfather = parent->_parent;
    if (parent == grandfather->_left) {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED) {
            // 情况一：uncle存在且为红
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather;
            parent = cur->_parent;
        }
        else {
            //情况二：u不存在或者u为黑
        }
    }
    else {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED) {
            // 情况一：uncle存在且为红
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather;
            parent = cur->_parent;
        }
        else {
            //情况二：u不存在或者u为黑

        }
    }
}
        _root->_col = BLACK;

情况二: uncle不存在，或者uncle为黑的情况下，需要旋转+变色(关键在于画图)，旋转代码和AVL树一样不再讲解。

while (parent && parent->_col == RED) {
    Node* grandfather = parent->_parent;
    if (parent == grandfather->_left) {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED) {
            // 情况一：uncle存在且为红
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather;
            parent = cur->_parent;
        }
        else {
            //情况二：u不存在或者u为黑
            if (parent->_left == cur) {
                //     g
                //   p   u
                // c
                RotateR(grandfather);
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else {
                //   g
                // p   u
                //   c
                RotateL(parent);
                RotateR(grandfather);
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            break;
        }
    }
    else {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED) {
            // 情况一：uncle存在且为红
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather;
            parent = cur->_parent;
        }
        else {
            //情况二：u不存在或者u为黑
            if (parent->_right == cur) {
                //   g
                // u   p
                //       c
                RotateL(grandfather);
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else {
                //   g
                // u   p
                //   c
                RotateR(parent);
                RotateL(grandfather);
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            break;
        }
    }
}
_root->_col = BLACK;

三、红黑树的平衡验证

bool Check(Node* root, int BlackNum, int RefBlackNum) {
    if (root == nullptr) {
        if (BlackNum != RefBlackNum) {
            cout << "黑色个数不相等" << endl;
            return false;
        }
        return true;
    }

    if (root->_col == BLACK)
        BlackNum++;

    if (root->_col == RED && root->_parent->_col == RED) {
        cout << "出现连续红色节点" << endl;
        return false;
    }

    return Check(root->_left, BlackNum, RefBlackNum)
        && Check(root->_right, BlackNum, RefBlackNum);
}

bool IsBalance() {
    if (_root && _root->_col == RED)
        return false;
    int RefBlackNum = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == BLACK)
            RefBlackNum++;
        cur = cur->_left;
    }
    return Check(_root, 0, RefBlackNum);
}

四、代码汇总

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
enum color {
    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;
    color _col;
    RBTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_kv(kv)
        ,_col(RED)
    {}
};

template<class K, class V> 
struct RBTree {
public:
    typedef RBTreeNode<K, V> Node;
    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->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            }
            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* grandfather = parent->_parent;
            if (parent == grandfather->_left) {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED) {
                    // 情况一：uncle存在且为红
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else {
                    //情况二：u不存在或者u为黑
                    if (parent->_left == cur) {
                        //     g
                        //   p   u
                        // c
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else {
                        //   g
                        // p   u
                        //   c
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED) {
                    // 情况一：uncle存在且为红
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else {
                    //情况二：u不存在或者u为黑
                    if (parent->_right == cur) {
                        //   g
                        // u   p
                        //       c
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else {
                        //   g
                        // u   p
                        //   c
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_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->_parent = parent;

        subR->_left = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = subR;

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

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

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

        subL->_right = parent;

        Node* ppnode = parent->_parent;
        parent->_parent = subL;

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

    bool Check(Node* root, int BlackNum, int RefBlackNum) {
        if (root == nullptr) {
            if (BlackNum != RefBlackNum) {
                cout << "黑色个数不相等" << endl;
                return false;
            }
            return true;
        }

        if (root->_col == BLACK)
            BlackNum++;

        if (root->_col == RED && root->_parent->_col == RED) {
            cout << "出现连续红色节点" << endl;
            return false;
        }

        return Check(root->_left, BlackNum, RefBlackNum)
            && Check(root->_right, BlackNum, RefBlackNum);
    }

    bool IsBalance() {
        if (_root && _root->_col == RED)
            return false;
        int RefBlackNum = 0;
        Node* cur = _root;
        while (cur) {
            if (cur->_col == BLACK)
                RefBlackNum++;
            cur = cur->_left;
        }
        return Check(_root, 0, RefBlackNum);
    }

private:
    Node* _root = nullptr;
};

void TestRBTree()
{
    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);
    }
    RBTree<int, int> t;
    for (auto e : v)
    {
        t.Insert(make_pair(e, e));
    }
    cout << t.IsBalance() << endl;
}