• C++精通之路：红黑树

    文章目录

    很多小伙伴为了刷题发愁
    今天为大家推荐一款刷题神奇哦：刷题面试神器牛客
    各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题 应有尽有，赶快来装备自己吧！助你面试稳操胜券，solo全场面试官

    红黑树

    一：红黑树的概念

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

    二：红黑树的性质

    1. 每个结点不是红色就是黑色
    2. 根节点是黑色的
    3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
    4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
    5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

    通过以上的规则，就能保证：
    其最长路径中节点个数不会超过最短路径节点个数的两倍
    从而达到相对平衡

    三：红黑树节点的定义

    // 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
RBTreeNode<ValueType>* _pRight; // 节点的右孩子
RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 注意：

    需要将节点的默认颜色给成红色的，因为红色不影响红黑树的整体结构。
    在后续插入的情况，也是一样

    四：红黑树结构

    • 在stl源码中的结构：
      在这里插入图片描述

    五：红黑树的插入操作

    1. 先用简单的比较，找到插入节点需要插入的位置
    2. 因为默认是为红色，所以要向上判断是否违反规则，情况如下：
    1. 父亲是黑色，则不用做任何操作即可满足红黑树的结构
    2. 父亲是红色，出现了连续的红节点，不满足红黑树的结构，需要处理，具体处理情况如下：
    • 具体处理情况：
    1. 因为父亲是红色，所以父亲不可能是根，因为不能出现连续的红节点，所以祖父是黑节点，
    2. 祖父和父亲都确定了，只有祖父的另外一个孩子（叔叔）的颜色没有确定
    3. 所以我们以叔叔的颜色为特殊情况再以次分析如何处理
    • 注：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

    情况一（只需要变色）：

    • cur为红，p为红，g为黑，u存在且为红
      在这里插入图片描述

    因为有连续的红节点，必须要做变色处理了，如何保证在不破坏红黑树的整体结构下来做变色处理呢？

    • 我们选择把 g变红，p和u变黑来处理。
    • 这样就保证了在p和u这两条路径下的黑色节点没有发生改变并且没有了连续的红节点
    • 但是g的改变也会导致g上层结构的变化，所以我们还要做出改变：
    1. 假如g为根节点的时候，将其变黑
    2. 假如g不为根节点的时候，则继续以g为新增节点向上调整

    情况二（单旋加变色）：

    • cur为红，p为红，g为黑，u不存在/u为黑
      在这里插入图片描述
    1. 假如u不存在，则cur一定是新增节点，因为假如cur原来是黑色的话，就违反了规则：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
    2. 假如u存在，所以u为黑色（为红色的情况以讨论）：假设cur是新增节点，则在cur未插入前，p左子树的这条路径的长度已经逼u上的路径上的黑色节点少了，违反了规则：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点，所以假设不成立，cur一定是从黑色变为红色的
    • 解决方法：

    如果p为g的左孩子，cur为p的左孩子，则进行右单旋转，p变黑，g变红
    如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，p变黑，g变红

    • 原因/理由：
      如果p为g的左孩子，cur为p的左孩子，则失去了平衡，通过变色已经无法满足要求了，所以我们就要借助旋转来帮助我们。所以如果p为g的左孩子，cur为p的左孩子，则进行右单旋转，p变黑，g变红。即平衡了整个树，又保证了路径中的黑色节点不变。

    情况三（双旋加变色）：

    也是cur为红，p为红，g为黑，u不存在/u为黑，但cur的位置发生了变化，如图所示：
    在这里插入图片描述

    • 解决办法：

    1. 如果p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，p旋转后再对g进行右单旋，旋转后将cur变黑，g变红

    2. 如果p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，p旋转后再对g进行左单旋，旋转后将cur变黑，g变红

    • 具体步骤图：
      在这里插入图片描述

    插入的实现

    pair<Node*, bool> Insert(const pair<K, V>& kv)
{
    //空树的情况
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return make_pair(_root, true);
    }

    //查找位置插入节点
    Node* cur = _root, * parent = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return make_pair(cur, false);
        }
    }

    //创建链接节点
    cur = new Node(kv);
    Node* newnode = cur;
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;
    
    //父节点存在且为红，则需要调整（不能存在连续的红色节点）
    while (parent && parent->_col == RED)
    {
        //此时当前节点一定有祖父节点
        Node* granparent = parent->_parent;
        //具体调整情况主要看叔叔节点
        //分左右讨论
        if (parent == granparent->_left)
        {
            Node* uncle = granparent->_right;
            //情况1：叔叔节点存在且为红
            if (uncle && uncle->_col == RED)
            {
                //修改颜色，继续向上检查
                granparent->_col = RED;
                parent->_col = uncle->_col = BLACK;

                cur = granparent;
                parent = cur->_parent;
            }
            else//情况2和3：叔叔节点不存在 或者存在且为黑
            {
                //单旋(三代节点为斜线)+变色
                if (cur == parent->_left)
                {
                    RotateR(granparent);

                    granparent->_col = RED;
                    parent->_col = BLACK;
                }
                else//双旋(三代节点为折线)+变色
                {
                    RotateL(parent);
                    RotateR(granparent);

                    cur->_col = BLACK;
                    granparent->_col = RED;
                }
                //旋转后不需再向上调整了
                break;
            }
        }
        else//parent=grandparent->right
        {
            Node* uncle = granparent->_left;
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                granparent->_col = RED;

                cur = granparent;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_right)
                {
                    RotateL(granparent);

                    parent->_col = BLACK;
                    granparent->_col = RED;
                }
                else
                {
                    RotateR(parent);
                    RotateL(granparent);

                    cur->_col = BLACK;
                    granparent->_col = RED;
                }
                break;
            }
        }
    }
    
    //确保根节点为黑
    _root->_col = BLACK;
    return make_pair(newnode, true);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123

    旋转实现

    void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentP = parent->_parent;


    parent->_right = subRL;
    if (subRL)
    {
        subRL->_parent = parent;
    }

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

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

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


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

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

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

    六:红黑树的验证

    • 红黑树的检测分为两步：

    1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

    2. 检测其是否满足红黑树的性质

    实现代码：

    bool IsRBTree()
{
    //空树
    if (_root == nullptr)
    {
        return true;
    }
    //根节点为黑色
    if (_root->_col == RED)
    {
        cout << "根节点为红色" << endl;
        return false;
    }
    //黑色结点数量各路径上相同
    //先走一条得到基准值
    int Blacknum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            Blacknum++;
        cur = cur->_left;
    }
    //检查子树
    int i = 0;
    return _IsRBTree(_root, Blacknum, i);
}

bool _IsRBTree(Node* root, int blacknum, int count)
{
    //递归到空节点
    if (root == nullptr)
    {
        if (blacknum == count)
            return true;
        cout << "各路径上黑色节点个数不同" << endl;
        return false;
    }
	//子节点为红则检查父节点是否为红（通过父节点检查子节点会遇到空节点）
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续红色节点" << endl;
        return false;
    }
	//计数黑结点
    if (root->_col == BLACK)
        count++;
	//递归左右子树
    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    七、红黑树的删除

    红黑树的删除不做讲解，有兴趣可参考：《算法导论》或者《STL源码剖析》
    http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
    http://blog.csdn.net/chenhuajie123/article/details/11951777

    八：红黑树与AVL树的比较

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

    九：红黑树的应用

    1. C++ STL库 – map/set、mutil_map/mutil_set
    2. Java 库
    3. linux内核
    4. 其他一些库

    下一章我们将会将map/set如何通过红黑树来实现的，敬请期待吧！！

    总结

    红黑树是一个极其优秀的数据结构，也是面试中比较爱考的。在liunx，c++，java中也有很多的使用。
    对于我们这些将来的互联网从业者来说，是一个必须要掌握的数据结构（可以不知道具体的代码实现，但要懂红黑树是如何实现的，以及后来如何封装出map/set的）。

  • 相关阅读:
    6-26漏洞利用-tomcat管理密码破解
    契约锁助力大型能源组织“产-运-储-销-交易”文件电子签
    vue2中，使用sortablejs组件和vuedraggable实现拖拽排序功能
    MySQL篇---第二篇
    maven多模块依赖包程序包xxx不存在
    jwt not active
    上海00后985毕业女生月薪1.2w，想找年薪40万程序员，网友表示很不理解
    根据递归原理设计一个简单的代码生成器
    【Qt】Sqlite数据库加密
    muduo源码剖析之Buffer缓冲区类
  • 原文地址：https://blog.csdn.net/yin_ming_hui/article/details/126037246