红黑树 | 而我独缺 你一生的了解
Cobb 561 1

看的时候把这个调整到数据结构中

/*
红黑树颜色定义
*/
enum Color
{
    BLACK, RED
};

/*
红黑树节点类型定义
*/
template<typename T>
class RBNode
{
public:
    RBNode(T data = T(), Color color = Color::BLACK, RBNode<T> *parent = NULL)
        : mdata(data)
        , mcolor(color)
        , mleft(NULL)
        , mright(NULL)
        , mparent(parent){}
    T mdata;
    Color mcolor;
    RBNode<T> *mleft;
    RBNode<T> *mright;
    RBNode<T> *mparent; // 红黑树需要存储父节点的指针
};

/*
红黑树实现
*/
template<typename T>
class RBTree
{
public:
    RBTree() :mroot(NULL){}
    ~RBTree(){}

    // 红黑树插入操作
    void insert(const T &val)
    {
        if (mroot == NULL)
        {
            mroot = new RBNode<T>(val, Color::BLACK, NULL);
            return;
        }

        RBNode<T> *parent = mroot;
        RBNode<T> *pcur = mroot;
        while (pcur != NULL)
        {
            parent = pcur;
            if (val < pcur->mdata)
            {
                pcur = pcur->mleft;
            }
            else if (val > pcur->mdata)
            {
                pcur = pcur->mright;
            }
            else
            {
                return; 
            }
        }

        // 红黑树新插入的节点都是红色的
        RBNode<T> *p = new RBNode<T>(val, Color::RED, parent);
        if (val < parent->mdata)
        {
            parent->mleft = p;
        }
        else
        {
            parent->mright = p;
        }

        // 检查并调整红黑树的是否满足条件
        fixAfterInsert(p);
    }

    // 红黑树的删除操作
    void remove(const T &val)
    {
        RBNode<T> *pcur = mroot;
        while (pcur != NULL)
        {
            if (val < pcur->mdata)
            {
                pcur = pcur->mleft;
            }
            else if (val > pcur->mdata)
            {
                pcur = pcur->mright;
            }
            else
            {
                break;
            }
        }

        // 没找到待删除的元素
        if (pcur == NULL)
        {
            return;
        }

        // 待删除节点有两个孩子节点,用后继节点来代替当前节点,然后删除后继节点
        if (pcur->mleft != NULL && pcur->mright != NULL)
        {
            RBNode<T> *pDel = pcur->mright;
            while (pDel->mleft != NULL)
            {
                pDel = pDel->mleft;
            }
            pcur->mdata = pDel->mdata;
            pcur = pDel;  // 删除后继节点
        }

        // 记录待删除节点的孩子节点
        RBNode<T> *pchild = NULL;
        if (pcur->mleft != NULL)
        {
            pchild = pcur->mleft;
        }
        else
        {
            pchild = pcur->mright;
        }

        // 待删除节点有孩子
        if (pchild != NULL)
        {
            pchild->mparent = pcur->mparent;
            if (pcur->mparent == NULL)
            {
                mroot = pchild;
            }
            else
            {
                if (pcur == pcur->mparent->mleft)  // 此处比较地址就可以了,不用比较数据的值是否相等
                {
                    pcur->mparent->mleft = pchild;
                }
                else
                {
                    pcur->mparent->mright = pchild;
                }
            }

            // 如果删除的节点是黑色节点,需要进行调整操作
            if (pcur->mcolor == Color::BLACK)
            {
                fixAfterDelete(pchild);
            }
        }
        else 
        {
            // RBTree只剩一个根节点,删除
            if (pcur->mparent == NULL)
            {
                mroot = NULL;
            }
            else
            {
                // 如果删除的节点是黑色节点,需要进行调整操作
                if (pcur->mcolor == Color::BLACK)
                {
                    fixAfterDelete(pcur);
                }

                if (pcur->mparent != NULL)
                {
                    if (pcur->mparent->mleft == pcur)
                    {
                        pcur->mparent->mleft = NULL;
                    }
                    else
                    {
                        pcur->mparent->mright = NULL;
                    }
                    pcur->mparent = NULL;
                }
            }
        }

        delete pcur;
    }

    // 中序遍历
    void inOrder()
    {
        inOrder(mroot);
        cout << endl;
    }

    void check()
    {
        bool ret = check(mroot);
        if (ret)
        {
            cout << "红黑树正常" << endl;
        }
        else
        {
            cout << "红黑树不正常" << endl;
        }
    }
private:
    bool check(RBNode<T> *pnode)
    {
        if (pnode == NULL)
            return true;

        if (color(pnode) == Color::RED)
        {
            if (color(pnode->mleft) == Color::RED
                || color(pnode->mright) == Color::RED)
            {
                return false;
            }
        }

        return check(pnode->mleft) && check(pnode->mright);
    }
    void inOrder(RBNode<T> *pnode)
    {
        if (pnode != NULL)
        {
            inOrder(pnode->mleft);
            cout << pnode->mdata << " ";
            inOrder(pnode->mright);
        }
    }
    // 红黑树插入节点,进行旋转操作和重新着色
    void fixAfterInsert(RBNode<T> *x)
    {
        while (x != NULL && x != mroot && color(parent(x)) == Color::RED)
        {
            // 插入节点在祖父节点的左子树上
            if (parent(x) == left(parent(parent(x))))
            {
                if (color(right(parent(parent(x)))) == Color::RED)
                {
                    // 叔父节点是红色
                    parent(x)->mcolor = Color::BLACK;
                    right(parent(parent(x)))->mcolor = Color::BLACK;
                    parent(parent(x))->mcolor = Color::RED;
                    x = parent(parent(x));
                }
                else
                {
                    // 叔父节点是黑色
                    if (right(parent(x)) == x)
                    {
                        x = parent(x);
                        leftRotate(x);
                    }

                    parent(x)->mcolor = Color::BLACK;
                    parent(parent(x))->mcolor = Color::RED;
                    rightRotate(parent(parent(x)));
                }
            }
            else
            {
                // 插入节点在祖父节点的右子树上
                if (color(left(parent(parent(x)))) == Color::RED)
                {
                    // 叔父节点是红色
                    parent(x)->mcolor = Color::BLACK;
                    left(parent(parent(x)))->mcolor = Color::BLACK;
                    parent(parent(x))->mcolor = Color::RED;
                    x = parent(parent(x));
                }
                else
                {
                    if (left(parent(x)) == x)
                    {
                        x = parent(x);
                        rightRotate(x);
                    }

                    parent(parent(x))->mcolor = Color::RED;
                    parent(x)->mcolor = Color::BLACK;
                    leftRotate(parent(parent(x)));
                }
            }
        }

        // 把根节点的颜色调整成黑色
        mroot->mcolor = Color::BLACK;
    }

    // 红黑树删除节点,进行旋转操作和重新着色
    void fixAfterDelete(RBNode<T> *x)
    {
        while (x != NULL && x != mroot && color(x) == Color::BLACK)
        {
            // 当前节点是父节点的左孩子
            if (left(parent(x)) == x)
            {
                // 当兄弟节点是红色节点
                if (color(right(parent(x))) == Color::RED)
                {
                    parent(x)->mcolor = Color::RED;
                    right(parent(x))->mcolor = Color::BLACK;
                    leftRotate(parent(x));
                }

                // 当兄弟节点是黑色节点
                // 当兄弟节点的两个子节点都是黑色的
                if (color(left(right(parent(x)))) == Color::BLACK
                    && color(right(right(parent(x)))) == Color::BLACK)
                {
                    right(parent(x))->mcolor = Color::RED;
                    x = parent(x);
                }
                else
                {
                    // 左孩子是红色
                    if (color(left(right(parent(x)))) == Color::RED)
                    {
                        left(right(parent(x)))->mcolor = Color::BLACK;
                        right(parent(x))->mcolor = Color::RED;
                        rightRotate(right(parent(x)));
                    }

                    // 右孩子是红色
                    right(parent(x))->mcolor = parent(x)->mcolor;
                    parent(x)->mcolor = Color::BLACK;
                    right(right(parent(x)))->mcolor = Color::BLACK;
                    leftRotate(parent(x));
                    x = mroot; // 已经平衡了,退出循环
                }
            }
            else
            {
                // 当兄弟节点是红色节点
                if (color(left(parent(x))) == Color::RED)
                {
                    parent(x)->mcolor = Color::RED;
                    left(parent(x))->mcolor = Color::BLACK;
                    rightRotate(parent(x));
                }

                // 当兄弟节点是黑色节点
                // 当兄弟节点的两个子节点都是黑色的
                if (color(left(left(parent(x)))) == Color::BLACK
                    && color(right(left(parent(x)))) == Color::BLACK)
                {
                    left(parent(x))->mcolor = Color::RED;
                    x = parent(x);
                }
                else
                {
                    // 右孩子是红色
                    if (color(right(left(parent(x)))) == Color::RED)
                    {
                        right(left(parent(x)))->mcolor = Color::BLACK;
                        left(parent(x))->mcolor = Color::RED;
                        leftRotate(left(parent(x)));
                    }

                    // 左孩子是红色
                    left(parent(x))->mcolor = parent(x)->mcolor;
                    parent(x)->mcolor = Color::BLACK;
                    left(left(parent(x)))->mcolor = Color::BLACK;
                    rightRotate(parent(x));
                    x = mroot; // 已经平衡了,退出循环
                }
            }
        }

        // 把节点的颜色调整成黑色
        x->mcolor = Color::BLACK;
    }

    // 左旋
    void leftRotate(RBNode<T> *pnode)
    {
        RBNode<T> *pchild = pnode->mright;
        pnode->mright = pchild->mleft;
        if (pchild->mleft != NULL)
        {
            pchild->mleft->mparent = pnode;
        }
        pchild->mparent = pnode->mparent;
        if (pnode->mparent == NULL)
        {
            mroot = pchild;
        }
        else if (pnode->mparent->mleft == pnode)
        {
            pnode->mparent->mleft = pchild;
        }
        else
        {
            pnode->mparent->mright = pchild;
        }
        pchild->mleft = pnode;
        pnode->mparent = pchild;
    }

    // 右旋
    void rightRotate(RBNode<T> *pnode)
    {
        RBNode<T> *pchild = pnode->mleft;
        pnode->mleft = pchild->mright;
        if (pchild->mright != NULL)
        {
            pchild->mright->mparent = pnode;
        }
        pchild->mparent = pnode->mparent;
        if (pnode->mparent == NULL)
        {
            mroot = pchild;
        }
        else if (pnode->mparent->mleft == pnode)
        {
            pchild->mparent->mleft = pchild;
        }
        else
        {
            pchild->mparent->mright = pchild;
        }
        pchild->mright = pnode;
        pnode->mparent = pchild;
    }

    RBNode<T>* parent(RBNode<T> *pnode)
    {
        return pnode->mparent;
    }
    RBNode<T>* left(RBNode<T> *pnode)
    {
        return pnode->mleft;
    }
    RBNode<T>* right(RBNode<T> *pnode)
    {
        return pnode->mright;
    }
    Color color(RBNode<T> *pnode)
    {
        return pnode == NULL ? Color::BLACK : pnode->mcolor;
    }
private:
    RBNode<T> *mroot;
};
/*
红黑树定义:
1.根节点是黑色的,所有叶子节点也是黑色的(把指针域NULL定义成黑色)
2.不能出现两个连续的红色节点,也就是父节点是红色,孩子节点必须是黑色
3.从根节点到每一个叶子节点,都包含相同数量的黑色节点
*/
int main()
{
    RBTree<int> rbtree;
    for (int i = 0; i < 1000; ++i)
    {
        rbtree.insert(i + 1);
    }

    rbtree.inOrder();

    rbtree.check();

    for (int i = 560; i < 820; ++i)
    {
        rbtree.remove(i);
    }
    rbtree.inOrder();
    rbtree.check();

    return 0;
}
评论区