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

使用红黑树模拟实现map和set

2023-03-21 285
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 将单独使用的红黑树改造一下，即使用类模板来适用set和map的不同情况，从而作为map和set的底层，进而模拟实现了map和set。

 在STL的源代码中，map和set的底层原理都是红黑树。但这颗红黑树跟我们单独写的红黑树不一样，它需要改造一下：

改造红黑树

节点的定义

因为map和set的底层都是红黑树。而且map是拥有键值对pair<K,V>的，而set是没有键值对，只有一个K。因此，为了应对这两种不同的情况，就使用模板参数T。

当map使用这棵红黑树的时候，T就会变成pair<K,V>。当set使用时，T就会变成K。

//使用枚举
enum Colour
{
  RED,
  BLACK,
};
// 如果是map，则为pair<K, V>; 如果是set，则为k
//因此，对于节点来说，需要再套一层模板，来应付两种不同的情况
template<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)  //默认是红色
  {}
};

image.gif

改版的红黑树的插入操作

红黑树的模板参数有三个：K、valueType和仿函数KeyOfValue。

K是key的类型，ValueTyp要么是set的K，要么是map的pair<const K,V>。

而仿函数是为了比较节点的值的大小的，因为官方库中键值对pair<K,V>比较大小的方法是比较first和second。但是红黑树中，新增节点是通过比较first，因此我们需要自己写一个仿函数用于单独比较first。

//跟节点的定义一样
//因为关联式容器中存储的是<key, value>的键值对，因此
// k为key的类型，
// ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k。如下：
// map->RBTree<K,pair<const K,V>,MapKeyOfT> _t;
// set->RBTree<K,K,SetKeyOfT> _t
// 
// KeyOfValue: 通过value来获取key的一个仿函数类。其作用就是用于比较。
template<class K,class ValueType,class KeyOfValue>
class RBTree
{
  typedef RBTreeNode<ValueType> Node;
public: 
    //迭代器
    typedef __RBTreeIterator<ValueType> iterator;
   //......
private:
  Node* _root = nullptr;
};

image.gif

迭代器

红黑树的迭代器不能使用原生指针，因为它是一棵树，节点地址不连续，因此需要封装起来。

//set的K，map的pair<K,V>
template<class ValueType>
struct __RBTreeIterator
{
  typedef RBTreeNode<ValueType> Node;
  typedef __RBTreeIterator<ValueType> Self;
  Node* _node;
  __RBTreeIterator(Node* node)
    :_node(node)
  {}
};

image.gif

1.operator++()

红黑树是二叉搜索树，采用的是中序遍历的方法。因此，迭代器每次向前走，是按照中序遍历的顺序走的。

因此，对于往前++，有两种情况：第一种情况是当前节点的右孩子不为空，那么按照中序遍历的顺序，下一个节点便是右子树的最小值。第二种情况是当前节点的右孩子为空：这种情况下，又分两种情况：①当前节点是父节点的左孩子，那么下一个节点肯定是当前节点的父节点。②当前节点是父节点的右孩子，这意味着当前节点的父节点也被遍历了，又没有右孩子节点，只能往上找了，找的节点是祖先节点，而这个祖先节点是特征是：孩子节点是它的左节点。

{70M%EQ73L~2GU86IL1W901.png

//左 根  右
  Self& operator++()
  {
    //当当前节点的右子树不为空，根据中序遍历的顺序，那就找右子树最小值
    if (_node->_right)
    {
      Node* minValue = _node->_right;
      while (minValue->_left)
      {
        minValue = minValue->_left;
      }
      //找到最小值的节点后，更新节点
      _node = minValue;
    }
    else  //当当前节的的右子树为空，说明它是叶子节点。此时需要判断情况
    {
      //判断当前节点是父亲节点的左孩子还是右孩子
      //第一种情况：如果是cur==parent->_right，即当前节点是父节点的右孩子的话，就
      //去找祖先节点（这个祖先节点的特征：孩子节点是它的左节点）
      //第二种情况：当前节点是父亲节点的左孩子，那么下一个节点就是父亲节点了
      Node* cur = _node;
      //定义父亲节点。
      Node* parent = cur->_parent;
      //如果当前节点不是父亲的右孩子，并且父亲是不存在，那么就是根节点或者是左孩子节点了
      //那就不进入循环。
      while (parent && cur == parent->_right)
      {
        //如果是，那就往上找到下一个节点。
        cur = cur->_parent;
        parent = parent->_parent;
      }
      //更新节点
      _node = parent;
    }
    return *this;
  }

image.gif

2.begin()和end();

迭代器的begin和end，是左闭右开的区间。那么begin就是最左的节点，end则是最右节点的下一个节点。这里不使用哨兵来作为end节点。

对于begin，就找到最左的节点就好啦！

iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }

image.gif

对于end，这里选择直接置为空，传入匿名对象。这样子做的话，当遍历到最后一个节点后，它会往回遍历，一直到了根节点的上面一个节点，也就是空。此时就会结束循环。

iterator end()
  {
    return iterator(nullptr);
  }

image.gif

迭代器整体代码：

template<class ValueType>
struct __RBTreeIterator
{
  typedef RBTreeNode<ValueType> Node;
  typedef __RBTreeIterator<ValueType> Self;
  Node* _node;
  __RBTreeIterator(Node* node)
    :_node(node)
  {}
  ValueType& operator*()
  {
    return _node->_data;
  }
  ValueType* operator->()
  {
    return &_node->_data;
  }
  Self& operator++()
  {
    if (_node->_right)
    {
      Node* minValue = _node->_right;
      while (minValue->_left)
      {
        minValue = minValue->_left;
      }
      _node = minValue;
    }
    else 
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  bool operator!=(const Self& s)
  {
    return _node != s._node;
  }
};

image.gif

set的模拟实现

仿函数

由于set只有Key，因此就让仿函数直接返回Key值就可以了。

template<class K>
  class set
  {
    //set的仿函数，返回set的K值
    struct SetKeyOfValue
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };

image.gif

整体都是复用了红黑树的接口，并没有什么技术含量，问题都在红黑树中解决了。

namespace my_set
{
  template<class K>
  class set
  {
    //set的仿函数，返回set的K值
    struct SetKeyOfValue
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    bool insert(const K& key)
    {
      return _t.Insert(key);
    }
  private:
    RBTree<K, K, SetKeyOfValue> _t;
  };

image.gif

map的模拟实现：

仿函数

由于比较的是first，因此我们返回键值对中的first即可。

template<class K, class V>
  class map
  {
    struct MapKeyOfValue
    {
      const K& operator()(const pair<const K, V>& kv)
      {
        return kv.first;
      }
    };

image.gif

整体代码，一样的都是复用了红黑树的接口，并没有什么技术含量：

namespace my_map
{
  template<class K, class V>
  class map
  {
    struct MapKeyOfValue
    {
      const K& operator()(const pair<const K, V>& kv)
      {
        return kv.first;
      }
    };
  public:
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfValue>::iterator iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    bool insert(const pair<const K, V>& kv)
    {
      return _t.Insert(kv);
    }
  private:
    RBTree<K, pair<const K, V>, MapKeyOfValue> _t;
  };

image.gif

最后是红黑树的整体代码，这段代码跟单独写的红黑树的代码差不多，就是在新增节点的操作那里，比较节点的值使用的是仿函数。

#pragma once
//使用枚举
enum Colour
{
  RED,
  BLACK,
};
// 如果是map，则为pair<K, V>; 如果是set，则为k
//因此，对于节点来说，需要再套一层模板，来应付两种不同的情况
template<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 ValueType>
struct __RBTreeIterator
{
  typedef RBTreeNode<ValueType> Node;
  typedef __RBTreeIterator<ValueType> Self;
  Node* _node;
  __RBTreeIterator(Node* node)
    :_node(node)
  {}
  ValueType& operator*()
  {
    return _node->_data;
  }
  ValueType* operator->()
  {
    return &_node->_data;
  }
  //左 根  右
  Self& operator++()
  {
    //当当前节点的右子树不为空，根据中序遍历的顺序，那就找右子树最小值
    if (_node->_right)
    {
      Node* minValue = _node->_right;
      while (minValue->_left)
      {
        minValue = minValue->_left;
      }
      //找到最小值的节点后，更新节点
      _node = minValue;
    }
    else  //当当前节的的右子树为空，说明它是叶子节点。此时需要判断情况
    {
      //判断当前节点是父亲节点的左孩子还是右孩子
      //第一种情况：如果是cur==parent->_right，即当前节点是父节点的右孩子的话，就
      //去找祖先节点（这个祖先节点的特征：孩子节点是它的左节点）
      //第二种情况：当前节点是父亲节点的左孩子，那么下一个节点就是父亲节点了
      Node* cur = _node;
      //定义父亲节点。
      Node* parent = cur->_parent;
      //如果当前节点不是父亲的右孩子，并且父亲是不存在，那么就是根节点或者是左孩子节点了
      //那就不进入循环。
      while (parent && cur == parent->_right)
      {
        //如果是，那就往上找到下一个节点。
        cur = cur->_parent;
        parent = parent->_parent;
      }
      //更新节点
      _node = parent;
    }
    return *this;
  }
  bool operator!=(const Self& s)
  {
    return _node != s._node;
  }
};
//跟节点的定义一样
//因为关联式容器中存储的是<key, value>的键值对，因此
// k为key的类型，
// ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k。如下：
// map->RBTree<K,pair<const K,V>,MapKeyOfT> _t;
// set->RBTree<K,K,SetKeyOfT> _t
// 
// KeyOfValue: 通过value来获取key的一个仿函数类。其作用就是用于比较。
template<class K,class ValueType,class KeyOfValue>
class RBTree
{
  typedef RBTreeNode<ValueType> Node;
public:
  typedef __RBTreeIterator<ValueType> iterator;
  iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  bool Insert(const ValueType& data)
  {
    //先按二叉搜索树的规矩来创建一棵二叉搜索树
    if (_root == nullptr)
    {
      _root = new Node(data);
      //因为红黑树的根节点是黑色的
      _root->_col = BLACK;
      return true;
    }
    KeyOfValue 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;
      cur->_parent = parent;
    }
    else
    {
      parent->_left = cur;
      cur->_parent = parent;
    }
    //创建完二叉搜索树
    //开始创建红黑树，使用颜色来判断是否需要调整
    //循环往上走，循环条件：当走到的parent不为空，并且parent是红色的
    //即我们列举是三种情况，parent都是红的，就需要重新调整
    //如果parent是黑色的，那就不需要了。直接就是一棵红黑树,不进入循环
    while (parent && parent->_col == RED)
    {
      //保存祖先节点，即g节点
      Node* grandfther = parent->_parent;
      //判断父节点是在祖先节点的哪边
      if (parent == grandfther->_left)
      {
        //父节点在左边，那么叔叔节点就在右边
        Node* uncle = grandfther->_right;
        //情况一：uncle存在且为红。改变颜色即可
        if (uncle && uncle->_col == RED)
        {
          //变色。
          parent->_col = uncle->_col = BLACK;
          grandfther->_col = RED;
          //往上走
          cur = grandfther;
          parent = cur->_parent;
        }
        else  //uncle不存在 或者 存在但是黑色
        {
          //情况二  p是g的左孩子，cur是p的左孩子，以g为轴右单旋
          if (cur == parent->_left)
          {
            //右单旋
            RotateR(grandfther);
            //变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
            parent->_col = BLACK;
            grandfther->_col = RED;
          }
          else  //情况三  p是g的左孩子，cur是p的右孩子.
          {
            //先以p为轴左旋转
            RotateL(parent);
            //变成情况二，再以g为轴右单旋
            RotateR(grandfther);
            //变色  cur变成根节点，为黑色。p和g是红色
            cur->_col = BLACK;
            grandfther->_col = RED;
          }
          break;
        }
      }
      else  //parent是在grandfther的右边
      {
        //叔叔节点就在祖先节点的左边
        Node* uncle = grandfther->_left;
        //情况一：uncle存在且为红。改变颜色即可
        if (uncle && uncle->_col == RED)
        {
          //变色。
          parent->_col = uncle->_col = BLACK;
          grandfther->_col = RED;
          //往上走
          cur = grandfther;
          parent = cur->_parent;
        }
        else  //uncle不存在 或者 存在但是黑色
        {
          //情况二  p是g的右孩子，cur是p的右孩子。
          if (cur == parent->_right)
          {
            //左单旋
            RotateL(grandfther);
            //变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
            parent->_col = BLACK;
            grandfther->_col = RED;
          }
          else  //情况三  p是g的右孩子，cur是p的左孩子.
          {
            //先以p为轴右旋转
            RotateR(parent);
            //变成情况二，再以g为轴左单旋
            RotateL(grandfther);
            //变色  cur变成根节点，为黑色。p和g是红色
            cur->_col = BLACK;
            grandfther->_col = RED;
          }
          break;
        }
      }
    }
    //最后将根节点置为黑
    _root->_col = BLACK;
    return true;
  }
  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 (ppNode == nullptr)
    {
      _root = subR;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
      subR->_parent = ppNode;
    }
  }
  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 (ppNode == nullptr)
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
      subL->_parent = ppNode;
    }
  }
  void Inorder()
  {
    _Inorder(_root);
  }
  void _Inorder(Node* root)
  {
    if (root == nullptr)
      return;
    _Inorder(root->_left);
    std::cout << root->_kv.first << ": " << root->_kv.second << std::endl;
    _Inorder(root->_right);
  }
  bool Check(Node* root, int blackNum, const int ref)
  {
    if (root == nullptr)
    {
      //cout << blackNum << endl;
      if (blackNum != ref)
      {
        cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
        return false;
      }
      return true;
    }
    if (root->_col == RED && root->_parent->_col == RED)
    {
      cout << "违反规则：出现连续红色节点" << endl;
      return false;
    }
    if (root->_col == BLACK)
    {
      ++blackNum;
    }
    return Check(root->_left, blackNum, ref)
      && Check(root->_right, blackNum, ref);
  }
  bool IsBalance()
  {
    if (_root == nullptr)
    {
      return true;
    }
    if (_root->_col != BLACK)
    {
      return false;
    }
    int ref = 0;
    Node* left = _root;
    while (left)
    {
      if (left->_col == BLACK)
      {
        ++ref;
      }
      left = left->_left;
    }
    return Check(_root, 0, ref);
  }
private:
  Node* _root = nullptr;
};

image.gif


文章标签：
C++
关键词：
map Set
红黑树Map
红黑树map Set
红黑树Set
Map红黑树
二肥是只大懒蓝猫
目录
相关文章
john散漫
|
2月前
|
存储 缓存 JavaScript
Set和Map有什么区别？
Set和Map有什么区别？
john散漫
241 1
ephemerals__
|
6月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map（附源码）
本文基于红黑树的实现，模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改，实现了两种容器的功能。主要步骤包括：1) 修改红黑树节点结构以支持不同数据类型；2) 使用仿函数适配键值比较逻辑；3) 实现双向迭代器支持遍历操作；4) 封装`insert`、`find`等接口，并为`map`实现`operator[]`。最终，通过测试代码验证了功能的正确性。此实现减少了代码冗余，展示了模板与仿函数的强大灵活性。
ephemerals__
169 2
码字猴儿
|
3月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些？
for...of循环在遍历Set和Map时的注意事项有哪些？
码字猴儿
118 13
hahaha无
|
3月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。在unordered_set中，元素的值同时也是唯一地标识它的key。在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
hahaha无
179 0
hahaha无
|
3月前
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后，我们的底层代码已经完成了，这时候已经是一个底层STL的红黑树了，已经已符合库里面的要求了，这时候我们是需要给他穿上对应的“衣服”，比如穿上set的“衣服”，那么这个穿上set的“衣服”，那么他就符合库里面set的要求了，同样map一样，这时候我们就需要实现set与map了。因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
hahaha无
43 0
hahaha无
|
3月前
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别，注意事项
set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列。set当中存储元素的value都是唯一的，不可以重复，因此可以使用set进行去重。set默认是升序的，但是其内部默认不是按照大于比较，而是按照小于比较。set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
hahaha无
191 0
羑悻的小杀马特
|
7月前
|
编译器 容器
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
羑悻的小杀马特
93 13
羑悻的小杀马特
|
7月前
|
编译器 测试技术 计算机视觉
红黑树模拟封装map和set
红黑树模拟封装map和set
羑悻的小杀马特
76 9
刘大猫.
|
9月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
154 18
你对Collection中Set、List、Map理解？