一篇文章带你了解红黑树并将其模拟实现（上）

struct Node {
    int data;
    Color color;
    Node* left;
    Node* right;
    Node* parent;
};
class RedBlackTree {
private:
    Node* root; // 实际的根节点
    Node* header; // 头结点
    // ...其他成员函数和辅助函数...
public:
    RedBlackTree() : root(nullptr), header(new Node) {
        header->color = BLACK;
        header->left = nullptr;
        header->right = nullptr;
        header->parent = nullptr;
    }
    // ...其他公共成员函数...
};

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)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};
template<class K, class V>
struct RBTree
{
  typedef RBTreeNode<K,V> Node;
private:
  Node* _root = nullptr;
};

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);
    cur->_col = RED;//新插入节点即为红节点,不懂结合性质和我下面的讲解
    if (parent->_kv.first < kv.first)//同搜索树规则先直接插入
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;//更新新插入节点的父指针
    while (parent && parent->_col == RED)
    {
        Node* grandfater = parent->_parent;
        assert(grandfater);
        assert(grandfater->_col == BLACK);
        if (parent == grandfater->_left)//具体看下面讲解
        {
            Node* uncle = grandfater->_right;
            // 情况一 : uncle存在且为红，变色+继续往上处理
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfater->_col = RED;
                // 继续往上处理
                cur = grandfater;
                parent = cur->_parent;
            }// 情况二+三：uncle不存在 + 存在且为黑
            else
            {
                // 情况二：右单旋+变色
                if (cur == parent->_left)
                {
                    RotateR(grandfater);
                    parent->_col = BLACK;
                    grandfater->_col = RED;
                }
                else
                {
                    // 情况三：左右单旋+变色
                    RotateL(parent);
                    RotateR(grandfater);
                    cur->_col = BLACK;
                    grandfater->_col = RED;
                }
                break;
            }
        }
        else // (parent == grandfater->_right)
        {
            Node* uncle = grandfater->_left;
            // 情况一
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfater->_col = RED;
                // 继续往上处理
                cur = grandfater;
                parent = cur->_parent;
            }
            else
            {
                // 情况二：左单旋+变色
                if (cur == parent->_right)
                {
                    RotateL(grandfater);
                    parent->_col = BLACK;
                    grandfater->_col = RED;
                }
                else
                {
                    // 情况三：右左单旋+变色
                    RotateR(parent);
                    RotateL(grandfater);
                    cur->_col = BLACK;
                    grandfater->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}