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

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

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

修改后红黑树全部代码

#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
Set封装
map Set封装
Map封装
红黑树map Set
爱学习的鱼佬
目录
相关文章
2的n次方_
|
15天前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet（哈希表实现，无序且元素唯一）、LinkedHashSet（保持插入顺序的HashSet）、TreeSet（红黑树实现，自动排序）。Map系列为双列集合，键值一一对应，键不可重复，值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景，并提供了面试题示例，如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
2的n次方_
23 6
【数据结构】map&set详解
刘大猫.
|
4天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
15 5
游客j4mujezz7vm7y
|
7天前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
游客j4mujezz7vm7y
21 5
周一同学Zelina
|
6天前
|
存储 前端开发 API
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法，并探讨了它们在前端开发中的具体应用，包括如何利用这些数据结构来解决常见的编程问题。
周一同学Zelina
12 0
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
热爱技术的小郑
|
2月前
|
存储 安全 Java
java集合框架复习----（4）Map、List、set
这篇文章是Java集合框架的复习总结，重点介绍了Map集合的特点和HashMap的使用，以及Collections工具类的使用示例，同时回顾了List、Set和Map集合的概念和特点，以及Collection工具类的作用。
热爱技术的小郑
35 1
java集合框架复习----（4）Map、List、set
热爱技术的小郑
|
2月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别？
该CSDN博客文章讨论了Map和Set的区别，但提供的内容摘要并未直接解释这两种集合类型的差异。通常，Map是一种键值对集合，提供通过键快速检索值的能力，而Set是一个不允许重复元素的集合。
热爱技术的小郑
36 3
wljslmz
|
2月前
|
存储 Java 索引
Java 中 List、Set、Map 和 Queue 之间的区别
【8月更文挑战第22天】
wljslmz
20 0
游客ot6eft3qn37ga
|
2月前
|
存储 JavaScript 前端开发
ES6新特性（四）: Set 和 Map
ES6新特性（四）: Set 和 Map
游客ot6eft3qn37ga
29 1
დ旧言~
|
3月前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
დ旧言~
31 2
დ旧言~
|
3月前
|
存储 C++ 容器
【C++】map和set深度讲解（下）
【C++】map和set深度讲解（下）
დ旧言~
55 2

热门文章

最新文章

  • 1
    [20120906]alter table set unused column后的恢复.txt
  • 2
    set DataGrid1.DataSource = rs DataGrid1为什么时空的？
  • 3
    特殊权限位set_uid set_gid stick_bit 软链接硬链接
  • 4
    oc-16-set,get方法
  • 5
    PHP 魔术方法__set() __get() 方法
  • 6
    Error: Failed to set Event Logging
  • 7
    spring-注入set集合
  • 8
    Parameter \&#39; \&#39;: No size set for variable length data type: String
  • 9
    启动mongodb报错 Failed to set up listener: SocketException: Address already in use 解决办法
  • 10
    Set uid, gid,sticky bit的三个权限的详细说明
  • 1
    JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】（二）
    43
  • 2
    JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】（一）
    30
  • 3
    vue 百度地图开发【教程】1. 绘制百度地图（不使用 vue-baidu-map，解决 BMap is undefined）
    243
  • 4
    vue-baidu-map 绘制行政区划的轮廓，添加行政区划名称（含给覆盖物添加点击事件）——vue 百度地图开发
    169
  • 5
    vue-baidu-map 报错 | map is undefined
    58
  • 6
    vue-baidu-map 报错 | BMap is undefined
    77
  • 7
    vue-baidu-map 自定义地图主题
    171
  • 8
    vue-baidu-map 百度地图检索、获取坐标
    33
  • 9
    DOM 属性列表（命名节点图 Named Node Map）
    26
  • 10
    C++一分钟之-扁平化映射与unordered_map
    50

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    无影云桌面