C++实现红黑树应用实例代码

什么是红黑树

红黑树（Red-Black Tree）是一种自平衡二叉查找树，在C++中的STL中的set和map就是基于红黑树实现的。红黑树满足以下性质：

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点，空节点）是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对于任意一个节点而言，其到叶子节点NIL的任何路径上包含的黑色节点个数相同。

通过以上性质，可以保证红黑树的树高不超过 $2log_2n$ ，其中 $n$ 为节点个数。

C++代码实现

结构体定义

首先我们定义红黑树的节点结构体：

enum Color{ RED, BLACK };

template <class T>
struct RBTreeNode
{
    Color color;
    T key;
    RBTreeNode<T>* parent;
    RBTreeNode<T>* left;
    RBTreeNode<T>* right;

    RBTreeNode(T data, Color c = Color::RED, RBTreeNode<T>* p = nullptr,
        RBTreeNode<T>* l = nullptr, RBTreeNode<T>* r = nullptr) :
        key(data), color(c), parent(p), left(l), right(r) {}
};

我们使用枚举类型 Color 来代表节点颜色，节点中包含了当前节点的颜色、关键字信息、父节点指针、左子树指针和右子树指针。

插入节点

插入节点的过程中，我们需要通过比较关键字大小判断插入的位置。插入完成后，红黑树可能会不满足黑色节点数目相同的性质，因此我们需要对红黑树进行一系列转换，保证性质得以满足。

template <class T>
void RBTree<T>::insert(RBTreeNode<T>* node)
{
    RBTreeNode<T>* ptrNode = root;
    RBTreeNode<T>* parentNode = nullptr;

    while (ptrNode != nullptr)
    {
        parentNode = ptrNode;

        if (node->key < ptrNode->key)
        {
            ptrNode = ptrNode->left;
        }
        else
        {
            ptrNode = ptrNode->right;
        }
    }

    node->parent = parentNode;

    if (parentNode == nullptr)
    {
        root = node;
    }
    else if (node->key < parentNode->key)
    {
        parentNode->left = node;
    }
    else
    {
        parentNode->right = node;
    }

    node->color = Color::RED;

    fixupInsert(node);
}

插入修复

为了修正插入节点引起的变化，我们需要进行一些修复操作：

template <class T>
void RBTree<T>::fixupInsert(RBTreeNode<T>* node)
{
    RBTreeNode<T>* parentNode = nullptr;
    RBTreeNode<T>* grandNode = nullptr;

    while (node->parent != nullptr && node->parent->color == Color::RED)
    {
        parentNode = node->parent;
        grandNode = parentNode->parent;

        if (parentNode == grandNode->left)
        {
            RBTreeNode<T>* nodeUncle = grandNode->right;

            // 情况1
            if (nodeUncle != nullptr && nodeUncle->color == Color::RED)
            {
                parentNode->color = Color::BLACK;
                nodeUncle->color = Color::BLACK;
                grandNode->color = Color::RED;

                node = grandNode;
            }
            else
            {
                // 情况2
                if (node == parentNode->right)
                {
                    leftRotate(parentNode);
                    std::swap(node, parentNode);
                }

                // 情况3
                parentNode->color = Color::BLACK;
                grandNode->color = Color::RED;

                rightRotate(grandNode);
            }
        }
        else
        {
            RBTreeNode<T>* nodeUncle = grandNode->left;

            // 情况1
            if (nodeUncle != nullptr && nodeUncle->color == Color::RED)
            {
                parentNode->color = Color::BLACK;
                nodeUncle->color = Color::BLACK;
                grandNode->color = Color::RED;

                node = grandNode;
            }
            else
            {
                // 情况2
                if (node == parentNode->left)
                {
                    rightRotate(parentNode);
                    std::swap(node, parentNode);
                }

                // 情况3
                parentNode->color = Color::BLACK;
                grandNode->color = Color::RED;

                leftRotate(grandNode);
            }
        }
    }

    root->color = Color::BLACK;
}

左旋和右旋

左旋和右旋是红黑树的基本操作：

template <class T>
void RBTree<T>::leftRotate(RBTreeNode<T>* node)
{
    RBTreeNode<T>* rightChild = node->right;

    node->right = rightChild->left;

    if (rightChild->left != nullptr)
    {
        rightChild->left->parent = node;
    }

    rightChild->parent = node->parent;

    if (node->parent == nullptr)
    {
        root = rightChild;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = rightChild;
    }
    else
    {
        node->parent->right = rightChild;
    }

    rightChild->left = node;
    node->parent = rightChild;
}

template <class T>
void RBTree<T>::rightRotate(RBTreeNode<T>* node)
{
    RBTreeNode<T>* leftChild = node->left;

    node->left = leftChild->right;

    if (leftChild->right != nullptr)
    {
        leftChild->right->parent = node;
    }

    leftChild->parent = node->parent;

    if (node->parent == nullptr)
    {
        root = leftChild;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = leftChild;
    }
    else
    {
        node->parent->right = leftChild;
    }

    leftChild->right = node;
    node->parent = leftChild;
}

示例

示例一：插入节点

以插入关键字为7的节点为例，我们先构造红黑树：

            (11B)
          /      \
        (2B)     (14R)
       /    \       \
    (1R)   (7R)     (15R)

插入关键字为7的节点，红色节点：

            (11B)
          /      \
        (2B)     (14R)
       /    \       \
    (1R)   (7R)     (15R)
              \
              (7R)

插入完成后修复红黑树，得到：

            (11B)
          /      \
        (2B)     (14B)
       /    \       \
    (1R)   (7B)     (15R)
              \
              (7R)

示例二：删除节点

以删除关键字为11的节点为例，我们先构造红黑树：

            (11B)
          /      \
        (2B)     (14R)
       /    \       \
    (1R)   (7R)     (15R)

删除关键字为11的节点，得到：

            (14R)
          /      \
        (2B)     (15B)
       /    \
    (1R)   (7R)

删除完成后我们需要对红黑树进行一系列修复操作，最终得到：

            (2B)
          /      \
        (1R)     (14B)
                /    \
              (7R)   (15R)