STL -- C++ 红黑树封装 Map 和 Set 基本实现思路如下一、红黑树基础1.1 什么是红黑树红黑树是一种自平衡的二叉搜索树每个节点增加一个存储位表示颜色红或黑。通过对任何一条从根到叶子的路径上各个节点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是近似平衡的。1.2 红黑树的五条性质每个节点不是红色就是黑色根节点是黑色每个叶子节点NIL是黑色通常用空指针表示如果一个节点是红色则它的两个子节点都是黑色不能有连续的红节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点黑色高度相等1.3 与 AVL 树的对比AVL 树严格平衡左右子树高度差不超过1查询快插入/删除旋转较多红黑树近似平衡最长路径不超过最短路径的2倍插入/删除旋转较少整体性能更优应用场景map,set, Linux 内核的epoll红黑树二、红黑树节点与迭代器2.1 节点结构RBTreeNodeTtemplateclass T class RBTreeNode { T _data; RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; Color _col; // RED 、BLACK };三叉链表左右 父节点便于迭代器的前后移动_data存储实际数据map为pairconst K,Vset为const K2.2 迭代器IteratorT, Ref, Ptrtemplate class T, class Ref, class Ptr class Iterator { Node* _node; Node* _root; // 用于 --end() };operator前置Self operator() { assert(_node ! nullptr); if (_node-_right)//右不为空 下一个节点就是 此右子树的 最左节点 { Node* leftMost _node-_right; while (leftMost-_left) { leftMost leftMost-_left;//找到左子树最小节点 } _node leftMost; } else//右为空 检查上一个父亲节点是祖父节点的左还是右节点--左则_node parent 右则往上一直走 直到是上一个节点的左节点或者是根节点 { Node* cur _node; Node* parent cur-_parent; while (parent parent-_right cur) { cur parent; parent cur-_parent; } _node parent; } return *this; }有右孩子 → 右子树的最左节点无右孩子 → 向上回溯直到当前节点是父节点的左孩子operator--前置Self operator--()// 左 中 右--》右 中 左 { if (_node nullptr) { Node* cur _root; while (cur cur-_right)//加判空 防止空树 { cur cur-_right; } _node cur; return *this; } if (_node-_left)//左不为空 下一个节点就是 此左子树的 最右节点 { Node* rightMin _node-_left; while (rightMin-_right) { rightMin rightMin-_right;//找到右子树最大节点 } _node rightMin; } else//左为空 检查上一个父亲节点是祖父节点的左还是右节点--右则_node parent 右则往上一直走 直到是上一个节点的左节点或者是根节点 { Node* cur _node; Node* parent cur-_parent; while (parent parent-_left cur) { cur parent; parent cur-_parent; } _node parent; } return *this; }有左孩子 → 左子树的最右节点无左孩子 → 向上回溯直到当前节点是父节点的右孩子如果_node nullptr即end()回退到整棵树的最大节点面试常问迭代器递增/递减的时间复杂度是多少平均 O(1)整体中序遍历整棵树为 O(N)三、红黑树封装3.1 模板参数设计templateclass K, class T, class KeyofT class RBTreeK键类型T节点存储的数据类型map为pairconst K,Vset为const KKeyofT仿函数用于从T中提取KKeyofT的作用统一比较逻辑使红黑树无需关心T的具体结构3.2 插入操作Insert返回类型pairiterator, bool.first插入位置或已存在节点的迭代器.secondtrue表示插入成功false表示键已存在插入后需要调整颜色和旋转维持红黑树性质成功插入后_size维护节点计数面试常问为什么Insert要返回pairiterator, bool为了支持operator[]它需要知道插入是否成功并能返回新插入或已存在元素的引用pairiterator,bool Insert(const T key) { if (_root nullptr) { _root new Node(key); _root-_col BLACK; _size; return {iterator(_root,_root),true}; } //空树插入情况单独考虑 Node* cur _root; Node* parent nullptr; while (cur) { if (kot(cur-_data) kot(key)) { parent cur; cur cur-_right; } else if (kot(cur-_data) kot(key)) { parent cur; cur cur-_left; } else return { iterator(cur,_root),false }; } //循环结束 说明已经找到需要插入的位置 cur new Node(key); cur-_col RED; Node* newnode cur; if (kot(parent-_data) kot(cur-_data)) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent;//前面也只是 对于父亲的指针做了更改 //确定cur的是父亲节点左还是右 while (parent parent-_col RED) { Node* grandfather parent-_parent; if (parent grandfather-_left) { Node* uncle grandfather-_right; if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else//叔叔节点不存在或者节点颜色为黑的情况--这意味着红色节点连续且无法通过变色直接解决 需要旋转 { if (cur parent-_left)//从整体上来看 用特殊情况替代一般情况 { RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { Node* uncle grandfather-_left; if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { if (cur parent-_left) { RotateR(parent); RotateL(grandfather); cur-_col RED; grandfather-_col BLACK; } else { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } break; } } } _size; _root-_col BLACK;//最后把_root 的颜色置为黑 肯定没问题 return { iterator(newnode,_root),true }; }3.3 查找操作Find返回iterator或const_iterator找不到返回end()即iterator(nullptr, _root)面试常问为什么find找不到要返回end()而不是nullptr统一接口所有 STL 容器都这么设计用户统一用if (it ! container.end())判断iterator _Find(Node* root,const K key) { Node* cur root; while (cur) { if (key kot(cur-_data)) { cur cur-_right; } else if (key kot(cur-_data)) { cur cur-_left; } else { return iterator(cur, _root);//构造一个迭代器 需要传的参数 这里要自己去参考迭代器的构造函数 } } return iterator(nullptr,_root); } const_iterator _Find(Node* root,const K key) const { Node* cur root; while (cur) { if (key kot(cur-_data)) { cur cur-_right; } else if (key kot(cur-_data)) { cur cur-_left; } else { return const_iterator(cur, _root);//构造一个迭代器 需要传的参数 这里要自己去参考迭代器的构造函数 } } return const_iterator(nullptr,_root); }3.4 旋转函数RotateL/RotateR左旋和右旋是红黑树调整的核心操作注意更新父节点指针和子节点指针的双向链接具体代码 参考AVL树的实现3.5 资源管理RAII// 强制使用默认构造 RBTree() default; // 析构函数 ~RBTree() { _Destroy(_root); } // 拷贝构造 --深拷贝 RBTree(const RBTree other) : _root(nullptr), _size(other._size) { _root _Copy(other._root); } // 赋值运算符 RBTree operator(const RBTree other) { if (this ! other) { _Destroy(_root); _root _Copy(other._root); _size other._size; } return *this; } // 节点数量 size_t Size() const { return _size; } bool Empty() const { return _root nullptr; }辅助函数_Destroy(Node* root)递归释放整棵树_Copy(Node* root)递归深拷贝整棵树注意拷贝时保留颜色和父指针面试常问如果不实现拷贝构造和赋值会发生什么默认浅拷贝会导致多个对象共享同一棵树修改一个会影响另一个引发内存泄漏或重复释放双重释放四、容器封装map和set4.1 Map 封装namespace JMP2 { template class K, class V class map { struct MapKeyofT { const K operator()(const pairconst K,V kv) const { return kv.first; } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyofT::iterator iterator;//在类里面 取没有确定的类模板成员 要加 typename typedef typename RBTreeK, pairconst K, V, MapKeyofT::const_iterator const_iterator; public: pairiterator,bool insert(const pairK, V kv)//具体插入什么根据具体容器决定 { return _rb.Insert(kv); } iterator begin() { return _rb.begin(); } const_iterator begin() const { return _rb.begin(); } iterator end() { return _rb.end(); } const_iterator end() const { return _rb.end(); } iterator find(const K kv) { return _rb.Find(kv); } const_iterator find(const K kv) const { return _rb.Find(kv); } V operator[](const K key) { pairiterator, bool ret insert(make_pair(key, V())); return ret.first-second; } size_t Size() const { return _rb.Size(); } bool Empty() const { return _rb.Empty(); } private: RBTree K, pairconst K,V, MapKeyofT _rb; }; }4.2 Set 封装namespace JMP1 { template class K class set { struct SetKeyofT { const K operator()(const K key) const { return key; } }; public: //要明白 typename的作用 编译器默认认为 依赖名::xxx 不是类型而是变量或函数 typedef typename RBTreeK, const K, SetKeyofT::iterator iterator;//编译器猜不出来 标准就规定 如果这确实是一个类型必须显式地用 typename 关键字告诉编译器 typedef typename RBTreeK, const K, SetKeyofT::const_iterator const_iterator; public: pairiterator, bool Insert(const K key)//具体插入什么根据具体容器决定 { return _rb.Insert(key); } iterator begin() { return _rb.begin(); } const_iterator begin() const { return _rb.begin(); } iterator end() { return _rb.end(); } const_iterator end() const { return _rb.end(); } iterator find(const K key) { return _rb.Find(key); } const_iterator find(const K key) const { return _rb.Find(key); } size_t Size() const { return _rb.Size(); } bool Empty() const { return _rb.Empty(); } private: RBTree K, const K, SetKeyofT _rb;//前面两个是重复的 之所以这么设计是因为 要兼顾map的实现 }; }六、踩坑记录坑1MapKeyofT参数类型不匹配错误operator()(const pairK,V kv)但树节点存储的是pairconst K,V解决改为operator()(const pairconst K,V kv)坑2kot(key)错误用法错误在Find中写kot(key) kot(cur-_data)解决直接key kot(cur-_data)因为key已经是K类型不需要再提取坑3拷贝构造忘记复制_size错误拷贝构造只复制了树结构没有复制_size解决初始化列表加_size(other._size)坑4赋值运算符未检查自赋值解决加if (this ! other)七、总结通过完整的手写红黑树及其封装深入理解红黑树的核心性质与调整逻辑迭代器的设计与实现模板与仿函数在容器封装中的应用RAII资源管理的必要性--内存关系STL 容器的标准接口设计规范八、面试高频问题汇总Q1红黑树插入有几种情况新节点为根 → 直接染黑父节点为黑 → 直接插入无需调整父节点为红需要调整叔叔为红→ 变色父、叔变黑祖父变红继续往上检查。叔叔为黑或不存在→ 旋转 变色LL型 → 右旋祖父RR型 → 左旋祖父LR型 → 左旋父 右旋祖父RL型 → 右旋父 左旋祖父Q2迭代器失效问题插入操作不导致任何已有迭代器失效节点地址不变删除操作指向被删除节点的迭代器失效拷贝构造/赋值与源对象无关不影响已有迭代器Q3map和unordered_map底层区别map红黑树有序查询 O(log N)unordered_map哈希表无序查询 O(1) 平均最坏 O(N)Q4为什么map的键是const防止用户通过迭代器修改键破坏红黑树的有序性。Q5find返回end()而不是nullptr的好处统一接口所有 STL 容器都这么设计用户代码可以写成统一风格if (it ! container.end())。Q6深拷贝和浅拷贝的区别浅拷贝默认拷贝构造/赋值只复制指针多个对象共享同一块内存深拷贝复制整个数据结构每个对象独立管理自己的资源我们的实现_Copy递归复制整棵树保证每个RBTree对象独立我的gitee仓库https://gitee.com/jiangmingpeng0716/c-learning-process