通过红黑树封装 map 和 set 容器

简介: 通过红黑树封装 map 和 set 容器

一、红黑树的迭代器

红黑树的遍历默认为中序遍历 —— key 从小到大,因此 begin() 应该获取到红黑树的最左节点 —— 最小,end() 获取到红黑树最右节点的下一个位置, operator++() 也应保证红黑树的遍历为中序的状态。

首先对红黑树节点进行改造:

引入一个模板参数 T ,使 RBTreeNode / RBTree 成为一个可以自动推演类型的容器,当我们向 RBTree 中传 key 时,封装 set 容器;向 RBTree 中传 pair<key, value> 时,封装 map 容器。

1.1 定义红黑树的迭代器:
  template<class T, class Ref, class Ptr> // 与 list 迭代器处没有区别,Ref —— T& ,Ptr —— T*
    struct RBTreeIterator
    {
        typedef RBTreeNode<T> Node;
        typedef RBTreeNodeIterator<T, Ref, Ptr> Self;
        Node* _node;
        
        RBTreeIterator(Node* node)
            :_node(node)
        {}
    };
1.2 红黑树 operator++()

请务必记住:红黑树迭代器 ++ 为中序遍历 —— 左子树 — 根 — 右子树 !

假设 cur —— 迭代器 已经走到了 key 为 8 的节点 位置,这代表着 key 为 8 的节点 的左子树已经遍历过了key 为 8 的节点 的右子树不为空,则中序遍历 key 为 8 的节点 的右子树

  iterator operator++()
    {
        if (_node == nullptr) // 空树,直接返回 空 的迭代器
        {
            return iterator(nullptr); 
        }
        
        if (_node->_right)
        {
            Node* subLeft = _node->_right;
            while (subLeft->_left)
            {
                subLeft = subLeft->_left;
            }
            _node = subLeft;
        }
        
        return *this;
    }

经过 operator++() 后,cur 到了 key 为 11 的节点 位置,此时 cur->_right 为空,表明以 key 为 11 的节点 为最右节点的子树已经全部遍历过,要去找从根到当前节点的简单路径中,cur 所在子树左子树最近祖宗节点

  iterator operator++()
    {
        // ...
        if (_node->_right)
        { //... }
        else 
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur != parent->_left) // parent 存在 且 cur所在子树不是parent的左子树时
            {
                cur = parent;
                parent = cur->_parent;
            }
            _node = parent;
        }
        return *this;
    }
总结:
  1. 迭代器指向节点的右子树不为空时, operator++() 的下一个位置就是其右子树的最左节点
  2. 迭代器指向节点的右子树为空,意味当前节点所在的左子树已经全部访问完了,operator++() 的下一个位置是当前子树为左子树的最近祖宗节点
1.3 operator*()
  Ref operator*()
    {
        return _node->_data;
    }
1.4 operator->()
  Ptr operator->()
    {
        return &(_node->_data);
    }

二、改造红黑树

在对红黑树进行修改之前,首先得明确:

  1. 老版本 Node(RBTreeNode) 的 data 类型是 pair<K, V>,我们通常把 K 当做键值,进而实现节点的查找、map::value 的修改等功能。
  2. 改造 Node 的目的是我们对模板参数 T 传 key 时,则编译器封装出 set 容器;对 T 传 pair<K, V> 时,则封装 map 容器。以此减少冗余代码。

为了避免与 STL 中的 map 和 set 冲突,请在自己定义的命名空间内实现!

2.1 初步改造红黑树
  template<class K, class T>
    class RBTree
    {
        typedef RBTreeNode<T> Node;
        typedef RBTreeIterator<T, T&, T*> iterator;
        typedef RBTreeIterator<T, const T&, const T*> const_iterator;
        
    private:
        Node* _root;
    };
2.2 初步搭建 map 和 set 的框架

map:

  template<class K, class V>
    class map
    {
        typedef RBTree<K, pair<const K, V>>::iterator iterator;
        typedef RBTree<K, pair<const K, const V>>::const_iterator const_iterator;
        
    private:
        RBTree<K, pair<const K, V>> _t; // 加上 const ,保证 key 是无法被修改的
    };

set:

  template<class K>
  class set
    {
        typedef RBTree<K, const K>::iterator iterator; 
        typedef RBTree<K, const K>::const_iterator const_iterator;
        
    private:
        RBTree<K, const K> _t; // set 中的节点不能被修改
    }

无论是 map 还是 set 中,都存着两个 key : K 和 const K / pair<const K, V> ,前者作为键值,用于查找;后者则是我们存入 Node 中的数据 —— 对应于 Node 的模板参数 T ,编译器会根据我们传入的数据类型生成对应类型的节点 。


注意容器内部树的类型要与 typedef 的迭代器类型保持一致,否则编译阶段会报错 —— 比如:在某些地方会出现 const 权限放大的问题。

2.3 引入仿函数 KeyOfT

我们再看一眼,旧版本的 RBTree::Insert()

第一,写死的 const pair<K, V> kv 显然已经不合时宜;


第二,如果 T 的类型是 pair ,我们可以通过 cur->_data.first (新版 Node 已将 _kv 修改为 _data)取到 key 进行比较,若 T 的类型是 int ,则整个程序必然出现问题。


因此,我们需要引入一个仿函数 KeyOfT ,用于从节点的 _data 中取到相应的键值,进而完成一系列操作。

  • 在 map 和 set 中封装仿函数 KeyOfT
  // map:
  template<class K, class V>
    class map
    {
        typedef RBTree<K, pair<const K, V>, KeyOfT>::iterator iterator;
        typedef RBTree<K, pair<const K, const V>, KeyOfT>::const_iterator const_iterator;
        
    public:
        struct KeyOfT
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };
        
    private:
        RBTree<K, pair<const K, V>, KeyOfT> _t; // 加上 const ,保证 key 是无法被修改的
    };

  // set:
  template<class K>
  class set
    {
        typedef RBTree<K, const K, KeyOfT>::iterator iterator; 
        typedef RBTree<K, const K, KeyOfT>::const_iterator const_iterator;
        
    public:
        struct KeyOfT
        {
            const K& operator()(const K& k)
            {
                return k;
            }
        };
        
    private:
        RBTree<K, const K, KeyOfT> _t; // set 中的节点不能被修改
    }

同时我们要为 RBTree 增加一个接受仿函数的模板参数。

  template<class K, class T, class KeyOfT>
    class RBTree
    {
        typedef RBTreeNode<T> Node;
        typedef RBTreeIterator<T, T&, T*> iterator;
        typedef RBTreeIterator<T, const T&, const T*> const_iterator;
        
    private:
        Node* _root;
    };
  • 改造 RBTree::Insert()
  pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK; // 默认构造节点为红色,根据红黑树的性质,我们应把根节点修改为黑色
            return make_pair(iterator(root), true);
        }
        
        Node* cur = _root;
        Node* parent = nullptr;
        KeyOfT kot; // 仿函数变量,用于获取 data 中的键值
        while (cur)
        {
            if (kot(cur->_data) > kot(data)) // 利用仿函数 kot 获取键值
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (kot(cur->_data) < kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else // 红黑树中已经存在一个要插入键值的节点
            {
                return make_pair(iterator(cur), true); // 返回当前节点所在的迭代器,并 return false
            }
        }
        
        Node* newnode = cur; // 保存当前节点的位置,防止旋转导致 cur 指向其他节点而出现错误
        if (kot(parent->_data) > kot(cur->_data))
        {
            parent->_left = cur;
        }
        else 
        {
            parent->_right = cur;
        }
        
        // 旋转的一系列过程
        // ...
        // 与普通红黑树无异,前面的文章已提到,这里不再赘述
        
        _root->_col = BLACK; // 把根节点修改为黑色
        return make_pair(iterator(newnode), true);
    }
2.4 改造 Find() ,增加 begin() end()
  • Find()
  iterator Find(const K& key)
    {
        if (_root == nullptr)
        {
            return iterator(nullptr); // 空树,返回空迭代器
        }
        
        Node* cur = _root;
        Node* parent = nullptr;
        KeyOfT kot; // 仿函数变量,用于获取 data 中的键值
        while (cur)
        {
            if (kot(cur->_data) > kot(data)) // 利用仿函数 kot 获取键值
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (kot(cur->_data) < kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else // 找到了
            {
                return iterator(cur);
            }
        }
        
        return iterator(nullptr);
    }

其实没有必要写 if (_root == nullptr) 这一语句,如果 _root 为空,cur 自然也为空,不会进入 while 循环,最终还是 return iterator(nullptr) ;为了代码的逻辑性,还是加上。

  • begin()
  iterator begin()
    {
        if (_root == nullptr)
        {
            return iterator(nullptr);
        }
        
        Node* subLeft = _root;
        while (subLeft->_left)
        {
            subLeft = subLeft->_left; // 找红黑树的最左节点
    }
        return iterator(subLeft);
    }

  const_iterator begin() const
    {
        if (_root == nullptr)
        {
            return iterator(nullptr);
        }
        
        Node* subLeft = _root;
        while (subLeft->_left)
        {
            subLeft = subLeft->_left; // 找红黑树的最左节点
    }
        return iterator(subLeft);
    }
  • end()
  iterator end()
    {
        return iterator(nullptr);
    }

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

三、实现 map

3.1 对简单接口进行包装
  template<class K, class V>
    class map
    {
        typedef RBTree<K, pair<const K, V>, KeyOfT>::iterator iterator;
        typedef RBTree<K, pair<const K, const V>, KeyOfT>::const_iterator const_iterator;
        
    public:
        struct KeyOfT
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };
        
        iterator begin() // 封装 begin()
        {
            return _t.begin();
        }
        
        iterator end() // end()
        {
            return _t.end();
        }
        
        iterator find(const K& key) // find()
        {
            return _t.Find(key);
        }
        
        pair<iterator, bool> insert(const pair<K, V>& kv) // insert()
        {
            return _t.Insert(kv);
        }
        
    private:
        RBTree<K, pair<const K, V>, KeyOfT> _t; // 加上 const ,保证 key 是无法被修改的
    };
3.2 operator[]

在前面的文章中,我们讲到过 operator[]insert() 的关系。

同样,我们也要通过 insert() 实现 operator[] 接口。

  V& operator[](const K& key)
    {
        pair<iterator, bool> ret = insert(make_pair(key, V()));
        return ret.first->second;
  }    
解释一下 ret.first->second
  1. ret.first 取到 pair 中的迭代器
  2. ret.first->second 全写为 ret.first->->second

第一个 ->operator->()return &(_node->_data)

第二个 ->(&_data)->second

编译器把两个 -> 简化为一个 —— 显式写两个反而会报错。

四、实现 set

与实现 map 基本一致,这里便不再重复了。

  template<class K>
  class set
  {
  public:
    struct KeyOfT
    {
      const K operator()(const K& data)
      {
        return data;
      }
    };

    typedef typename RBTree<K, const K, KeyOfT>::iterator iterator;
    typedef typename RBTree<K, const K, KeyOfT>::const_iterator const_iterator;

    iterator begin()
    {
      return _t.begin();
    }

    iterator end()
    {
      return _t.end();
    }

    iterator find(const K& key)
    {
      return _t.Find(key);
    }

    pair<iterator, bool> insert(const K& key)
    {
      return _t.Insert(key);
    }

  private:
    RBTree<K, const K, KeyOfT> _t;
  };
相关文章
|
1月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
34 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
36 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
|
2月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
5月前
|
Dart
Dart之集合详解(List、Set、Map)
Dart之集合详解(List、Set、Map)
|
2月前
|
Go 定位技术 索引
Go 语言Map(集合) | 19
Go 语言Map(集合) | 19
|
1月前
|
存储 分布式计算 Java
Stream很好,Map很酷,但答应我别用toMap():Java开发中的高效集合操作
在Java的世界里,Stream API和Map集合无疑是两大强大的工具,它们极大地简化了数据处理和集合操作的复杂度。然而,在享受这些便利的同时,我们也应当警惕一些潜在的陷阱,尤其是当Stream与Map结合使用时。本文将深入探讨Stream与Map的优雅用法,并特别指出在使用toMap()方法时需要注意的问题,旨在帮助大家在工作中更高效、更安全地使用这些技术。
40 0
|
3月前
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。