AI 助理
备案控制台
开发者社区 人工智能 文章 正文

一篇文章教会你利用红黑树实现map和set的封装（下）

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

修改后红黑树全部代码

#pragma once
#include<iostream>
#include<assert.h>
#include<time.h>
using namespace std;
enum Colour
{
  RED,
  BLACK
};
template<class T>
struct RBTreeNode
{
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  T _data;
  Colour _col;
  RBTreeNode(const T& data)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
  {}
};
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T, Ref, Ptr> Self;
  Node* _node;
  __RBTreeIterator(Node* node)
    :_node(node)
  {}
  Ref operator*()
  {
    return _node->_data;
  }
  Ptr operator->()
  {
    return &_node->_data;
  }
  bool operator!=(const Self& s) const
  {
    return _node != s._node;
  }
  bool operator==(const Self& s) const
  {
    return _node == s._node;
  }
  Self& operator++()
  {
    if (_node->_right)
    {
      // 下一个就是右子树的最左节点
      Node* left = _node->_right;
      while (left->_left)
      {
        left = left->_left;
      }
      _node = left;
    }
    else
    {
      // 找祖先里面孩子不是祖先的右的那个
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self& operator--()
  {
    if (_node->_left)
    {
      // 下一个是左子树的最右节点
      Node* right = _node->_left;
      while (right->_right)
      {
        right = right->_right;
      }
      _node = right;
    }
    else
    {
      // 孩子不是父亲的左的那个祖先
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_left)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
};
template<class K, class T, class KeyOfT>
struct RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef __RBTreeIterator<T, T&, T*> iterator;
  iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  pair<iterator, bool> Insert(const T& data)
  {
    KeyOfT kot;
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_col = BLACK;
      return make_pair(iterator(_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(iterator(cur), 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* grandfater = parent->_parent;
      assert(grandfater);
      assert(grandfater->_col == BLACK);
      // 关键看叔叔
      if (parent == grandfater->_left)
      {
        Node* uncle = grandfater->_right;
        // 情况一 : uncle存在且为红，变色+继续往上处理
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfater->_col = RED;
          // 继续往上处理
          cur = grandfater;
          parent = cur->_parent;
        }// 情况二+三：uncle不存在 + 存在且为黑
        else
        {
          // 情况二：右单旋+变色
          if (cur == parent->_left)
          {
            RotateR(grandfater);
            parent->_col = BLACK;
            grandfater->_col = RED;
          }
          else
          {
            // 情况三：左右单旋+变色
            RotateL(parent);
            RotateR(grandfater);
            cur->_col = BLACK;
            grandfater->_col = RED;
          }
          break;
        }
      }
      else // (parent == grandfater->_right)
      {
        Node* uncle = grandfater->_left;
        // 情况一
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfater->_col = RED;
          // 继续往上处理
          cur = grandfater;
          parent = cur->_parent;
        }
        else
        {
          // 情况二：左单旋+变色
          if (cur == parent->_right)
          {
            RotateL(grandfater);
            parent->_col = BLACK;
            grandfater->_col = RED;
          }
          else
          {
            // 情况三：右左单旋+变色
            RotateR(parent);
            RotateL(grandfater);
            cur->_col = BLACK;
            grandfater->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  bool IsBalance()
  {
    if (_root == nullptr)
    {
      return true;
    }
    if (_root->_col == RED)
    {
      cout << "根节点不是黑色" << endl;
      return false;
    }
    // 黑色节点数量基准值
    int benchmark = 0;
    return PrevCheck(_root, 0, benchmark);
  }
private:
  bool PrevCheck(Node* root, int blackNum, int& benchmark)
  {
    if (root == nullptr)
    {
      if (benchmark == 0)
      {
        benchmark = blackNum;
        return true;
      }
      if (blackNum != benchmark)
      {
        cout << "某条黑色节点的数量不相等" << endl;
        return false;
      }
      else
      {
        return true;
      }
    }
    if (root->_col == BLACK)
    {
      ++blackNum;
    }
    if (root->_col == RED && root->_parent->_col == RED)
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
    return PrevCheck(root->_left, blackNum, benchmark)
      && PrevCheck(root->_right, blackNum, benchmark);
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
  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 (_root == parent)
    {
      _root = subR;
      subR->_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 (_root == parent)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
      subL->_parent = ppNode;
    }
  }
private:
  Node* _root = nullptr;
};

简易封装map

1. map封装代码

#pragma once
#include "RBTree.hpp"
namespace yulao
{
  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<K, V>, MapKeyOfT>::iterator iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
      return _t.Insert(kv);
    }
    V& operator[](const K& key)
    {
      pair<iterator, bool> ret = insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    RBTree<K, pair<K, V>, MapKeyOfT> _t;
  };
}

使用一个底层的红黑树 _t 来存储键-值对（pair<K, V>）。以下是这个 map 类的主要特点和功能：

  1. 构造函数：map 类没有在提供的代码中实现构造函数，但可以自行添加。
  2. 迭代器：map 类定义了一个嵌套的 iterator 类型，这个迭代器是红黑树中的迭代器。begin() 函数返回红黑树中最小元素的迭代器，而 end() 函数返回表示结束位置的迭代器。这使得你可以使用迭代器来遍历 map 中的键-值对。
  3. 插入操作：insert 函数用于向 map 中插入键-值对。它通过调用底层红黑树 _t 的 Insert 函数来执行插入操作，并返回一个 pair 对象，其中包含一个迭代器和一个布尔值。迭代器指向插入的元素，布尔值表示是否插入成功。如果插入的键已经存在，则返回的布尔值为 false，否则为 true。
  4. 访问操作：operator[] 函数用于通过键访问 map 中的值。它首先调用 insert 函数尝试插入键-值对，然后返回插入的元素的值的引用。如果键已经存在，则不会插入新元素，而是返回已存在元素的引用。

2. 测试map封装

void test_map()
{
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map<string, int> countMap;
    for (auto& str : arr)
    {
        // 1、str不在countMap中，插入pair(str, int()),然后在对返回次数++
        // 2、str在countMap中，返回value(次数)的引用，次数++;
        countMap[str]++;
    }
    map<string, int>::iterator it = countMap.begin();
    while (it != countMap.end())
    {
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    for (auto& kv : countMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
}

输出结果

苹果:6
西瓜:3
香蕉:2
苹果:6
西瓜:3
香蕉:2

简易封装set

1. set封装代码

#pragma once
#include "RBTree.hpp"
namespace yulao
{
  template<class K>
  class set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      return _t.Insert(key);
    }
  private:
    RBTree<K, K, SetKeyOfT> _t;
  };
}
  1. 构造函数：set 类没有在提供的代码中实现构造函数，但可以自行添加。
  2. 迭代器：set 类定义了一个嵌套的 iterator 类型，这个迭代器是红黑树中的迭代器。begin() 函数返回红黑树中最小元素的迭代器，而 end() 函数返回表示结束位置的迭代器。这使得你可以使用迭代器来遍历 set 中的元素。
  3. 插入操作：insert 函数用于向 set 中插入元素。它通过调用底层红黑树 _t 的 Insert 函数来执行插入操作，并返回一个 pair 对象，其中包含一个迭代器和一个布尔值。迭代器指向插入的元素，布尔值表示是否插入成功。如果插入的元素已经存在，则返回的布尔值为 false，否则为 true。

2. 测试set封装

void test_set()
{
    set<int> s;
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    s.insert(3);
    s.insert(2);
    s.insert(1);
    s.insert(5);
    s.insert(3);
    s.insert(6);
    s.insert(4);
    s.insert(9);
    s.insert(7);
    it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

输出结果

1 2 3 4 5 6 7 9

总结

这里我们只是通过我们之前学习的红黑树的基础上做了一些模板上的修改,简单的实现了map和set的迭代器功能和插入功能,但这种使用红黑树底层模拟 map 和 set 的迭代器和插入功能的实现有以下作用和好处：

  1. 提供了自定义数据结构的能力： 通过使用底层红黑树实现 map 和 set，你可以更灵活地定义自己的数据结构，而不仅限于使用标准库提供的容器。这使得你可以根据特定的需求来设计和实现数据结构，以满足项目的要求。
  2. 学习数据结构和算法： 这种实现方式可以帮助你深入理解红黑树这种常用的自平衡二叉搜索树数据结构，以及与之相关的算法。通过手动实现红黑树的插入、删除和迭代器等功能，你可以更好地理解这些操作的内部工作原理，从而提高自己的编程技能。
  3. 适应特定需求： 有时标准库提供的容器不一定能满足特定项目或应用的需求。通过自定义数据结构，你可以根据自己的需求进行扩展和定制，以提供更适用的功能和性能。
  4. 教育和学术用途： 这种实现方式还可以用于教育和学术研究。它可以作为一个教学工具，帮助学生理解和学习红黑树等数据结构和算法的原理。同时，它也可以用于学术研究，用于开展相关领域的实验和研究。


文章标签：
算法
容器
存储
关键词：
红黑树map Set
红黑树Map
红黑树Set
map Set
Set封装
爱学习的鱼佬
目录
相关文章
羑悻的小杀马特
|
4天前
|
编译器 容器
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
羑悻的小杀马特
26 13
羑悻的小杀马特
|
4天前
|
编译器 测试技术 计算机视觉
红黑树模拟封装map和set
红黑树模拟封装map和set
羑悻的小杀马特
19 9
软件求生
|
2月前
|
存储 缓存 安全
只会“有序无序”？面试官嫌弃的List、Set、Map回答！
小米，一位热衷于技术分享的程序员，通过与朋友小林的对话，详细解析了Java面试中常见的List、Set、Map三者之间的区别，不仅涵盖了它们的基本特性，还深入探讨了各自的实现原理及应用场景，帮助面试者更好地准备相关问题。
软件求生
73 20
刘大猫.
|
2月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
79 18
你对Collection中Set、List、Map理解？
chian-ocean
|
3月前
|
存储 算法 C++
【C++】unordered_map（set）
C++中的`unordered`容器（如`std::unordered_set`、`std::unordered_map`）基于哈希表实现，提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中，每个桶可存储一个或多个元素，以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列，以及迭代器。哈希函数用于计算元素的哈希值，冲突通过开链法解决，负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1)，但在冲突较多时可能退化为O(n)。
chian-ocean
37 5
chian-ocean
|
3月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
62 3
【C++】map、set基本用法
html的七十二变
|
4月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中，Set 和 Map 用于存储唯一值和键值对，支持多种操作方法，如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象，有助于防止内存泄漏，适合特定场景使用。
html的七十二变
62 2
GuGuStudy
|
4月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
GuGuStudy
57 1
刘大猫.
|
5月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
51 5
周一同学Zelina
|
5月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法，并探讨了它们在前端开发中的具体应用，包括如何利用这些数据结构来解决常见的编程问题。
周一同学Zelina
53 0
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用