[C++][数据结构][红黑树]详细讲解

标签：cur parent C++ col 红黑树数据结构节点 left

1.红黑树的概念

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

2.红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的 --> 树中没有连续的红色节点
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 --> 每条路径的黑色节点数量相等
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍？
- 极限最短：全黑
- 极限最长：一黑一红

3.红黑树节点的定义

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, Colour colour = RED)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(colour)
    {}
};

4.红黑树的结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色
并且让头结点的_parent域指向红黑树的根节点，_left域指向红黑树中最小的节点，_right域指向红黑树中最大的节点
但是我的实现中，并没有使用头节点

5.红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
- 按照二叉搜索的树规则插入新节点
- 检测新节点插入后，红黑树的性质是否造到破坏
  - 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整
  - 但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
注意：此处所看到的树，可能是一颗完整的树，也可能是一颗子树
红黑树的关键是叔叔 --> 遇事不决看叔叔
cur为红，p为红，g为黑是固定的

1.cur为红，p为红，g为黑，u存在且为红

请添加图片描述

如果g是根节点，调整完成后，需要将g改为黑色
如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整

请添加图片描述

解决方式：
- 将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

2.cur为红，p为红，g为黑，u不存在/u存在且为黑 – 单旋+变色

请添加图片描述

u的情况有两种
- 如果u节点不存在
  - 则cur一定是新插入节点
  - 因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同
- 如果u节点存在，且为黑
  - 则cur节点原来的颜色一定是黑色的
  - 现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色
解决方式：
- p为g的左孩子，cur为p的左孩子，则进行右单旋转
- p为g的右孩子，cur为p的右孩子，则进行左单旋转
- p变黑色，g变红色

3.cur为红，p为红，g为黑，u不存在/u存在且为黑 – 双旋+变色

请添加图片描述

解决方式：
- p为g的左孩子，cur为p的右孩子，则针对p做左单旋转
- p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
- 转换成情况二
- 再以g为轴点进行右单旋/左单旋

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);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;

    // 处理颜色
    while (parent && parent->_col == RED)
    {
        Node *grandparent = parent->_parent;
        assert(grandparent);
        assert(grandparent->_col == BLACK);

        // 关键看叔叔
        if (grandparent->_left == parent)
        {
            Node *uncle = grandparent->_right;
            if (uncle && uncle->_col == RED)
            {
                // 1.uncle存在且为红
                parent->_col = uncle->_col = BLACK;
                grandparent->_col = RED;

                // 继续往上处理
                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
                // 2.uncle不存在/存在且为黑
                if (parent->_left == cur) // 情况二：右单旋 + 变色
                {
                    RotateR(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else // 情况三：左右双旋 + 变色
                {
                    RotateL(parent);
                    RotateR(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }

                break;
            }
        }
        else // grandparent->_right == parent
        {
            Node *uncle = grandparent->_left;
            if (uncle && uncle->_col == RED)
            {
                // 1.uncle存在且为红
                parent->_col = uncle->_col = BLACK;
                grandparent->_col = RED;

                // 继续往上处理
                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
                // 2.uncle不存在/存在且为黑
                if (parent->_right == cur) // 情况二：左单旋 + 变色
                {
                    RotateL(grandparent);

                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else // 情况三：右左双旋 + 变色
                {
                    RotateR(parent);
                    RotateL(grandparent);

                    cur->_col = BLACK;
                    grandparent->_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本来就为空，对空指针访问
    {
        subRL->_parent = parent;
    }

    // 用于判断原来的parent是否是子树
    Node *grandParent = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

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

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

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

    Node *grandParent = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

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

        subL->_parent = grandParent;
    }
}

6.红黑树的迭代器

1.begin()与end()

STL明确规定
- begin()与end()代表的是一段前闭后开的区间
- 而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？
  - 答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置

typedef __RBTree_Iterator<T, T &, T *> iterator;

iterator begin()
{
    Node *left = _root;
    while (left && left->_left) // left --> 防止空树
    {
        left = left->_left;
    }

    return iterator(left); // 匿名结构体
}

iterator end()
{
    return iterator(nullptr); // 非带头节点版本
}

2.operator++

右子树不为空 --> ++就是找右子树的最左节点
右子树为空 --> ++找现孩子不是父亲右的那个祖先

3.operator–

左子树不为空 --> --就是找左子树的最右节点
左子树为空 --> --找现孩子不是父亲左的那个祖先

template <class T, class Ref, class Ptr>
struct __RBTree_Iterator
{
    typedef RBTreeNode<T> Node;
    typedef __RBTree_Iterator<T, Ref, Ptr> Self;
    Node *_node;

    __RBTree_Iterator(Node *node)
        : _node(node)
    {}

    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &(operator*());
    }

    bool operator!=(const Self &s) const
    {
        return _node != s._node;
    }

    bool operator==(const Self &s) const
    {
        return _node == s._node;
    }

    Self& operator++()
    {
        if (_node->_right)
        {
            // 下一个就是右子树的最左节点
            Node *left = _node->_right;
            while (left->_left)
            {
                left = left->_left;
            }

            _node = left;
        }
        else
        {
            // 找祖先里面 孩子不是父亲的右 的那个祖先
            Node *parent = _node->_parent;
            Node *cur = _node;

            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = parent->_parent;
            }

            _node = parent;
        }

        return *this;
    }

    Self operator--()
    {
        if (_node->_left)
        {
            // 下一个节点是左子树的最右节点
            Node *right = _node->_left;
            while (right->_right)
            {
                right = right->_right;
            }

            _node = right;
        }
        else
        {
            // 找祖先里面 孩子不是父亲的左 的那个祖先
            Node *parent = _node->_parent;
            Node *cur = _node;

            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = parent->_parent;
            }

            _node = parent;
        }
    }
};

7.红黑树的验证

红黑树的检测分为两步：
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质

bool IsBalance()
{
    if (_root == nullptr)
    {
        return true;
    }

    if (_root->_col == RED)
    {
        cout << "根节点不是黑色" << endl;
        return false;
    }

    // 获取黑色节点数量基准值  -->  每一条路黑色节点数量相同
    Node *cur = _root;
    int benchmark = 0;
    while (cur)
    {
        if (cur->_col == BLACK)
        {
            ++benchmark;
        }
        cur = cur->_left;
    }

    return PreCheck(_root, 0, benchmark);
}

bool PreCheck(Node *root, int blackNum, int &benchmark)
{
    if (root == nullptr)
    {
        if (blackNum != benchmark)
        {
            cout << "某条黑色节点的数量不相等" << endl;
            return false;
        }
        else
        {
            return true;
        }
    }

    if (root->_col == BLACK)
    {
        ++blackNum;
    }

    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续的红色节点" << endl;
    }

    return PreCheck(root->_left, blackNum, benchmark) && PreCheck(root->_right, blackNum, benchmark);
}

8.红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)
红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

标签：cur,parent,C++,col,红黑树,数据结构,节点,left
From： https://blog.csdn.net/qq_37281656/article/details/139724602

[C++][数据结构][红黑树]详细讲解

目录

1.红黑树的概念

2.红黑树的性质

3.红黑树节点的定义

4.红黑树的结构

5.红黑树的插入操作

1.cur为红，p为红，g为黑，u存在且为红

2.cur为红，p为红，g为黑，u不存在/u存在且为黑 – 单旋+变色

3.cur为红，p为红，g为黑，u不存在/u存在且为黑 – 双旋+变色

6.红黑树的迭代器

1.begin()与end()

2.operator++

3.operator–

7.红黑树的验证

8.红黑树与AVL树的比较

相关文章

赞助商

阅读排行