从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(上)

简介: 从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现

1. set和map中的红黑树

前一篇红黑树的源代码:

#pragma once
 
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
 
enum Colour // 枚举颜色
{
  RED,
  BLACK
};
 
template<class K, class V>
struct RBTreeNode
{
  RBTreeNode<K, V>* _left;
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;
 
  pair<K, V> _kv;
  Colour _col; // 比AVL树少了平衡因子,多了颜色
 
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};
 
template<class K, class V>
struct RBTree
{
  typedef RBTreeNode<K, V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_col = BLACK; // 根给黑色
      return true;
    }
 
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) // 找到要插入的结点
    {
      if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
 
    cur = new Node(kv);
    cur->_col = RED; // 默认插入红色结点
    if (parent->_kv.first < kv.first) // 找到位置后插入结点
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
 
    while (parent && parent->_col == RED) // 父亲存在且为红才需要处理
    {
      Node* grandfather = parent->_parent;
      assert(grandfather); // 确定的可以断言下,否则就是插入前就不是红黑树
      assert(grandfather->_col == BLACK);
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
 
        if (uncle && uncle->_col == RED) // 情况一,叔叔存在且为红(可以直接复制到下面uncle在左边)
        {    // 将父亲和叔叔改为黑,祖父改为红,然后把祖父当成cur,parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三:叔叔存在且为黑或叔叔不存在
        {
          if(cur == parent->_left) // 情况二的右旋+变色(parent在左)
          {
            //     g      
            //   p   u
            // c
            RotateR(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的左右双旋+变色(parent在左)
          {
            //      g      
                        //   p     u
                        //    c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
 
        if (uncle && uncle->_col == RED) // 情况一,叔叔存在且为红
        {    // 将父亲和叔叔改为黑,祖父改为红,然后把祖父当成cur,parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三:叔叔存在且为黑或叔叔不存在
        {
          if (cur == parent->_right) // 情况二的左旋+变色(parent在右)
          {
            //     g      
            //   u   p
            //        c
            RotateL(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的右左双旋+变色(parent在右)
          {
            //       g      
            //    u     p
            //         c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    
    _root->_col = BLACK;
    return 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; // 黑色节点数量基准值
    //Node* cur = _root; // 这种方法是先遍历一遍,然后传值,不过我们可以传引用
    //while (cur)
    //{
    //  if (cur->_col == BLACK)
    //  {
    //    ++benchmark;
    //  }
    //  cur = cur->_left;
    //}
    return PrevCheck(_root, 0, benchmark); // 验证性质三和四
  }
 
protected:
  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不为空才更新
    {
      subRL->_parent = parent;
    }
 
    Node* ppNode = parent->_parent; // 记录parent的parent,防止parent是一颗子树的头结点
 
    subR->_left = parent; // 再更新两个指针
    parent->_parent = subR;
 
    if (_root == parent)  // 最后更新两个指针
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else // parent是一颗子树的头结点
    {
      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;
    }
  }
 
  Node* _root = nullptr;
};

在前一篇学习红黑树的时候,实现的是KV模型,节点中存放的是键值对pair。

而set中的节点只存放一个key值,map中的节点存放的是键值对。

但是map和set却使用的是同一颗红黑树。

这到底是怎么实现的呢?怎么做到一会儿是键值,一会又是键值对的呢?

看一下STL库中是如何实现的:

map和set中都既有key值,又有数据类型,map中的数据类型是键值对pair,


而set中的数据类型也是key值。STL模板中,红黑树中的数据类型只有一个。


无论是map还是set,底层封装的都是红黑树,


区别在于给红黑树实例化的是什么类型的模板参数。


map给红黑树传的模板参数是键值对pair。


set给红黑树传的模板参数是键值Key。


对于红黑树而言,它是不知道接收到的第二个模板参数value是什么类型的,


它只能推演。所以set对应的红黑树中的数据类型就是一个key值,


而map对应的红黑树中的数据类型就是一个键值对。


接下来就是对我们实现的红黑树进行改造,(配合上一篇一起看)


首先就是对结点进行改造,将原本的KV键值对数据类型改成T,像STL中一样,只有一个,


让编译器自己去推演这个数据类型是key值还是键值对:

template<class T>
struct RBTreeNode
{
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
 
  T _data; // 结点中的数据
  Colour _col; // 比AVL树少了平衡因子,多了颜色
 
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
  {}
};

红黑树中也不再用键值对去构建新节点,而是使用那一个数据类型T。

先改一点是这样的:

Set.h:

#pragma once
 
#include "RedBlackTree.h"
 
namespace rtx
{
  template <class K>
  class set
  {
  protected:
    RBTree <K, K> _t;
  };
}

Map.h:

#pragma once
 
#include "RedBlackTree.h"
 
namespace rtx
{
  template <class K,class V>
  class map
  {
  protected:
    RBTree <K, pair<K, V>> _t;
  };
}

set中,向红黑树传的模板参数是,第二个K传给节点,作为节点是数据类型。


map中,向红黑树传的模板参数是>键值对,


第二个参数键值对pair传给节点,作为节点的数据类型。


现在有一个问题,给红黑树传模板参数时,第一个参数K类型的作用是什么?


对于insert来说,set和map中都可以不要第一个参数K,因为第二个参数中就有K,


可以用来比较。但是对于find接口来说,它需要的只是K。set中第二个参数也是K,


所以第一个K也可以省略。map中第二个参数是一个键值对,如果省略了第一K后,


红黑树中只有一个键值对类型,在使用find的时候,无法确定拿到first的数据类型,


此时就需要第一个模板参数K来确定find的类型了。


虽然set中可以不需要第一个模板参数K,但是map不可以,因它两使用的一个红黑树,

所以为了统一,第一个模板参数K不能省略


2. 仿函数比较键值对

改了数据那插入的所有比较都要改了,


站在红黑树的角度,并不知道它接收到的模板参数value是来自set中的键值还是map中的键值对。


在插入结点进行比较时:


set:cur->data 与 data进行比较,插入结点中的key值直接和树中的key值比较大小,决定插入左还是右即可。


map:cur->data.first 与 data.first进行比较,插入结点中的键值对的first和树种键值对的first比较,决定插入左还是右。


既然使用的是模板,是泛型编程,那么在比较处到底该写成map和set中的哪种比较方式呢?


要知道set中的data不是键值对,是没有first的,而map中的data直接比较又不符合我们的要求。


(pair也能比较键值对,不过它在first一样时比较了second,但我们不想比较second)


(关于set和map的细节可以回去看看

此专栏第26篇,后面实现方括号也要知道细节,链接:从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别-CSDN博客)


此时我们也不能自己重新定义键值对的比较方式,因为库中已经有了,


我们无法再重载一个函数名,返回值,参数都相同的比较方式。


为了能够在红黑树中使用统一的比较方式,这里采用仿函数的方式:


在set和map中各定义一个仿函数,专门用来获取key值的,


并且将这个仿函数当作模板参数传给红黑树。

实现下仿函数和封装下insert,现在的部分代码就是这样:

set中存放的数据本身就是key,所以获取key时有点多此一举,但是为了和红黑树的结构以及map的结构统一,也需要写一个。

map中存放的数据是键值对,所以仿函数返回的是键值对中的first,依次来获取到key值。

在插入函数inset中,创建仿函数对象koft。


在需要进行键值key比较的位置,使用仿函数koft获取键值进行比较,然后决定插入左边函数右边。


使用仿函数的方法,压根就不用关心比较的是键值还是键值对,因为set和map都会给红黑树传它自己获取键值的仿函数,最终比较的都是键值。


set和map中的插入直接复用红黑树中的插入即可。


但是set中插入的是一个键值,而map中插入的是一个键值对。


跑一下测试用例:

#include "RedBlackTree.h"
#include "Set.h"
#include "Map.h"
 
namespace rtx
{
  void TestSet()
  {
    set<int> s;
    s.insert(1);
    s.insert(5);
    s.insert(3);
    s.insert(5);
  }
  void TestMap()
  {
    map<int,int> m;
    m.insert(make_pair(6, 1));
    m.insert(make_pair(2, 1));
    m.insert(make_pair(3, 1));
    m.insert(make_pair(2, 1));
  }
}
 
int main()
{
  rtx::TestSet();
  rtx::TestMap();
 
  return 0;
}

如果想遍历,那么就要实现迭代器了。

3. 红黑树迭代器的实现

这里实现的和库里的不太一样,库里的实现是带哨兵位头结点的,它指向根结点,

它的左指向中序遍历的第一个结点,右指向中序遍历的最后一个结点。

但不用哨兵位头结点也能实现,所以就不改了。

set和map的迭代器就是红黑树的迭代器:

这里可以参考list的迭代器,红黑树也是通过指针来链接的。

template<class T, class Ref, class Ptr>
struct __RBTreeInterator
{
public:
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T, Ref, Ptr> Self;
  Node* _node;
 
  __RBTreeIterator(Node* node)
    :_node(node)
  {}
};

最基本的迭代器如上面所示代码,迭代器中只有一个成员变量,那就是节点node。

下面就是逐渐完善迭代器支持的功能了,比如解引用,判断等于,加加,减减,等操作。

解引用+箭头+等于+不等于:(这里和链表是一样的,就不再详细讲解了)

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
public:
  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;
  }
};

比较的内容是两个迭代器指向节点是否相同,而不是节点中的值。

无论是普通对象还是const对象,都可以调用const版本,并且仅仅是进行比较,

所以只有const版本的就够用了。

从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(下):https://developer.aliyun.com/article/1522303?spm=a2c6h.13148508.setting.17.50c04f0es3cPJy

目录
相关文章
|
8天前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
11 2
|
8天前
|
存储 C++ 容器
【C++】map和set深度讲解(下)
【C++】map和set深度讲解(下)
19 2
|
8天前
|
存储 自然语言处理 Java
【C++】map和set深度讲解(上)
【C++】map和set深度讲解(上)
17 2
|
8天前
|
Java C++ Python
【C++】手撕红黑树
【C++】手撕红黑树
8 1
|
16天前
|
存储 C++ 容器
|
17天前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
18 1
|
8天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
14 0
|
14天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
24 0
|
17天前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(一)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(一)
11 0
|
22天前
|
自然语言处理 C语言 C++
程序与技术分享:C++写一个简单的解析器(分析C语言)
程序与技术分享:C++写一个简单的解析器(分析C语言)