AI 助理
备案控制台
开发者社区 云原生 文章 正文

红黑树源代码（进阶与细节解释）

2025-06-03 45
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 看完前两篇的文章，相信对于红黑树有了一定的了解，知道红黑树是怎么样子进行插入的，是怎么样进行查找的，知道了底层是怎么样子的，知道了其与AVL树，二叉搜索树有什么区别了。但是对于set，map的底层又全是红黑树，set与map的区别就是其键值对一个是k，k型，一个是k，v型的，所以就有了封装，（对于封装后面会讲解什么是封装）二者底层全是同一份的红黑树，但是前面两篇文章的红黑树要不只能使用与k，k型，要不就是k，v型，所以就要对红黑树的源代码进行修改，进行细节上的修饰与进阶。

​
目录

看完前两篇的文章，相信对于红黑树有了一定的了解，知道红黑树是怎么样子进行插入的，是怎么样进行查找的，知道了底层是怎么样子的，知道了其与AVL树，二叉搜索树有什么区别了。

但是对于set，map的底层又全是红黑树，set与map的区别就是其键值对一个是k，k型，一个是k，v型的，所以就有了封装，（对于封装后面会讲解什么是封装）二者底层全是同一份的红黑树，但是前面两篇文章的红黑树要不只能使用与k，k型，要不就是k，v型，所以就要对红黑树的源代码进行修改，进行细节上的修饰与进阶。

对于结点的修改
对于此其实不需要进行特别的修改，但是要注意这里的T，如果要是对应的set，那么他就是K，如果是map那么他就是pair。

enum Colour
{
RED,
BLACK,
};

template
struct RBTreeNode
{
RBTreeNode _left;
RBTreeNode _right;
RBTreeNode* _parent;
T _data;
Colour _col;

RBTreeNode(const T& data)
    : _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
    , _col(RED)
{}

};
红黑树模板参数的控制

这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template
class RBTree
这里的T也就是对应的结点设置的T，上面也说了，set对应的是K，map是pair。

那么下面就看看set容器与map容器中的传的模板参数吧。

template
class set
{
public:
//...
private:
RBTree _t;
};

template
class map
{
public:
//...
private:
RBTree> _t;
};
那能不能不要红黑树的第一个模板参数，只保留第二个模板参数呢？

乍眼一看好像是可以的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但实际上红黑树的第一个模板参数是不能省略的。

对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase。

红黑树结点当中存储的数据

前面说到，由于上层容器的不同，底层红黑树当中的K和T也是不同的：

set容器：K和T都代表键值Key。
map容器：K代表键值Key，T代表由Key和Value构成的键值对。
对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。

这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是键值对。

所以说其实结点的设置其实没有太大的修改，还是与原本还差不多。

对于insert函数的细节修改
在做完上面的修改后，原本的代码如果在运行下，是会有些问题的，（问题是在封装出现）这里问题是什么就不多说了，

修改起来也是很简单

只需要把其返回值修改为如此就可以。

然后第一个参数就是结点指针，第二个是bool值，插入成功返回true，失败false。

迭代器的代码
对于解决迭代器的问题，首先就是要添加一个迭代器类，然后再解决迭代器的++/--，对于红黑树的++，--。用语言来说是很简便的。

迭代器类的添加
template
struct TreeIterator
{
typedef RBTreeNode Node;
typedef TreeIterator Self;
Node* _node;

__TreeIterator(Node* node)
    :_node(node)
{}
Ref operator*()
{
    return _node->_data;
}
Ptr operator->()
{
    return &_node->_data;
}

};
template
class RBTree
{
typedef RBTreeNode Node;
public:
typedef TreeIterator iterator;
typedef TreeIterator const_iterator;
//......
private:
Node* _root = nullptr;
};
迭代器的++
核心：中序的下一个

it指向的节点，右子树不为空，下一个就是右子树的最左节点。
it指向的节点，右子树为空，it所在的子树全已访问完了，那么需要往上找孩子是父亲做节点的那个祖先。
迭代器的--
it的左子树不为空，下一个就为左子树的最有节点。
it的左子树为空，沿着根找孩子是父亲右节点的那个祖先。
代码展示：

Self& operator--()
{
    //走的是中序  左 根 右
    if (_node->_left)
    {
        //左不为空，下一个就是左子树的最右
        Node* cur = _node->_left;
        while (cur->_right)
        {
            cur = cur->_right;
        }
        _node = cur;
    }

    else
    {
        //左为空，没根找孩子是父亲右的那个祖先
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }

    return *this;
}
Self& operator++()
{
    //走的是中序  左 根 右
    if (_node->_right)
    {
        //右子树不为空，下一个就是右子树的最左结点
        Node* cur = _node->_right;
        while (cur->_left)
        {
            cur = cur->_left;
        }

        _node = cur;
    }

    else
    {
        //右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)
        {
            cur = parent;
            parent = parent->_parent;
        }

        _node = parent;
    }

    return *this;
}

正向迭代器的代码
template
struct TreeIterator
{
typedef RBTreeNode Node;
typedef TreeIterator Self;
Node* _node;

__TreeIterator(Node* node)
    :_node(node)
{}
Ref operator*()
{
    return _node->_data;
}
Ptr operator->()
{
    return &_node->_data;
}
Self& operator--()
{
    //走的是中序  左 根 右
    if (_node->_left)
    {
        //左不为空，下一个就是左子树的最右
        Node* cur = _node->_left;
        while (cur->_right)
        {
            cur = cur->_right;
        }
        _node = cur;
    }

    else
    {
        //左为空，没根找孩子是父亲右的那个祖先
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }

    return *this;
}
Self& operator++()
{
    //走的是中序  左 根 右
    if (_node->_right)
    {
        //右子树不为空，下一个就是右子树的最左结点
        Node* cur = _node->_right;
        while (cur->_left)
        {
            cur = cur->_left;
        }

        _node = cur;
    }

    else
    {
        //右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)
        {
            cur = parent;
            parent = parent->_parent;
        }

        _node = parent;
    }

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

};
对于迭代器的最后一步就是添加上begin（），end（）函数。

红黑树代码全部展示：

pragma once

include

include

include

using namespace std;
enum Colour
{
RED,
BLACK,
};

template
struct RBTreeNode
{
RBTreeNode _left;
RBTreeNode _right;
RBTreeNode* _parent;
T _data;
Colour _col;

RBTreeNode(const T& data)
    : _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
    , _col(RED)
{}

};

template
struct TreeIterator
{
typedef RBTreeNode Node;
typedef TreeIterator Self;
Node* _node;

__TreeIterator(Node* node)
    :_node(node)
{}
Ref operator*()
{
    return _node->_data;
}
Ptr operator->()
{
    return &_node->_data;
}
Self& operator--()
{
    //走的是中序  左 根 右
    if (_node->_left)
    {
        //左不为空，下一个就是左子树的最右
        Node* cur = _node->_left;
        while (cur->_right)
        {
            cur = cur->_right;
        }
        _node = cur;
    }

    else
    {
        //左为空，没根找孩子是父亲右的那个祖先
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }

    return *this;
}
Self& operator++()
{
    //走的是中序  左 根 右
    if (_node->_right)
    {
        //右子树不为空，下一个就是右子树的最左结点
        Node* cur = _node->_right;
        while (cur->_left)
        {
            cur = cur->_left;
        }

        _node = cur;
    }

    else
    {
        //右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)
        {
            cur = parent;
            parent = parent->_parent;
        }

        _node = parent;
    }

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

};

template
class RBTree
{
typedef RBTreeNode Node;
public:
typedef TreeIterator iterator;
typedef TreeIterator const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}

    return iterator(cur);
}    
iterator end()
{
    return iterator(nullptr);
}
const_iterator begin() const
{
    Node* cur = _root;
    while (cur && cur->_left)
    {
        cur = cur->_left;
    }

    return const_iterator(cur);
}
const_iterator end() const
{
    return const_iterator(nullptr);
}
pair<Node*, bool> Insert(const T& data)
{
    if (_root == nullptr)
    {
        _root = new Node(data);

        _root->_col = BLACK;
        return make_pair(_root, true);;
    }

    Node* parent = nullptr;
    Node* cur = _root;

    while (cur)
    {
        if (cur->_data < data)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_data > data)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return make_pair(cur, false);;
        }
    }

    cur = new Node(data);
    Node* newnode = cur;
    //默认结点颜色为红色

    if (parent->_data < data)
    {
        parent->_right = cur;
        cur->_parent = parent;
    }
    else
    {
        parent->_left = cur;
        cur->_parent = parent;
    }

    while (parent && parent->_col == RED)
    {
        Node* grandfather = parent->_parent;
        //大前提
        //parent在左
        if (parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;
            //Node* uncle = parent->_right;//错误二
            if (uncle && uncle->_col == RED)
            {
                //情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
                    //     g
                    //   p   u
                    // c
                    // 
                    //解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_left)
                {
                    //情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
                        //     g
                        //   p   u
                        // c
                        // 
                    // 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    //情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
                        //       g
                        //   p      u
                        //     c
                    // 解决：对p左单旋，后变为情景二。
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
        else//情景大概反着来
        {
            //1  uncle
            Node* uncle = grandfather->_left;//错误一
            //Node* uncle = parent->_right;//错误一
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            }

            else
            {
                if (cur == parent->_right)//2
                {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else//3
                {
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    //最后
    _root->_col = BLACK;

    return make_pair(newnode, true);;
}
void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    subR->_left = parent;

    Node* parentParent = parent->_parent;

    parent->_parent = subR;
    if (subRL)
        subRL->_parent = parent;

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

        subR->_parent = parentParent;
    }
}

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

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

    Node* parentParent = parent->_parent;

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

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

        subL->_parent = parentParent;
    }
}

iterator Find(const K& key)
{
    Node* cur = _root;
    KeyOfT kot;
    while (cur)
    {
        if (cur->_data < key)
        {
            cur = cur->_right;
        }
        else if (cur->_data > key)
        {
            cur = cur->_left;
        }
        else
        {
            return iterator(cur);
        }
    }
    return end();
}
void InOrder()
{
    _InOrder(_root);
    cout << endl;
}
void _InOrder(Node* root)
{
    if (root == nullptr)
        return;
    _InOrder(root->_left);
    cout << kof(root->_data) << " ";
    _InOrder(root->_right);
}
bool Check(Node* root, int blacknum, const int refVal)
{
    if (root == nullptr)
    {
        if (refVal != blacknum)
        {
            cout << "存在黑色节点数量不相等的路径" << endl;
            return false;
        }
        return true;
    }
    if (root->_col == RED)
    {
        if (root->_parent->_col == RED)
        {
            cout << "有连续的红色节点" << endl;
            return false;
        }
    }
    if (root->_col == BLACK)
    {
        ++blacknum;
    }
    return Check(root->_left, blacknum, refVal)
        && Check(root->_right, blacknum, refVal);

}
bool IsBalance()
{
    //1:是否存在 红-红 
   //每条路径黑色结点是否相同个数
   //最长的不超过最短的二倍
   //根，叶子为黑
    if (_root == nullptr)
        return true;
    if (_root->_col == RED)
        return false;
    int refVal = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
        {
            ++refVal;
        }
        cur = cur->_left;
    }
    int blacknum = 0;
    return Check(_root, blacknum, refVal);
}

private:
Node* _root = nullptr;
};
下一篇文章就开始进行封装的解释。

​

文章标签：
容器
存储
hahaha无
目录
相关文章
hahaha无
|
4月前
|
C语言
学习atoi
然后，从该字符开始，接受一个可选的初始加号或减号，然后跟随尽可能多的十进制数字，并将它们解释为一个数值。④如果字符串str中第一个非空白字符序列不是有效的整数，或者如果不存在这样的序列，因为str为空或只包含空白字符，则不执行转换，并返回零。base-10 digits——十进制数字，即0、1、2、3、4、5、6、7、8、9这10个数字。③字符串可以包含形成整数的字符之后的其他字符，这些字符将被忽略，并不会影响此函数的行为。①解析C字符串str，将其内容解释为整数，并将其作为int类型的值返回。
hahaha无
60 0
Bluening
|
4月前
|
存储 JSON 前端开发
菜鸟之路Day39一一登录
本文介绍了登录功能的实现及其相关技术细节，包括会话管理、令牌认证和异常处理等内容。作者通过 Java 实现了一个基于用户名和密码的登录接口，调用服务层和数据库层完成用户验证。同时，文章深入探讨了三种会话跟踪技术：Cookie、Session 和 JWT 令牌。 在 JWT 部分，详细讲解了其生成与校验流程，实现了登录成功后返回 JWT 令牌的功能。此外，文章还介绍了过滤器（Filter）和拦截器（Interceptor）的概念及应用，演示了如何利用它们实现登录校验。 最后，为解决前后端交互中异常响应不统一的问题，定义了一个全局异常处理器 将系统异常以统一的 JSON 格式返回给前端。
Bluening
128 0
hahaha无
|
4月前
|
C++
爱心代码 C++
这段C++代码使用EasyX图形库生成动态爱心图案。程序通过数学公式绘制爱心形状，并以帧动画形式呈现渐变效果。运行时需安装EasyX库，教程链接：http://【EasyX图形库的安装和使用】https://www.bilibili.com/video/BV1Xv4y1p7z1。代码中定义了屏幕尺寸、颜色数组等参数，利用随机数与数学函数生成动态点位，模拟爱心扩散与收缩动画，最终实现流畅的视觉效果。
hahaha无
507 0
hahaha无
|
4月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。在unordered_set中，元素的值同时也是唯一地标识它的key。在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
hahaha无
194 0
hahaha无
|
4月前
|
NoSQL Linux 开发工具
Linux环境基础开发工具的使用（yum、vim、gcc、g++、gdb、make/Makefile）
本文介绍了yum 包管理工具、Vim 编辑器、gcc/g++ 编译器、gdb 调试器、编译原理及 Makefile 的使用，同时还配备了如何使用，以及图解。旨在帮助读者更好地理解和应用这些工具与技术。
hahaha无
214 0
hahaha无
|
4月前
|
安全 Shell 开发工具
Windows下使用git配置gitee远程仓库
就在前几天因为一些原因，我的电脑重装了系统，然后再重新配置git的环境的时候就遇到了一些小问题。所以我决定自己写一篇文章，以便以后再配置git时，避免一些错误操作，而导致全网搜方法，找对的文章去找对应的解决方法。下面为了演示方便就拿gitee来演示，不拿GitHub了写文章了。
hahaha无
222 0
hahaha无
|
4月前
|
存储 人工智能 Unix
Linux常见指令汇总
最常见的就是 ll (为ls -l的省略）
hahaha无
166 0
hahaha无
|
4月前
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别，注意事项
set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列。set当中存储元素的value都是唯一的，不可以重复，因此可以使用set进行去重。set默认是升序的，但是其内部默认不是按照大于比较，而是按照小于比较。set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
hahaha无
205 0
hahaha无
|
4月前
|
存储 算法 安全
c++模板进阶操作——非类型模板参数、模板的特化以及模板的分离编译
在 C++ 中，仿函数（Functor）是指重载了函数调用运算符()的对象。仿函数可以像普通函数一样被调用，但它们实际上是对象，可以携带状态并具有更多功能。与普通函数相比，仿函数具有更强的灵活性和可扩展性。仿函数通常通过定义一个包含operator()的类来实现。public:// 重载函数调用运算符Add add;// 创建 Add 类的对象// 使用仿函数return 0;
hahaha无
134 0