网站导航
> 技术文档 > C++之利用红黑树作为底层，实现对set和map的封装（难）

C++之利用红黑树作为底层，实现对set和map的封装（难）

网友: 技术文档 2025-07-30 11:24:50

模拟封装map和set

  • 一.回顾红黑树
  • 二.模拟实现map和set
    • 2.1复⽤红⿊树,实现insert
      • 结构体 SetKeyOfT
      • 结构体 MapKeyOfT
    • 2.2⽀持iterator的实现
      • 迭代器具体实现部分
      • 上层迭代器操作
      • 普通迭代器与const迭代器
        • map与set
        • 红黑树
      • 1. 前缀递增操作符 `++`
      • 2. 前缀递减操作符 `--`
      • 示例
        • 前缀递增操作符 `++`
        • 前缀递减操作符 `--`
    • 2.3map操作符[]
      • 代码解析
        • 成员变量和函数
        • 详细步骤
      • 详细解释
        • 情况1：键已存在
        • 情况2：键不存在
    • 2.4其余操作
      • 控制map中K不可修改,V可以修改
      • 上层insert和find操作
  • 三.代码总览
    • mymap部分
    • myset部分
    • 红黑树部分

请添加图片描述

一.回顾红黑树

红黑树是一种自平衡的二叉查找树，它在普通的二叉查找树基础上增加了着色规则来保证树的平衡性，从而确保各种操作（如查找、插入、删除等）的时间复杂度都能维持在对数级别。红黑树的节点是红色或黑色，它需要满足以下五条性质：

  1. 节点是红色或黑色：每个节点都有一个颜色属性，红色或黑色。
  2. 根节点是黑色：树的根节点必须是黑色。
  3. 叶子节点是黑色：叶子节点（即空节点或NIL节点）是黑色。
  4. 红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点都是黑色，即不能有两个连续的红色节点。
  5. 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点：从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点，这保证了树的平衡性。

以下是旧文代码实现：

enum Colour{RED,BLACK};// red blacktemplate<class K, class V>struct RBTreeNode{// 需要parent指针，后续更新平衡因子可以看到pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public: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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 1、u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else // 2、u不存在或者u存在且为黑{if (cur == parent->_left){// g// p u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // (parent == grandfather->_right){Node* uncle = grandfather->_left;// 1、u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else // 2、u不存在或者u存在且为黑{if (cur == parent->_right){// g// u p // cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时，意味着一条路径走完了if (blackNum != refNum){cout << \"存在黑色结点的数量不相等的路径\" << endl;return false;}return true;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << \"存在连续的红色结点\" << endl;return false;}if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}bool IsBalanceTree(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}private:int _Size(Node* root){return root == nullptr ? 0 :_Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << \" \";_InOrder(root->_right);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}private:Node* _root = nullptr;};

二.模拟实现map和set

2.1复⽤红⿊树,实现insert

其次因为RBTree实现了泛型不知道T参数导致是K，还是pair，那么insert内部进⾏插⼊逻辑⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任何时候只⽐较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较。
myset:

template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};

结构体 SetKeyOfT

struct SetKeyOfT{ const K& operator()(const K& key) { return key; }};
  • 作用：SetKeyOfT 是一个函数对象，它用于从元素中提取键。在红黑树中，每个节点存储的是元素本身，但树的结构需要根据元素的值来进行排序和查找。因此，需要一个函数对象来提取元素的值。
  • 实现：通过重载 operator()，SetKeyOfT 可以将一个元素 K 转换为键 K。具体来说，它直接返回元素本身，因为 set 中的元素本身就是键。
    mymap:
template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};

结构体 MapKeyOfT

struct MapKeyOfT{ const K& operator()(const pair<K, V>& kv) { return kv.first; }};
  • 作用：MapKeyOfT 是一个函数对象，它用于从键值对中提取键。在红黑树中，每个节点存储的是键值对，但树的结构需要根据键来进行排序和查找。因此，需要一个函数对象来提取键。
  • 实现：通过重载 operator()，MapKeyOfT 可以将一个键值对 pair 转换为键 K。具体来说，它返回键值对的第一个元素 kv.first。

所以，之后所用红黑树里用key进行比较大小的地方，都要用上述函数带换，
包括在set和map传参时，都要将所实现的各自的KeyOfT,传给模板参数。

template<class K, class T, class KeyOfT>typedef RBTreeNode<T> Node;public:bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return false;}}// 新插入红色节点cur = new Node(data);cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 1、u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else // 2、u不存在或者u存在且为黑{if (cur == parent->_left){// g// p u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // (parent == grandfather->_right){Node* uncle = grandfather->_left;// 1、u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else // 2、u不存在或者u存在且为黑{if (cur == parent->_right){// g// u p // cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

2.2⽀持iterator的实现

iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为。但是由于底层是由红黑树所实现的，底层是树状结构，就注定了迭代器的++ 与 --操作与之前是相异的,其是按照中序遍历的顺序进行++ -- 的

迭代器具体实现部分

template<class T, class Ref, class Ptr>struct RBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){// 1、当前节点的右不为空// 下一个就是右子树中序第一个（最左节点）Node* minLeft = _node->_right;while (minLeft->_left){minLeft = minLeft->_left;}_node = minLeft;}else{// 2、当前节点的右为空// 下一个是当前节点的祖先，孩子是父亲左那个祖先Node* cur = _node;Node* parent = cur->_parent;// parent为空，cur是根，说明当前树走完了，// nullptr给_node，nullptr做end()while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr){// --end()，到最右节点Node* maxRight = _root;while (maxRight && maxRight->_right){maxRight = maxRight->_right;}_node = maxRight;}else if (_node->_left){// 左子树不为空，中序左子树最后一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}bool operator==(const Self& s) const{return _node == s._node;}bool operator!=(const Self& s) const{return _node != s._node;}};

上层迭代器操作

iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}

为实现普通迭代器，以及const迭代器两种情况
需要在底层设置三个模板参数

普通迭代器与const迭代器

map与set
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>,MapKeyOfT>::ConstIterator const_iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

typename 的作用：

  1. 指示嵌套依赖类型：RBTree::Iterator 和 RBTree::ConstIterator 是嵌套在模板类RBTree中的类型。由于RBTree是模板类，其嵌套类型可能依赖于模板参数（如K和V），因此编译器默认认为这些名称可能是静态成员变量或枚举值。
  2. typename 强制编译器将Iterator和ConstIterator解释为类型。
红黑树
typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

通过是否使用const，实现两个版本的迭代器，也使得在map和set上层，可以调用的两个版本的迭代器。

1. 前缀递增操作符 ++

前缀递增操作符 ++ 用于将迭代器移动到下一个节点。在红黑树的中序遍历中，下一个节点是当前节点的中序后继。具体实现如下：

Self& operator++(){ if (_node->_right) { // 1、当前节点的右不为空 // 下一个就是右子树中序第一个（最左节点） Node* minLeft = _node->_right; while (minLeft->_left) { minLeft = minLeft->_left; } _node = minLeft; } else { // 2、当前节点的右为空 // 下一个是当前节点的祖先，孩子是父亲左的那个祖先 Node* cur = _node; Node* parent = cur->_parent; // parent为空，cur是根，说明当前树走完了， // nullptr给_node，nullptr做end() while (parent && cur == parent->_right) { cur = parent; parent = parent->_parent; } _node = parent; } return *this;}

  1. 右子树不为空：

    • 如果当前节点的右子树不为空，下一个节点是右子树中最左边的节点（即右子树的中序第一个节点）。
    • 从当前节点的右子节点开始，沿着左子树一直向下，直到找到最左边的节点。
    • 将 _node 更新为这个最左边的节点。

  2. 右子树为空：

    • 如果当前节点的右子树为空，下一个节点是当前节点的祖先，且当前节点是其祖先的右孩子。
    • 从当前节点开始，沿着父节点向上查找，直到找到一个节点，该节点是其父节点的左孩子。
    • 如果找到了这样的节点，将 _node 更新为该节点的父节点。
    • 如果没有找到（即当前节点是树的最右节点），将 _node 设置为 nullptr，表示迭代器已经到达了树的末尾（end()）。

2. 前缀递减操作符 --

前缀递减操作符 -- 用于将迭代器移动到上一个节点。在红黑树的中序遍历中，上一个节点是当前节点的中序前驱。具体实现如下：

Self& operator--(){ if (_node == nullptr) { // --end()，到最右节点 Node* maxRight = _root; while (maxRight && maxRight->_right) { maxRight = maxRight->_right; } _node = maxRight; } else if (_node->_left) { // 左子树不为空，中序左子树最后一个 Node* rightMost = _node->_left; while (rightMost->_right) { rightMost = rightMost->_right; } _node = rightMost; } else { // 孩子是父亲右的那个祖先 Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = parent; parent = cur->_parent; } _node = parent; } return *this;}

  1. 当前节点为空：

    • 如果当前节点为空（即 end()），则需要找到树中最右边的节点（即中序遍历的最后一个节点）。
    • 从根节点开始，沿着右子树一直向下，直到找到最右边的节点。
    • 将 _node 更新为这个最右边的节点。

  2. 左子树不为空：

    • 如果当前节点的左子树不为空，上一个节点是左子树中最右边的节点（即左子树的中序最后一个节点）。
    • 从当前节点的左子节点开始，沿着右子树一直向下，直到找到最右边的节点。
    • 将 _node 更新为这个最右边的节点。

  3. 左子树为空：

    • 如果当前节点的左子树为空，上一个节点是当前节点的祖先，且当前节点是其祖先的左孩子。
    • 从当前节点开始，沿着父节点向上查找，直到找到一个节点，该节点是其父节点的右孩子。
    • 将 _node 更新为该节点的父节点。

示例

假设我们有以下红黑树：

 8(B) / \\ 3(R) 10(B) / \\ \\ 1(B) 6(B) 14(R) / \\ / 4(R) 7(R)13(B)
前缀递增操作符 ++

  1. 当前节点为 3：

    • 右子树不为空，下一个节点是右子树中最左边的节点。
    • 从 3 的右子节点 6 开始，沿着左子树向下，找到 4。
    • _node 更新为 4。

  2. 当前节点为 4：

    • 右子树为空，下一个节点是其祖先，且当前节点是其祖先的右孩子。
    • 从 4 开始，沿着父节点向上，找到 6。
    • _node 更新为 6。

  3. 当前节点为 6：

    • 右子树不为空，下一个节点是右子树中最左边的节点。
    • 从 6 的右子节点 7 开始，沿着左子树向下，找到 7。
    • _node 更新为 7。

  4. 当前节点为 7：

    • 右子树为空，下一个节点是其祖先，且当前节点是其祖先的右孩子。
    • 从 7 开始，沿着父节点向上，找到 8。
    • _node 更新为 8。
前缀递减操作符 --

  1. 当前节点为 8：

    • 左子树不为空，上一个节点是左子树中最右边的节点。
    • 从 8 的左子节点 3 开始，沿着右子树向下，找到 6。
    • _node 更新为 6。

  2. 当前节点为 6：

    • 左子树不为空，上一个节点是左子树中最右边的节点。
    • 从 6 的左子节点 4 开始，沿着右子树向下，找到 4。
    • _node 更新为 4。

  3. 当前节点为 4：

    • 左子树为空，上一个节点是其祖先，且当前节点是其祖先的左孩子。
    • 从 4 开始，沿着父节点向上，找到 3。
    • _node 更新为 3。

  4. 当前节点为 3：

    • 左子树为空，上一个节点是其祖先，且当前节点是其祖先的左孩子。
    • 从 3 开始，沿着父节点向上，找到 1。
    • _node 更新为 1。

2.3map操作符[]

代码解析

V& operator[](const K& key){ pair<iterator, bool> ret = _t.Insert({ key, V() }); iterator it = ret.first; return it->second;}
成员变量和函数
  • _t：这是一个红黑树对象，存储了map的所有键值对。
  • Insert：这是红黑树的一个成员函数，用于插入一个新的键值对。它返回一个pair，其中first是一个迭代器，指向插入的节点或已存在的相同键的节点；second是一个布尔值，表示是否成功插入（true表示插入成功，false表示键已存在）。
详细步骤

  1. 插入操作：

    pair<iterator, bool> ret = _t.Insert({ key, V() });
    • 这里调用了红黑树的Insert方法，尝试插入一个新的键值对{key, V()}。V()是值类型的默认构造函数，用于创建一个默认值。
    • Insert方法返回一个pair，其中first是一个迭代器，指向插入的节点或已存在的相同键的节点；second是一个布尔值，表示是否成功插入。

  2. 获取迭代器：

    iterator it = ret.first;
    • 从Insert方法返回的pair中获取迭代器it，它指向插入的节点或已存在的相同键的节点。

  3. 返回值的引用：

    return it->second;
    • 通过迭代器it访问节点的值（it->second），并返回这个值的引用。如果键已存在，返回已存在的值的引用；如果键不存在，返回新插入的默认值的引用。

详细解释

情况1：键已存在
  • 当Insert方法尝试插入一个已存在的键时，它不会插入新的节点，而是返回一个迭代器，指向已存在的节点，以及一个布尔值false。
  • 在这种情况下，it->second将返回已存在的值的引用。
情况2：键不存在
  • 当Insert方法尝试插入一个不存在的键时，它会插入一个新的节点，并返回一个迭代器，指向新插入的节点，以及一个布尔值true。
  • 在这种情况下，it->second将返回新插入的默认值的引用。

2.4其余操作

控制map中K不可修改,V可以修改

// pair可以修改，pair的K类型用const修饰，保证key不能被修改RBTree<K, pair<const K, V>, MapKeyOfT> _t;

上层insert和find操作

map::pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}set::pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}

这里主要强调的是insert的返回值，和 下层一样，是一个pair;
返回一个 pair，其中 first 是一个迭代器，指向插入的节点或已存在的相同键的节点；second 是一个布尔值，表示是否成功插入（true 表示插入成功，false 表示键已存在）。

三.代码总览

mymap部分

template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::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(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}// 11:40V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert({ key, V() });iterator it = ret.first;return it->second;}private:// pair可以修改，pair的K类型用const修饰，保证key不能被修改RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void Print(const map<string, string>& m){for (auto& e : m){cout << e.first << \":\" << e.second << endl;}}

myset部分

template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::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(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:// 第一个模板参数带const，保证key不能被修改RBTree<K, const K, SetKeyOfT> _t;};void Print(const set<int>& s){set<int>::const_iterator it = s.end();while (it != s.begin()){--it;//*it += 10;cout << *it << \" \";}cout << endl;}

红黑树部分

enum Colour{RED,BLACK};// red blacktemplate<class T>struct RBTreeNode{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template<class T, class Ref, class Ptr>struct RBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){// 1、当前节点的右不为空// 下一个就是右子树中序第一个（最左节点）Node* minLeft = _node->_right;while (minLeft->_left){minLeft = minLeft->_left;}_node = minLeft;}else{// 2、当前节点的右为空// 下一个是当前节点的祖先，孩子是父亲左那个祖先Node* cur = _node;Node* parent = cur->_parent;// parent为空，cur是根，说明当前树走完了，// nullptr给_node，nullptr做end()while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr){// --end()，到最右节点Node* maxRight = _root;while (maxRight && maxRight->_right){maxRight = maxRight->_right;}_node = maxRight;}else if (_node->_left){// 左子树不为空，中序左子树最后一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}bool operator==(const Self& s) const{return _node == s._node;}bool operator!=(const Self& s) const{return _node != s._node;}};template<class K, class T, class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* minLeft = _root;while (minLeft && minLeft->_left){minLeft = minLeft->_left;}return Iterator(minLeft, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* minLeft = _root;while (minLeft && minLeft->_left){minLeft = minLeft->_left;}return ConstIterator(minLeft, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return {Iterator(_root, _root), true};}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return {Iterator(cur, _root), false};}}// 新插入红色节点cur = new Node(data);Node* newNode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 1、u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else // 2、u不存在或者u存在且为黑{if (cur == parent->_left){// g// p u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // (parent == grandfather->_right){Node* uncle = grandfather->_left;// 1、u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else // 2、u不存在或者u存在且为黑{if (cur == parent->_right){// g// u p // cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return { Iterator(newNode, _root), true };}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Iterator Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur, _root);}}return End();}private:int _Size(Node* root){return root == nullptr ? 0 :_Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << \" \";_InOrder(root->_right);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}private:Node* _root = nullptr;};

在这里插入图片描述

网络标签：

相关问题