AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

红黑树封装实现STL-map、set

2024-02-06 40
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 红黑树封装实现STL-map、set

利用红黑树作为模板封装的思路

将红黑树作为一个基础的类模板，通过给这个类模板传递不同的参数，从而控制它所实现的容器。

最主要的点是用自己的map和set通过传递不同的模板参数控制红黑树第二个模板参数 T 来确定传入的到底是 Key 还是 pair<Key, Value> 类型的模板参数【泛型编程的思想】，如下图

红黑树的第二个参数T，通过传入参数的不同，控制红黑树中到底存储什么类型的变量。

给红黑树传的第三个模板参数 KeyOfT 是一个类，这个类中重载了 operator()，它实例化出的对象可以当做函数来使用，并且这个函数可以实现多种不同数据类型的大小比较，通过传进来类的不同，来使用不同的比较方式。

如图，KeyOfT示例化出的对象kot来进行树中的大小比较，当传 SetKeyOfT 时，就使用 key 作为比较依据；当传 MapKeyOfT 时，就使用 kv.first 作为大小比较依据。

迭代器的封装

首先，需要写一个迭代器的类模板，里面有迭代器变量主要需要使用的一些功能，如++，->，*，!=，==等等这些，通过传递不同的参数，来构造不同类型的迭代器。

迭代器的内部成员变量就是一个红黑树结点类型的指针，通过重载++，--，->等运算符作为成员函数。而模板参数传 Ref 和 Ptr 的原因是：当构造的是 const 类型或 非const 类型的迭代器时，编译器可以自己推导出返回值的类型。因为普通迭代器 iterator 和const类型的迭代器 const_iterator 不是同一个类型！

在红黑树中根据模板参数的不同重定义两个不同的迭代器：普通迭代器和 const 迭代器。当使用普通迭代器时，相当于给迭代器模板传<T, T&, T*>；当使用 const迭代器 时，相当于给迭代器模板传<T, const T&, const T*>

map 和 set 内部对于迭代器的处理

stl中 set 里的 key 不允许改变，因此无论是 iterator 还是 const_iterator，都需要使用红黑树中定义的 const_iterator 迭代器来初始化。

而map中，key不允许改变，T却可以改变，直接在模板参数中加 const 修饰K，普通迭代器用iterator，const 迭代器用 const_iterator修饰。

将insert 的返回值设置为 pair 类型，第一个 first 参数为 Node* 类型，因为无论是普通迭代器还是 const类型的迭代器，都是用 Node* 类型的变量来初始化的，只要是相近类型，pair的拷贝构造函数都能进行构造推导，推导为正确的类型！

代码实现

RBTree.h

#pragma once
#pragma once
#include<iostream>
#include<string>
#include<stdbool.h>
using namespace std;
typedef enum Color
{
  RED,  // 红色
  BLACK // 黑色
}Color;
template<class T>
struct RBTreeNode
{
  RBTreeNode(const T& data)
    :_right(nullptr)
    , _left(nullptr)
    , _parent(nullptr)
    , _col(RED)
    , _data(data)
  {}
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _parent;
  // 颜色：枚举类型
  Color _col;
  T _data;
};
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef __TreeIterator<T, Ref, Ptr> self;
  Node* _node;
  __TreeIterator(Node* node)
    :_node(node)
  {}
  self& operator--()
  {
    if (_node->_left)
    {
      Node* cur = _node->_left;
      while (cur->_right)
      {
        cur = cur->_right;
      }
      _node = cur;
    }
    else
    {
      // 等于空，说明当前结点已经访问结束了。
      // 向上回溯，直到孩子是父亲左节点的孩子
      Node* cur = _node;
      Node* parent = _node->_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
    {
      // 等于空，说明当前结点已经访问结束了。
      // 向上回溯，直到孩子是父亲左节点的孩子
      Node* cur = _node;
      Node* parent = _node->_parent;
      while (parent && cur == parent->_right)
      {
        cur = parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  bool operator==(const self& it)
  {
    return _node == it._node;
  }
  bool operator!=(const self& it)
  {
    return _node != it._node;
  }
  Ptr operator->()
  {
    return &_node->_data;
  }
  Ref operator*()
  {
    return _node->_data;
  }
};
template<class K, class T, class KeyOfT>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef __TreeIterator<T, T&, T*> iterator;
  typedef __TreeIterator<T, const T&, const T*> const_iterator;
  KeyOfT kot;
  iterator begin()
  {
    Node* cur = _root;
    while (cur->_left)
    {
      cur = cur->_left; /*_t = cur; // 这个 _t 是根节点，不能随便变*/
    }
    return iterator(cur); //return *this;迭代器这里不能返回引用
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  const_iterator begin() const
  {
    Node* cur = _root;
    while (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 (kot(cur->_data) < kot(data))
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (kot(cur->_data)> kot(data))
      {
        parent = cur;
        cur = cur->_left;
      }
      else // 相等
      {
        return make_pair(cur, false);
      }
    }
    cur = new Node(data); // 初始化的时候就是红色结点
    cur->_parent = parent;
    // 调整父子之间的关系
    if (kot(parent->_data) < kot(data))
      parent->_right = cur;
    else if (kot(parent->_data) > kot(data))
      parent->_left = cur;
    Node* grandparent = parent->_parent;
    while (parent && parent->_col == RED)
    {
      grandparent = parent->_parent;
      Node* uncle = nullptr;
      // 调整父亲和叔叔与爷爷的关系
      if (kot(parent->_data) > kot(grandparent->_data))
      {
        grandparent->_right = parent;
        uncle = grandparent->_left;
      }
      else if (kot(parent->_data) < kot(grandparent->_data))
      {
        grandparent->_left = parent;
        uncle = grandparent->_right;
      }
      // 新插入结点的父亲是红色结点，需要调整
      // 调整父亲和叔叔的左右
      if (uncle && uncle->_col == RED) // 叔叔存在并且为红色
      {
        grandparent->_col = RED;
        uncle->_col = parent->_col = BLACK;
        cur = grandparent;
        parent = cur->_parent;
      }
      else if (uncle == nullptr || uncle->_col == BLACK) // 叔叔不存在或者存在且为黑色，需要调整加变色
      {
        // 旋转都是将不均衡变为相对均衡，然后旋转后的父节点变为黑色，分到叔叔那边的结点变为红色
        // 因为这种情况，爷爷本来就是黑色
        if (parent == grandparent->_left)
        {
          if (cur == parent->_left)
          {
            RotateR(grandparent);
            parent->_col = BLACK;
            grandparent->_col = RED;
          }
          else if (cur == parent->_right)
          {
            RotateL(parent);
            RotateR(grandparent);
            cur->_col = BLACK;
            grandparent->_col = RED;
          }
        }
        else
        {
          if (cur == parent->_left)
          {
            RotateR(parent);
            RotateL(grandparent);
            grandparent->_col = RED;
            cur->_col = BLACK;
          }
          else if (cur == parent->_right)
          {
            RotateL(grandparent);
            grandparent->_col = RED;
            parent->_col = BLACK;
          }
        }
        break;
      }
    }
    _root->_col = BLACK;
    return make_pair(cur, true);
  }
  bool IsValidRBTree()
  {
    Node* pRoot = _root;
    // 空树也是红黑树
    if (nullptr == pRoot)
      return true;
    // 检测根节点是否满足情况
    if (BLACK != pRoot->_col)
    {
      cout << "违反红黑树性质二：根节点必须为黑色" << endl;
      return false;
    }
    // 获取任意一条路径中黑色节点的个数
    size_t blackCount = 0;
    Node* pCur = pRoot;
    while (pCur)
    {
      if (BLACK == pCur->_col)
        blackCount++;
      pCur = pCur->_left;
    }
    // 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    size_t k = 0;
    return _IsValidRBTree(pRoot, k, blackCount);
  }
  bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
  {
    //走到null之后，判断k和black是否相等
    if (nullptr == pRoot)
    {
      if (k != blackCount)
      {
        cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
        return false;
      }
      return true;
    }
    // 统计黑色节点的个数
    if (BLACK == pRoot->_col)
      k++;
    // 检测当前节点与其双亲是否都为红色
    Node* pParent = pRoot->_parent;
    if (pParent && RED == pParent->_colo && RED == pRoot->_col)
    {
      cout << "违反性质三：没有连在一起的红色节点" << endl;
      return false;
    }
    return _IsValidRBTree(pRoot->_left, k, blackCount) &&
      _IsValidRBTree(pRoot->_right, k, blackCount);
  }
  void Order()
  {
    _Order(_root);
    cout << endl;
  }
  void _Order(Node* root)
  {
    if (root == nullptr)
      return;
    _Order(root->_left);
    cout << root->_kv.first << " ";
    _Order(root->_right);
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* parentParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (parentParent->_left == parent)
      {
        parentParent->_left = subL;
      }
      else if (parentParent->_right == parent)
      {
        parentParent->_right = subL;
      }
      subL->_parent = parentParent;
    }
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (subRL)
      subRL->_parent = parent;
    parent->_right = subRL;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      // 先找到 parent 是父亲的左子树还是右子树
      if (parentParent->_left == parent) // 左子树
      {
        parentParent->_left = subR;
      }
      else if (parentParent->_right == parent) // 右子树
      {
        parentParent->_right = subR;
      }
      subR->_parent = parentParent;
    }
  }
private:
  Node* _root = nullptr;
};

MyMap.h

#pragma once
#include"RBTree.h"
namespace zyb
{
  template<typename K, typename T>
  class map
  {
  public:
    struct MapKeyOfT
    {
      const K& operator()(const pair<const K, T>& kv)
      {
        return kv.first;
      }
    };
    typedef typename RBTree<K, pair<const K, T>, MapKeyOfT>::iterator iterator;
    typedef typename RBTree<K, pair<const K, T>, MapKeyOfT>::const_iterator 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();
    }
    T& operator[](const K& key)
    {
      pair<iterator, bool> ret = insert(make_pair(key, T()));
      return ret.first->second;
    }
    pair<iterator, bool> insert(const pair<const K, T>& kv)
    {
      return _t.Insert(kv);
    }
  private:
    RBTree<K, pair<const K, T>, MapKeyOfT> _t;
  };
}

MySet.h

#pragma once
#include"RBTree.h"
namespace zyb
{
  template<typename K>
  class set
  {
  public:
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
    pair<iterator, bool> insert(const K& key)
    {
      return _t.Insert(key);
    }
    const_iterator begin() const
    {
      return _t.begin();
    }
    const_iterator end() const
    {
      return _t.end();
    }
  private:
    RBTree<K, K, SetKeyOfT> _t;
  };
}

可以使用以下用例对功能进行测试：

#include"RBTree.h"
#include"MyMap.h"
#include"MySet.h"
void test1(const zyb::set<int>& s1)
{
   
  zyb::set<int>::const_iterator it = s1.begin();
  while (it != s1.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}
void  test2(const zyb::map<string, int>& m1)
{          
  zyb::map<string, int>::const_iterator it = m1.begin();
  while (it != m1.end())
  {
    cout << it->first << ":" << it->second << endl;
    ++it;
  }
  cout << endl;
}
int main()
{
  zyb::set<int> s1;
  s1.insert(1);
  s1.insert(2);
  s1.insert(3);
  s1.insert(3);
  s1.insert(5);
  s1.insert(6);
  zyb::map<string, int> m1;
  m1.insert(make_pair("zyb", 1));
  m1.insert(make_pair("jn", 1));
  m1.insert(make_pair("yw", 1));
  test1(s1);
  test2(m1);
  return 0;
}

文章标签：
C++
容器
测试技术
存储
编译器
关键词：
map Set
封装Set
红黑树map Set
封装map Set
红黑树封装Set
绝世剑仙纪宁
目录
相关文章
刘大猫.
|
21天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
57 18
你对Collection中Set、List、Map理解？
软件求生
|
15天前
|
存储 缓存 安全
只会“有序无序”？面试官嫌弃的List、Set、Map回答！
小米，一位热衷于技术分享的程序员，通过与朋友小林的对话，详细解析了Java面试中常见的List、Set、Map三者之间的区别，不仅涵盖了它们的基本特性，还深入探讨了各自的实现原理及应用场景，帮助面试者更好地准备相关问题。
软件求生
53 20
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
31 3
【C++】map、set基本用法
chian-ocean
|
1月前
|
存储 算法 C++
【C++】unordered_map（set）
C++中的`unordered`容器（如`std::unordered_set`、`std::unordered_map`）基于哈希表实现，提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中，每个桶可存储一个或多个元素，以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列，以及迭代器。哈希函数用于计算元素的哈希值，冲突通过开链法解决，负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1)，但在冲突较多时可能退化为O(n)。
chian-ocean
23 5
龙大吉
|
2月前
|
Java 开发者
在Java的集合世界里，Set以其独特的特性脱颖而出，它通过“哈希魔法”和“红黑树防御”两大绝技
【10月更文挑战第13天】在Java的集合世界里，Set以其独特的特性脱颖而出。它通过“哈希魔法”和“红黑树防御”两大绝技，有效抵御重复元素的侵扰，确保集合的纯洁性和有序性。无论是“人海战术”还是“偷梁换柱”，Set都能从容应对，成为开发者手中不可或缺的利器。
龙大吉
35 6
html的七十二变
|
2月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中，Set 和 Map 用于存储唯一值和键值对，支持多种操作方法，如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象，有助于防止内存泄漏，适合特定场景使用。
html的七十二变
41 2
2的n次方_
|
3月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet（哈希表实现，无序且元素唯一）、LinkedHashSet（保持插入顺序的HashSet）、TreeSet（红黑树实现，自动排序）。Map系列为双列集合，键值一一对应，键不可重复，值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景，并提供了面试题示例，如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
2的n次方_
50 6
【数据结构】map&set详解
GuGuStudy
|
2月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
GuGuStudy
44 1
刘大猫.
|
3月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
42 5
游客j4mujezz7vm7y
|
3月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
游客j4mujezz7vm7y
54 5