这个问题需要单独处理

发布时间：2025-06-24 20:18:53  作者：北方职教升学中心  阅读量：492


那假设 it 到达6节点上呢，6的右为空，但是根据中序遍历的顺序，6的父亲1已经访问过了。但是在本篇文章中由于展示等的原因，无法按照上面的步骤。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key 数据。

map 中 pair 的 first 不能修改，second 可以修改，在 pair 的第一个参数前加 const 即可。

在改造红黑树的过程中，我大概归纳了以下几个需要重点解决的问题：

(1) 对红黑树节点的改造。

说明：如果大家要自己动手实现封装，可以按照上面五个问题的流程进行实现。

MySet.h

#include"RBTree.h"namespace cc{template<class K>class set	{// 获取 set 里面的 keystructSetOfT{constK&operator()(constK&key){returnkey;}};public:typedeftypename RBTree<K,constK,SetOfT>::Iterator iterator;typedeftypename RBTree<K,constK,SetOfT>::ConstIterator const_iterator;iterator begin(){return_t.Begin();}iterator end(){return_t.End();}const_iterator begin()const{return_t.Begin();}const_iterator end()const{return_t.End();}pair<iterator,bool>insert(constK&key){return_t.Insert(key);}iterator find(constK&key){return_t.Find(key);}private:RBTree<K,constK,SetOfT>_t;};}//使用 const 迭代器 voidPrint(constcc::set<int>&s){autoit =s.begin();while(it !=s.end()){cout <<*it <<" ";++it;}cout <<endl;}//测试代码voidTest_set(){//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };inta[]={16,3,7,11,9,26,18,14,15};cc::set<int>s;for(autoe :a)s.insert(e);for(autoe :s)cout <<e <<" ";cout <<endl;Print(s);}

在这里插入图片描述

七，map 的封装实现

map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可。

为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可。

MyMap.h

#include"RBTree.h"namespace cc{template<class K,class V>class map	{//获取 pair 中的 keystructMapOfT{constK&operator()(constpair<K,V>&kv){returnkv.first;}};public:typedeftypename RBTree<K,pair<constK,V>,MapOfT>::Iterator iterator;typedeftypename RBTree<K,pair<constK,V>,MapOfT>::ConstIterator const_iterator;iterator begin(){return_t.Begin();}iterator end(){return_t.End();}const_iterator begin()const{return_t.Begin();}const_iterator end()const{return_t.End();}pair<iterator,bool>insert(constpair<K,V>&kv){return_t.Insert(kv);}iterator find(constK&key){return_t.Find(key);}//给一个key，返回value的引用V&operator[](constK&key){pair<iterator,bool>ret =insert(make_pair(key,V()));returnret.first->second;}private:RBTree<K,pair<constK,V>,MapOfT>_t;};}//测试代码voidTest_map(){cc::map<string,string>dict;dict.insert({"left","左边"});dict.insert({"right","右边"});dict.insert({"insert","插入"});dict["left"]="剩余，左边";cc::map<string,string>::iterator it =dict.begin();while(it !=dict.end()){//it->first += 'x'; //errit->second +='y';//okcout <<it->first <<":"<<it->second <<endl;++it;}cout <<endl;}

在这里插入图片描述

Iterator Find(constK&key){Node*cur =_root;while(cur){if(cur->_data >key)cur =cur->_left;elseif(cur->_data <key)cur =cur->_right;elsereturnIterator(cur);}returnEnd();}

4.2 Insert 函数的改造

map 里的 operator[] 需要依赖 Insert 的返回值

pair<Iterator,bool>Insert(constT&data){if(_root ==nullptr){_root =new Node(data);returnmake_pair(Iterator(_root),true);}KeyOfT kot;Node*cur =_root;Node*parent =nullptr;while(cur){if(kot(cur->_data)>kot(data)){parent =cur;cur =cur->_left;}elseif(kot(cur->_data)<kot(data)){parent =cur;cur =cur->_right;}elsereturnmake_pair(Iterator(cur),false);}cur =new Node(data);Node*newnode =cur;//此处省略变色+旋转部分的代码……

五，红黑树改造的完整代码

说明：由于代码太长，影响展示效果，所以插入部分的 变色+旋转 的代码此处省略，和红黑树的基本一模一样，请前往【C++】：红黑树深度剖析 — 手撕红黑树！

RBTree.h

#include<iostream>#include<assert.h>using namespace std;//枚举颜色enumColour{RED,BLACK};//节点类template <class T>structRBTreeNode{T _data;RBTreeNode<T>*_left;RBTreeNode<T>*_right;RBTreeNode<T>*_parent;//pair<K, V> _kv;Colour _col;RBTreeNode(constT&data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(BLACK){}};//迭代器类template <class T,class Ref,class Ptr>structRBTreeIterator{typedefRBTreeNode<T>Node;typedefRBTreeIterator<T,Ref,Ptr>Self;Node*_node;RBTreeIterator(Node*node):_node(node){}bool operator!=(constSelf&s){returns._node !=_node;}Ref operator*(){return_node->_data;}Ptr operator->(){return&_node->_data;}//从局部的某一个过程考虑Self&operator++(){if(_node->_right){//右不为空，右子树的最左节点就是下一个访问的节点Node*leftMost =_node->_right;while(leftMost->_left)leftMost =leftMost->_left;_node =leftMost;}else{//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点Node*cur =_node;Node*parent =cur->_parent;//循环找祖先while(parent &&cur ==parent->_right){cur =parent;parent =parent->_parent;}_node =parent;}return*this;}};//K 是给find，erase用的，T 是给节点，插入用的// KeyOfT 是由于下面需要比较，但是比较时不知道T的类型，// set是key类型的比较，map是pair类型的比较，要统一变成key的比较template <class K,class T,class KeyOfT>class RBTree{typedefRBTreeNode<T>Node;public:typedefRBTreeIterator<T,T&,T*>Iterator;typedefRBTreeIterator<T,constT&,constT*>ConstIterator;//中序遍历，找树的最左节点Iterator Begin(){//Node* cur = _root;Node*leftMost =_root;while(leftMost->_left)leftMost =leftMost->_left;returnIterator(leftMost);}Iterator End(){returnIterator(nullptr);}ConstIterator Begin()const{//Node* cur = _root;Node*leftMost =_root;while(leftMost->_left)leftMost =leftMost->_left;returnConstIterator(leftMost);}ConstIterator End()const{returnConstIterator(nullptr);}Iterator Find(constK&key){Node*cur =_root;while(cur){if(cur->_data >key)cur =cur->_left;elseif(cur->_data <key)cur =cur->_right;elsereturnIterator(cur);}returnEnd();}pair<Iterator,bool>Insert(constT&data){if(_root ==nullptr){_root =new Node(data);returnmake_pair(Iterator(_root),true);}KeyOfT kot;Node*cur =_root;Node*parent =nullptr;while(cur){if(kot(cur->_data)>kot(data)){parent =cur;cur =cur->_left;}elseif(kot(cur->_data)<kot(data)){parent =cur;cur =cur->_right;}elsereturnmake_pair(Iterator(cur),false);}cur =new Node(data);Node*newnode =cur;//新增节点，颜色为红色cur->_col =RED;//此处省略变色+旋转部分的代码……private:Node*_root =nullptr;};

六，set 的封装实现

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。这个问题需要单独处理。

右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先，是哪个祖先呢？沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点。

点击跳转至文章：【C++】：红黑树深度剖析 — 手撕红黑树！

目录

  • 前言
  • 一，红黑树的改造
    • 1. 红黑树的主体框架
    • 2. 对红黑树节点结构的改造
    • 3. 红黑树的迭代器
      • 3.1 迭代器类
      • 3.2 Begin() 和 End()
  • 四，红黑树相关接口的改造
    • 4.1 Find 函数的改造
    • 4.2 Insert 函数的改造
  • 五，红黑树改造的完整代码
  • 六，set 的封装实现
  • 七，map 的封装实现

前言

map 和 set 的底层本质上还是复用，通过对红黑树的改造，再分别套上一层 map 和 set 的 “壳子”，以达到 “一树二用” 的目的。如何用一个节点结构控制两种类型，使用类模板参数T。由于我们的节点类型的泛型，如果是 set 则是 K，如果是map，则为pair<K, V>，而pair的比较是由 first 和 second 共同决定的，这显然不符合要求。

(2) 在插入操作时，如何完成数据的比较。

template <class K,class T,class KeyOfT>class RBTree{typedefRBTreeNode<T>Node;//节点public:typedefRBTreeIterator<T,T&,T*>Iterator;//普通迭代器typedefRBTreeIterator<T,constT&,constT*>ConstIterator;//const 迭代器//其他功能的实现……private:Node*_root =nullptr;};

2. 对红黑树节点结构的改造

//枚举颜色enumColour{RED,BLACK};//节点类template <class T>structRBTreeNode{T _data;RBTreeNode<T>*_left;RBTreeNode<T>*_right;RBTreeNode<T>*_parent;//pair<K, V> _kv;Colour _col;RBTreeNode(constT&data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(BLACK){}};

3. 红黑树的迭代器

3.1 迭代器类

//迭代器类template <class T,class Ref,class Ptr>structRBTreeIterator{typedefRBTreeNode<T>Node;typedefRBTreeIterator<T,Ref,Ptr>Self;Node*_node;RBTreeIterator(Node*node):_node(node){}bool operator!=(constSelf&s){returns._node !=_node;}Ref operator*(){return_node->_data;}Ptr operator->(){return&_node->_data;}//从局部的某一个过程考虑Self&operator++(){if(_node->_right){//右不为空，右子树的最左节点就是下一个访问的节点Node*leftMost =_node->_right;while(leftMost->_left)leftMost =leftMost->_left;_node =leftMost;}else{//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点Node*cur =_node;Node*parent =cur->_parent;//循环找祖先while(parent &&cur ==parent->_right){cur =parent;parent =parent->_parent;}_node =parent;}return*this;}};

迭代器中最复杂的就是 operator++()的实现，它与原先的 vector/list 不同，红黑树的迭代器是要完成二叉树的中序遍历。

(a) 假设此时走到了15节点，下一个访问的节点是17，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点；

在这里插入图片描述

(b) 假设此时走到了6节点，下一个访问的节点是8，但是此时 cur 是 parent 的右，不满足条件，继续向上查找，cur = parent，parent = parent->_parent，这时 cur 在1，parent 在8，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点

在这里插入图片描述

3.2 Begin() 和 End()

//中序遍历，找树的最左节点Iterator Begin(){//Node* cur = _root;Node*leftMost =_root;while(leftMost->_left)leftMost =leftMost->_left;returnIterator(leftMost);}Iterator End(){returnIterator(nullptr);}ConstIterator Begin()const{//Node* cur = _root;Node*leftMost =_root;while(leftMost->_left)leftMost =leftMost->_left;returnConstIterator(leftMost);}ConstIterator End()const{returnConstIterator(nullptr);}Iterator Find(constK&key){Node*cur =_root;while(cur){if(cur->_data >key)cur =cur->_left;elseif(cur->_data <key)cur =cur->_right;elsereturnIterator(cur);}returnEnd();}

四，红黑树相关接口的改造

4.1 Find 函数的改造

查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。

为了完成二叉树的中序遍历，我们需要从局部的某一过程考虑，就是假设 it 已经走到了某一节点，要找到下一个访问的节点，分为两种情况：

(1) 当前节点的右子树不为空：

如下图，假设 it 已经到达了13节点，说明此时13的左子树已经访问完了，右子树不为空，下一个要访问的节点就是右子树的最左节点15

在这里插入图片描述

(2) 当前节点的右子树为空：

如下图，假设 it 此时到达了15节点，它的右子树为空，下一个访问哪个节点呢？有些人单纯的认为是15的父亲17，其实是错误的。

(3) 在红黑树中实现普通迭代器和const迭代器，再套上 “壳子”。

在这里插入图片描述

其实此时是要找当前节点的祖先，父亲也是祖先之一。

(4) 关于 key 的修改问题。关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是 set 则是 K，如果是map，则为pair<K, V>。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。

一，红黑树的改造

1. 红黑树的主体框架

(1) K 是给find，erase用的，T 是给节点，insert用的；

(2) KeyOfT 是由于下面需要比较，但是比较时不知道T的类型， set是key类型的比较，map是pair类型的比较，要统一变成key的比较。

(5) 红黑树相关接口的改造。

上一篇：大疆新产品发布会日期临近临近 消息人士称或发布SDR技术产品
下一篇：Java离线视频提取音频+音频提取文案