构建红黑树--C++版_红黑树的构建

根据《普林斯顿算法》实现了红黑树的C++版本

红黑树的树形修整基于三个基本操作，即左旋，右旋和镜像

左旋示意图：

右旋示意图

镜像示意图：

树形结构调整示意图

C++ 版 code:

//红黑树
enum Color
{
    RED,
    BLACK
};
struct RBNode
{
    int key;
    int value;
    RBNode *pleft;
    RBNode *pright;
    int count;
    Color color;
};
RBNode *rotateLeft(RBNode *node)
{
    RBNode* temp = node->pright;
    node->pright = temp->pleft;
    temp->pleft = node;
    node->color = RED;
    return temp;
}

RBNode *rotateRight(RBNode *node)
{
    RBNode *temp = node->pleft;
    node->pleft = temp->pright;
    temp->pright = node;
    node->color = RED;
    return temp;
}

RBNode *flip(RBNode *node)
{
    node->color = RED;
    node->pleft->color = BLACK;
    node->pright->color = BLACK;
}

//构建红黑树
int rbSize(RBNode *node)
{
    if (node == nullptr)
        return 0;
    else
    {
        return node->count;
    }
}
RBNode *put(RBNode* node, int key, int value)
{
    if (node == nullptr)
        return new RBNode({ key, value, nullptr, nullptr, RED });

    if (key < node->key)
        node->pleft = put(node->pleft, key, value);
    else if (key > node->key)
        node->pright = put(node->pright, key, value);
    else if (key == node->key)
        node->value = value;
    node->count = 1 + rbSize(node->pleft) + rbSize(node->pright);

    //开始调整树的结构 左旋，右旋，flip
    if (node->pleft->color == BLACK && node->pright->color == RED)
        rotateLeft(node);
    if (node->pleft->color == RED && node->pleft->pleft->color == RED)
        rotateRight(node);
    if (node->pleft->color == RED && node->pright->color == RED)
        flip(node);
    return node;
    
}