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

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

从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(上):https://developer.aliyun.com/article/1522297

3.1 迭代器++

set和map迭代器的++按照中序遍历的顺序进行加加的。

时刻铭记中序遍历的顺序:左子树 根 右子树

现在设想 it 迭代器在树的任意一个位置,它++可以分为以下情况:

① 右子树存在:

当++it以后,it指向的应是右子树中的最左节点,如图所示。

解决步骤:

将当前it指向节点的有子节点开始,一直寻找最左节点。找到后,让it指向最左节点。

② 右子树不存在:

it处于下图所示位置,位于子树的最右边,当++it后,it会指向哪呢?

it的右子树为空,肯定不能像上面那样找右子树最左边的节点。


解决步骤:


it是parent的右子树,说明父节点parent已经被访问过了,所以还需要继续向上走。


garent又是grandfather的右子树,说明祖父节点grandfather也被访问过了,


所以还需要继续向上走。grandfather是它父节点的左子树,按照中序遍历的顺序,


grandfather的父节点还没有被访问,所以it应该指向这里,也就是grandfather->parent节点。

当it右子树不存在时,++it后,it指向的是it所在子树是左子树的最近祖宗节点


右子树不存在,如果it是中序最后一个节点呢?

当it指向的是红黑树最右边的节点时,再++it后,it应该指向最后一个节点的下一个节点。

但是红黑树最后一个节点的下一个节点并没有,所以我们让it指向nullptr。

我们按上面的步骤走,it也能指向空:

在代码中,无论是找到了++it后的位置,

还是it是最后一个节点,都会跳出循环,将it指向跳出循环的parent即可:

前置++:

  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)
      {   // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return *this;
  }

后置++和前置++的唯一不同就是返回的是++之前的位置,

其他操作都一样,所以在改变it指向的位置之前,需要提前记录下要返回的it。

后置++返回类型不能用引用,因为记录位置的临时变量会销毁:

  Self operator++(int)
  {
    Self ret = Self(_node); // 记录当前位置 最后返回
 
    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)
      {   // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return ret;
  }

3.2 迭代器--

迭代器减减的逻辑和加加是相反的,所以它的顺序应该是:右子树 根 左子树

① 左子树存在:


当左子树存在时,it减减后,应该指向的是左子树最右边的节点,如上图所示。


② 左子树不存在:

it是左子树,说明它的根节点就已经被访问过来,所以需要继续向上。

当找到it所在子树是右子树的最近祖宗时,将it指向这个祖宗节点。

因为是–,逻辑相反,所以此时减减it后,it指向it所在子树是右子树的最近祖宗节点,

同样,当it指向是第一个节点时,减减it会指向空节点。

前置--:

  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)
      {  // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况
        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)
      {  // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return *this;
  }

迭代器写好之后,还要在红黑树中封装它,因为我们都是通过红黑树来使用的。

begin返回的是中序遍历的第一个结点,end返回的是最后结点的下一个,所以直接给空:

3.3 map的operator[ ]

map有一个特有的[ ],可以实现查找,插入,修改三个功能,下面来实现一下。

(在讲解map的时候放过这段代码)

    V& operator[](const K& key)
    {
      pair<iterator, bool> ret = insert(make_pair(key, V()));
      return ret.first->second;
    }

需要对红黑树底层中的insert做修改:


1. 返回值改成pair<iterator, bool>   : pair<iterator, bool> Insert(const T& data)


2. 空树时返回根的迭代器和true的键值对:return make_pair(iterator(_root), true);


3. 存在新插入的数据,返回原本存在的数据的迭代器和false

4. 插入成功,返回新插入数据的迭代器和true

红黑树底层的inset已经被修改了,set和map中的insert也需要被修改,改返回值就行。


4. 完整代码

底层的迭代器做好了,下一步就需要把它封装到set和map中:

Set.h

#pragma once
 
#include "RedBlackTree.h"
 
namespace rtx
{
  template <class K>
  class set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    //必须得加关键字typename。
    //当模板类没有进行实例化时,它就是一张图纸,在编译的时候并不参与编译。
    //因为域作用限定符::的存在,编译器在处理这条语句的时候,可能会将::后的iterator当作静态变量处理,参与编译。
    //所以就需要加关键字typename来告诉编译器这是一个模板类型,暂时不参与编译。
 
    iterator begin()
    {
      return _t.begin();
    }
 
    iterator end()
    {
      return _t.end();
    }
 
    pair<iterator, bool> insert(const K& key)
    {
      return _t.Insert(key);
    }
  protected:
    RBTree <K, K, SetKeyOfT> _t;
  };
}

Map.h

#pragma once
 
#include "RedBlackTree.h"
 
namespace rtx
{
  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; // 为什么+typename在set里
 
    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;
    }
 
  protected:
    RBTree <K, pair<K, V>, MapKeyOfT> _t;
  };
}

RedBlackTree.h

#pragma once
 
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
 
enum Colour // 枚举颜色
{
  RED,
  BLACK
};
 
template<class T>
struct RBTreeNode
{
public:
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
 
  T _data; // 结点中的数据
  Colour _col; // 比AVL树少了平衡因子,多了颜色
 
  RBTreeNode(const T& data)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
  {}
};
 
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;
  }
 
  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)
      {   // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return *this;
  }
 
  Self operator++(int)
  {
    Self ret = Self(_node); // 记录当前位置 最后返回
 
    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)
      {   // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return ret;
  }
 
  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)
      {  // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return *this;
  }
 
  Self operator--(int)
  {
    Self ret = Self(_node); // 记录当前位置 最后返回
 
    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)
      {  // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况
        cur = cur->_parent;
        parent = parent->_parent;
      }
 
      _node = parent;
    }
 
    return ret;
  }
};
 
template<class K, class T, class KeyOfT> // KeyOfT仿函数,把key取出来
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) // 1. 返回值改成pair<iterator, bool>
  {
    KeyOfT kot; // 定义一个仿函数的对象
 
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_col = BLACK; // 根给黑色
      return make_pair(iterator(_root), true); // 2. 空树时返回根的迭代器和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(cur, false); // 3. 存在新插入的数据,返回原本存在的数据的迭代器和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* 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 make_pair(newnode, true); // 4. 插入成功,返回新插入数据的迭代器和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;
};

Test.cpp

#include "RedBlackTree.h"
#include "Set.h"
#include "Map.h"
 
namespace rtx
{
  void TestSet()
  {
    set<int> s;
    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);
 
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }
 
  void TestMap()
  {
    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;
    }
    cout << endl;
 
    for (const auto& kv : countMap) // 范围for也能用了(傻瓜替换)
    {
      cout << kv.first << ":" << kv.second << endl;
    }
  }
}
 
int main()
{
  rtx::TestSet();
  rtx::TestMap();
 
  return 0;
}


本篇完。

下一部分:(哈希)闭散列和开散列(哈希桶)的实现,再然后是unordered_set和unordered_map介绍+哈希桶封装。

目录
相关文章
|
3天前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
9 2
|
3天前
|
存储 C++ 容器
【C++】map和set深度讲解(下)
【C++】map和set深度讲解(下)
11 2
|
3天前
|
存储 自然语言处理 Java
【C++】map和set深度讲解(上)
【C++】map和set深度讲解(上)
15 2
|
9天前
|
存储 算法 C++
C++一分钟之-扁平化映射与unordered_map
【7月更文挑战第5天】C++的STL `unordered_map`是键值对的快速查找容器,基于哈希表。常见问题包括哈希函数选择、键类型限制、内存管理和迭代顺序不确定性。要避免问题,需优化哈希函数,确保自定义类型支持哈希和比较操作,合理管理内存,不依赖迭代顺序。提供的代码示例展示了如何为自定义类型定义哈希函数并操作`unordered_map`。正确使用能提升代码效率。
21 0
C++一分钟之-扁平化映射与unordered_map
|
3天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
11 0
|
9天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
14 0
|
11天前
|
C++ 容器
【C++】string类的使用①(迭代器接口begin,end,rbegin和rend)
迭代器接口是获取容器元素指针的成员函数。`begin()`返回首元素的正向迭代器,`end()`返回末元素之后的位置。`rbegin()`和`rend()`提供反向迭代器,分别指向尾元素和首元素之前。C++11增加了const版本以供只读访问。示例代码展示了如何使用这些迭代器遍历字符串。
|
19天前
|
Dart
Dart之集合详解(List、Set、Map)
Dart之集合详解(List、Set、Map)
19 1
|
24天前
|
存储 JavaScript 前端开发
JavaScript进阶-Map与Set集合
【6月更文挑战第20天】JavaScript的ES6引入了`Map`和`Set`,它们是高效处理集合数据的工具。`Map`允许任何类型的键,提供唯一键值对;`Set`存储唯一值。使用`Map`时,注意键可以非字符串,用`has`检查键存在。`Set`常用于数组去重,如`[...new Set(array)]`。了解它们的高级应用,如结构转换和高效查询,能提升代码质量。别忘了`WeakMap`用于弱引用键,防止内存泄漏。实践使用以加深理解。
|
19天前
|
Go
go语言map、实现set
go语言map、实现set
28 0