devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++【红黑树】_红黑树c++

作者：AllinToyou | 2024-03-16 02:01:03

赞

踩

红黑树c++

目录

一、什么是红黑树

红黑树的性质

情况一：cur为红，p为红，g为黑，u存在且为红

 case1：a/b/c/d/e是空树，cur是新增

case2：a/b/c/d/e不为空，cur是新增

 情况二：cur为红，p为红，g为黑，u不存在，或者u存在但是为黑色

case1：u不存在，cur是新增，a/b/c/d/e都是空树

case2：u存在且为黑

情况三：cur为红，p为红，g为黑，u不存在或者u存在且为黑色

case1：u不存在,cur就是新增的节点

case2：u存在且为黑

代码实现

检测代码

二、封装红黑树

写在set.h中的内容

写在map.h当中的内容

三、红黑树的迭代器

1.前置++

2.前置--

3.后置++和--

4.比较运算符的重载

5.*和->的重载

四、代码的汇总

1.RBTree.h

2.Map.h

3.set.h

4.main.cpp

一、什么是红黑树

AVLTree：要求左右高度差不超过1

红黑树：AVLTree过分严格，可能会导致过分的旋转，那能不能不要那么严格呢？

需要达到的目的，最长路径不超过最短路径的二倍。

也就是说，我们的AVLTree是严格平衡，我们的红黑树是不严格平衡，而是近似平衡

结果：相对而言，插入同样的数据，AVL树的旋转更多，红黑树的旋转次数更少

 假设N是100w，AVL树为logN的高度，也就是大概20左右

但是我们的红黑树的话，最短的高度大概是logN也就是20左右，最深的应该为2*logN，为40次左右。

红黑树的性质

1.每个结点不是红色，就是黑色

2.根节点是黑色的

3.如果一个节点是红色的，则它的两个孩子结点是黑色的（解读：树中没有连续的红色结点）

4.对于每个节点，从给结点到其所有的后代叶结点的简单路径上，均包含相同数目的黑色结点（解读：每条路径上的黑色结点的数量相等）

5.每个叶子结点都是黑色的（这里的叶子结点指的是空节点） 

 上面的图中一共有几条路径？

（从根节点到空节点才算一条路径）

一共有11条

 每个叶子结点都是黑色的（这里的叶子结点指的是空节点）

这里的叶子结点又称为NIL结点

为什么？

假设只有两个结点

 那么我们这里假设的是叶子结点（不是空节点）是黑色的，那么我们并不能做到每条路径上的黑色结点的数量是相等的。我们这里的叶子结点必须是红色的。

为什么这几条规则就能够保证最长的路径中的结点个数不超过最短路径的结点个数的两倍？

每条路径都有相同数量的黑的结点

那么极限的最短一定是全黑的路径。

那么极限的最长路径一定是在每个黑色结点之间插入一个红色的结点，也就是一黑一红排布的结点。

如果你把黑色的结点全部都拿出来，那么我们可以认为我们的树基本是一棵满二叉树了。 

新插入结点，插入什么颜色？

红色：规则三（如果一个节点是红色的，则它的两个孩子结点是黑色的（解读：树中没有连续的红色结点））

黑色：规则四 （对于每个节点，从给结点到其所有的后代叶结点的简单路径上，均包含相同数目的黑色结点（解读：每条路径上的黑色结点的数量相等））

明显插入红色的更加方便

我们这里插入结点需要变色+旋转

因为控制住了颜色，那么我们就能够将我们的高度给控制住 

这里我们先初步理解一下红黑树的调整方案 

  

 我们这里不妨假设在27的右子树的地方插入新节点，并且插入的新结点是红色的，为了满足我们的规则三，我们必须将我们的27结点设置成黑色的。因为不能有两个连续的红色结点。如果我们新插入的节点是黑色的话，就不满足我们上面新插入的结点是红色的原则了。

遇事不决看叔叔。

如果叔叔存在，也为红，那如果parent变黑了，那么叔叔和parent一起背锅，也变成黑色的 

 

为什么叔叔也要变成黑色的呢？

因为我们的parent的这条路径上多了一个黑色的结点，那么我们需要遵循我们的第四条规则，给我们uncle的这条结点也增加一个黑色结点.，所以我们将uncle结点也变成黑色的。

这里的祖父一定是黑色的，因为插入之前，我们的红黑树一定是满足规则的，所以我们的父亲是红色的话，我们的祖父节点一定是黑色的。

然后还是遵循第四条规则，每条路径上的黑色的结点的数目是一样的，所以我们需要将祖父结点的颜色从黑色变成红色的

 这样我们的黑色结点的数量就不会发生变化。

但是我们这里的17和25都是红色的，我们还需要继续向上调整 。

这一轮循环和我们上面这一轮调整是一样的，也就是cur的parent和cur都是红色的，然后我们需要将parent编程黑色的，同时将uncle也变成黑色的，然后将grandparent变成红色的 

 这里我们的cur再次指向grandparent的位置，然后我们发现我们此时的cur已经是根节点了，那么我们就停止调整了。

此时我们观察到其实我们每一条路径上都多了一个黑色的结点。 

我们发现这里的红黑树插入了这个新的节点之后，其实左右高度差已经超过了1，但是我们并没有进行旋转。

仅仅是变色，我们就让我们的红黑树再次满足了条件。  

但是上述的情况是叔叔结点存在且为红的情况，要是我们的叔叔结点为黑色呢？ 

那我们这个时候就不能仅仅是变色了。

我们此时的最长路径是5，最短路径是2，是右边高，左边第要是和我们刚刚一样，将parent和uncle都变成黑色的，那么我们的右边的parent所在的所有分支都会比我们左边的子树都多一个黑色的结点，那么我们就没办法仅仅是通过变色来调平衡了

我们需要像上面的旋转一样，将我们的15结点挂载到我们13的右节点，然后再将我们的13的这个结点变成红色的结点。从而满足我们红黑树的条件。

情况一：cur为红，p为红，g为黑，u存在且为红

cur是当前位置的结点

p是parent结点

g是grandfather结点

u是uncle结点

下面的是抽象图，代表着任意多种情况

a/b/c/d/e是我们符合红黑树规则的子树（子树根不一定为黑色的） 

 case1：a/b/c/d/e是空树，cur是新增

p和u变黑，g变红。

p,u变红是为了保证g下面的两颗子树的黑色结点个数相同

g变红是为了让我们的g这一条分支和我们的其他的分支的黑色的数目相同。因为我们的上一步操作，u和p变黑都让我们的这两条分支的黑色的结点个数都加了1，呢么g变红，恰好能让这两条路径的黑色结点-1

继续把g当成cur结点，向上继续迭代处理 

case2：a/b/c/d/e不为空，cur是新增

c/d/e应该是右边四种情况中的一种

cde的组合是4×4×4，插入的结点在ab的左子树和右子树，也是4种情况，所以256种情况，画不完。 

新增的结点可以在a,b的任意孩子位置。

 新插入的结点是红色的，将父亲和叔叔结点变黑，然后将祖父结点变成红色的。

如果g结点已经是根节点了，那么我们就将其变成黑色的 

所以上面两种的case的调整方案其实都是一样的。

都是变色

 情况二：cur为红，p为红，g为黑，u不存在，或者u存在但是为黑色

case1：u不存在，cur是新增，a/b/c/d/e都是空树

在p位置发生右旋，p变成黑色的，祖父变成红色的。

case2：u存在且为黑

新增结点可以在ab孩子的任意位置，de可以是空树或者是一个红结点，c可以是根是黑结点的子树，是下面四种情况中的任意一种

 

c的情况有4中，插入的位置可以是ab的任意子树，有4中，de一共有2×2种情况

所以是4×4×4种情况64

 叔叔存在且为黑，我们就在p的位置进行右旋，p变成根节点的位置，g变到p的右节点，然后p原先的右节点变成g的左子树，然后p变成黑色的，g变成红色的

所以上面两种的case的调整方案其实都是一样的。

都是单旋+变色

情况三：cur为红，p为红，g为黑，u不存在或者u存在且为黑色

这里按照我们上面的推测，我们不妨猜出我们的情况三是双旋+变色

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 则转换成了情况2 

case1：u不存在,cur就是新增的节点

 

case2：u存在且为黑

 新增的结点可以在bc的任意孩子位置，a为黑色，de为空树或者是红结点

a可以是下面四种的任意一种

a有四种，新增的结点可以在bc的任意孩子位置，有4中，然后de分别可以为空树或者是红结点，有4种情况，一共是4×4×4，为64种

也就是现在p点左单旋，然后再在g位置进行右单旋

将cur的左，变成p的右，cur变成g的左，然后cur的左节点变成p这个时候就变成情况2了

然后将cur转到根的位置，cur的右子树变成g的左子树，cur的右链接g

然后cur变成黑色的，g变成红色的 

红黑树的关键是看叔叔

如果叔叔存在且为红，变色，继续往上处理 

如果叔叔不存在或者存在且为黑，旋转+变色（单旋还是双旋，左单旋还是右单旋）

代码实现

  1. //插入和我们的avl树其实是差不多的
  2.     bool Insert(const pair<K, V>& kv)
  3.     {
  4.         if (_root == nullptr)
  5.         {
  6.             _root = new Node(kv);
  7.             //根节点必须是黑色的
  8.             _root->_col = BLACK;
  9.             return true;
  10.         }
  11.  
  12.         Node* parent = nullptr;
  13.         Node* cur = _root;
  14.         while (cur)
  15.         {
  16.             if (cur->_kv.first < kv.first)
  17.             {
  18.                 parent = cur;
  19.                 cur = cur->_right;
  20.             }
  21.             else if (cur->_kv.first > kv.first)
  22.             {
  23.                 parent = cur;
  24.                 cur = cur->_left;
  25.             }
  26.             else
  27.             {
  28.                 return false;
  29.             }
  30.         }
  31.  
  32.         cur = new Node(kv);
  33.         //新插入的接地那默认是红色的
  34.         cur->_col=RED;
  35.         if (parent->_kv.first < kv.first)
  36.         {
  37.             parent->_right = cur;
  38.         }
  39.         else
  40.         {
  41.             parent->_left = cur;
  42.         }
  43.  
  44.         cur->_parent = parent;
  45.  
  46.         //如果存在parent并且parent的节点的颜色为红色，按照我们不能有两个红色结点连在一起的原则，我们需要进行调整
  47.         while(parent &&parent->_col==RED)
  48.         {
  49.             Node* grandfather=parent->_parent;
  50.             assert(grandfather);
  51.             //父亲是红色的话，祖父结点一定是黑色的，不然我们的红黑树在我们的本次调整之前就已经不满足红黑树的条件了
  52.             assert(grandfather->_col==BLACK);
  53.             // 关键看叔叔
  54.             //父亲是祖父的左
  55.             if (parent == grandfather->_left)
  56.             {
  57.                 Node* uncle = grandfather->_right;
  58.                 // 情况一 : uncle存在且为红，变色+继续往上处理
  59.                 if (uncle && uncle->_col == RED)
  60.                 {
  61.                     //父亲和叔叔全部都变成黑色的，把祖父变成红色的
  62.                     parent->_col = uncle->_col = BLACK;
  63.                     grandfather->_col = RED;
  64.                     // 继续往上处理，将祖父当成cur结点，然后再将cur的父亲找到
  65.                     cur = grandfather;
  66.                     parent = cur->_parent;
  67.                 }
  68.                 // 情况二+三：uncle不存在 + 存在且为黑
  69.                 //看是单旋还是双旋
  70.                 else
  71.                 {
  72.                     // 情况二：右单旋+变色
  73.                     //     g
  74.                     //   p   u
  75.                     // c
  76.                     //cur是父节点的左子树，左边高，右单旋+变色
  77.                     if (cur == parent->_left)
  78.                     {
  79.                         //对祖父的位置进行右旋
  80.                         RotateR(grandfather);
  81.                         parent->_col = BLACK;
  82.                         grandfather->_col = RED;
  83.                     }
  84.                     else
  85.                     {
  86.                         // 情况三：左右单旋+变色
  87.                         //     g
  88.                         //   p   u
  89.                         //     c
  90.                         RotateL(parent);
  91.                         RotateR(grandfather);
  92.                         cur->_col = BLACK;
  93.                         grandfather->_col = RED;
  94.                     }
  95.  
  96.                     break;
  97.                 }
  98.             }
  99.             //父亲是祖父的右结点
  100.             else // (parent == grandfather->_right)
  101.             {
  102.                 Node* uncle = grandfather->_left;
  103.                 // 情况一
  104.                 if (uncle && uncle->_col == RED)
  105.                 {
  106.                     parent->_col = uncle->_col = BLACK;
  107.                     grandfather->_col = RED;
  108.                     // 继续往上处理
  109.                     cur = grandfather;
  110.                     parent = cur->_parent;
  111.                 }
  112.                 else
  113.                 {
  114.                     // 情况二：左单旋+变色
  115.                     //     g
  116.                     //   u   p
  117.                     //         c
  118.                     if (cur == parent->_right)
  119.                     {
  120.                         RotateL(grandfather);
  121.                         //父亲的颜色变黑，祖父的颜色变红
  122.                         parent->_col = BLACK;
  123.                         grandfather->_col = RED;
  124.                     }
  125.                     else
  126.                     {
  127.                         // 情况三：右左单旋+变色
  128.                         //     g
  129.                         //   u   p
  130.                         //     c
  131.                         //先以parent的位置进行右单旋，然后再祖父结点进行左单旋
  132.                         RotateR(parent);
  133.                         RotateL(grandfather);
  134.                         //cur变黑，祖父变红
  135.                         cur->_col = BLACK;
  136.                         grandfather->_col = RED;
  137.                     }
  138.  
  139.                     break;
  140.                 }
  141.             }
  142.             //永远将根节点设置为黑色
  143.         _root->_col = BLACK;
  144.         return true;
  145.         }
  146.  
  147.     }

  1. void _InOrder(Node* root)
  2.     {
  3.         if (root == nullptr)
  4.         {
  5.             return;
  6.         }
  7.  
  8.         _InOrder(root->_left);
  9.         cout << root->_kv.first << ":" << root->_kv.second << endl;
  10.         _InOrder(root->_right);
  11.     }

检测代码

我们可以看颜色，或者看高度

但是高度差不超过2倍不一定是红黑树，只有颜色符号我们的四个规则，才是我们的红黑树。

  1. bool IsBalance()
  2.     {
  3.         //空树可以认为是红黑树
  4.         if (_root == nullptr)
  5.         {
  6.             return true;
  7.         }
  8.  
  9.         //根节点的颜色一定要是黑色
  10.         if (_root->_col == RED)
  11.         {
  12.             cout << "根节点不是黑色" << endl;
  13.             return false;
  14.         }
  15.  
  16.         // 黑色节点数量基准值
  17.  
  18.         int benchmark = 0;
  19.  
  20.         return PrevCheck(_root, 0, benchmark);
  21.     }
  22.  
  23. //在递归中，blackNum记录根节点--大年结点路径上的黑色结点的数量
  24.     //前序递归遍历即可，深度优先遍历，遍历到根节点，返回这一条路径的所有的黑色结点统计出来的数量
  25.     bool PrevCheck(Node* root, int blackNum, int& benchmark)
  26.     {
  27.         if (root == nullptr)
  28.         {
  29.             //cout << blackNum << endl;
  30.             //return;
  31.  
  32.             //根节点一定是黑色的，只要我们走完第一条路径，将其benchmark更新成第一条路径的黑色结点的个数
  33.             //然后再看其他路径的benchmark也就是黑色结点的数量是不是和我们第一条的路径的黑色节点的数目一样。
  34.             if (benchmark == 0)
  35.             {
  36.                 //记录黑色结点的数量
  37.                 benchmark = blackNum;
  38.                 return true;
  39.             }
  40.  
  41.             if (blackNum != benchmark)
  42.             {
  43.                 cout << "某条黑色节点的数量不相等" << endl;
  44.                 return false;
  45.             }
  46.             else
  47.             {
  48.                 //如果是相等的话，就return true返回给上一层
  49.                 return true;
  50.             }
  51.         }
  52.         //如果是黑色，记录黑色的数量+1
  53.         if (root->_col == BLACK)
  54.         {
  55.             ++blackNum;
  56.         }
  57.  
  58.         //不检查孩子，遇到红结点去检查父亲结点的颜色
  59.         if (root->_col == RED && root->_parent->_col == RED)
  60.         {
  61.             cout << "存在连续的红色节点" << endl;
  62.             return false;
  63.         }
  64.         
  65.         //递归遍历当前结点的左子树和右子树
  66.         return PrevCheck(root->_left, blackNum, benchmark)
  67.                && PrevCheck(root->_right, blackNum, benchmark);
  68.     }
  69.  
  70.     void _InOrder(Node* root)
  71.     {
  72.         if (root == nullptr)
  73.         {
  74.             return;
  75.         }
  76.  
  77.         _InOrder(root->_left);
  78.         cout << root->_kv.first << ":" << root->_kv.second << endl;
  79.         _InOrder(root->_right);
  80.     }

  1. void TestRBTree1()
  2. {
  3.     int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 0,5,30,25,20,4,13,30,28,27};  // 测试双旋平衡因子调节
  4.     //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  5.     RBTree<int, int> t1;
  6.     for (auto e : a)
  7.     {
  8.         t1.Insert(make_pair(e, e));
  9.     }
  10.  
  11.     t1.InOrder();
  12.     cout << "IsBalance:" << t1.IsBalance() << endl;
  13. }

 随机数据测试代码

  1. void TestRBTree2()
  2. {
  3.     size_t N = 1000;
  4.     srand(time(0));
  5.     RBTree<int, int> t1;
  6.     for (size_t i = 0; i < N; ++i)
  7.     {
  8.         int x = rand();
  9.         cout << "Insert:" << x << ":" << i << endl;
  10.         t1.Insert(make_pair(x, i));
  11.     }
  12.     cout << "IsBalance:" << t1.IsBalance() << endl;
  13. }

 

二、封装红黑树

我们看一下STL底层是怎么将红黑树封装成map和set的

如果是set的话，我们的key_type和value_type其实都是key

如果是map的话，我们的key_type是key，而我们的value_type是pair<const key,T>

也就是说，我们可以用一棵泛型结构的红黑树，通过不同的实例化参数，实现我们的set和map， 

这样就实现了代码复用。

这和我们之前的普通迭代器和const迭代器，正向迭代器和反向迭代器的时候是一样的。 

写在set.h中的内容

  1.  
  2. #ifndef RBTREE_SET_H
  3. #define RBTREE_SET_H
  4. #include "RBTree.h"
  5. namespace zhuyuan
  6. {
  7.     template<class K>
  8.     class set
  9.     {
  10.         struct SetKeyOfT
  11.         {
  12.             const K& operator()(const K& key)
  13.             {
  14.                 return key;
  15.             }
  16.         };
  17.     public:
  18.         typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
  19.         typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
  20.  
  21.         iterator begin()
  22.         {
  23.             return _t.Begin();
  24.         }
  25.  
  26.         iterator end()
  27.         {
  28.             return _t.End();
  29.         }
  30.  
  31.         pair<iterator, bool> insert(const K& key)
  32.         {
  33.             //pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
  34.             auto ret = _t.Insert(key);
  35.             return pair<iterator, bool>(iterator(ret.first._node), ret.second);
  36.         }
  37.  
  38.         iterator find(const K& key)
  39.         {
  40.             return _t.Find(key);
  41.         }
  42.     private:
  43.         RBTree<K, K, SetKeyOfT> _t;
  44.     };
  45.  
  46.     
  47. }
  48. #endif //RBTREE_SET_H

写在map.h当中的内容

  1. #ifndef RBTREE_MAP_H
  2. #define RBTREE_MAP_H
  3. #include "RBTree.h"
  4. namespace zhuyuan
  5. {
  6.     template<class K, class V>
  7.     class map
  8.     {
  9.         struct MapKeyOfT
  10.         {
  11.             const K& operator()(const pair<K, V>& kv)
  12.             {
  13.                 return kv.first;
  14.             }
  15.         };
  16.     public:
  17.         typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
  18.         typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
  19.  
  20.         iterator begin()
  21.         {
  22.             return _t.Begin();
  23.         }
  24.  
  25.         iterator end()
  26.         {
  27.             return _t.End();
  28.         }
  29.  
  30.         pair<iterator, bool> insert(const pair<K, V>& kv)
  31.         {
  32.             return _t.Insert(kv);
  33.         }
  34.  
  35.         iterator find(const K& key)
  36.         {
  37.             return _t.Find(key);
  38.         }
  39.  
  40.         V& operator[](const K& key)
  41.         {
  42.             pair<iterator, bool> ret = insert(make_pair(key, V()));
  43.             return ret.first->second;
  44.         }
  45.  
  46.     private:
  47.         RBTree<K, pair<K, V>, MapKeyOfT> _t;
  48.     };
  49.  
  50. }
  51. #endif //RBTREE_MAP_H

三、红黑树的迭代器

1.前置++

中序：左子树 根 右子树

1、右子树不为空，++就是找右子树中序第一个（最左节点）

2、右子树为空，我当前这棵树访问完了，++找孩子不是父亲右的那个祖先

7是6的右孩子，7结束之后找到6,6不是8的右子树，所以访问8

3、父亲是空，也就是找到了根节点的位置，根节点是没有父节点的，所以停止搜索。

（如果有哨兵位的头结点的话，就走到哨兵位的头结点）

  1. //前置++
  2.     Self& operator++()
  3.     {
  4.         if(_node->_right)
  5.         {
  6.             //下一个就是右子树的最左节点
  7.             Node *left=_node->_right;
  8.             while(left->_left)
  9.             {
  10.                 left=left->_left;
  11.             }
  12.             _node=left;
  13.             
  14.         }
  15.         else
  16.         {
  17.             //如果右为空
  18.             //找祖先里面孩子不是祖先的右的那一个
  19.             Node* parent=_node->_parent;
  20.             Node* cur=_node;
  21.             //如果是父亲的右子树，就一直往上走
  22.             //如果parent已经为空，那么就停止循环，parent已经到达了我们的end的位置
  23.             while(parent&&cur==parent->_right)
  24.             {
  25.                 cur=cur->_parent;
  26.                 parent=parent->_parent;
  27.             }
  28.             
  29.             _node=parent;
  30.         }
  31.         return *this;
  32.     }

 2.前置--

1、当前结点的左子树不为空，访问左子树的最右结点

2、孩子是父亲的右的时候，访问父亲，孩子是父亲的左的时候，返回到上一层，再次判断

  1. //前置--
  2.     Self& operator--()
  3.     {
  4.  
  5.         if(_node->_left)
  6.         {
  7.             //下一个是左子树的最右节点
  8.             Node* right=_node->_left;
  9.             while(right->_right)
  10.             {
  11.                 right=right->_right;
  12.             }
  13.             _node=right;
  14.         }
  15.         else
  16.         {
  17.             //孩子不是父亲的左的那个祖先
  18.             Node* parent=_node->_parent;
  19.             Node* cur=_node;
  20.             //如果是父亲的右子树，就一直往上走
  21.             //如果parent已经为空，那么就停止循环，parent已经到达了我们的end的位置
  22.             while(parent&&cur==parent->_left)
  23.             {
  24.                 cur=cur->_parent;
  25.                 parent=parent->_parent;
  26.             }
  27.  
  28.             _node=parent;
  29.         }
  30.         return *this;
  31.     }

3.后置++和--

  1.  Self operator--(int)
  2.     {
  3.         Self tmp(*this);
  4.  
  5.         --(*this);
  6.  
  7.         return tmp;
  8.     }
  9.  
  10.  Self operator++(int)
  11.     {
  12.         Self tmp(*this);
  13.  
  14.         ++(*this);
  15.  
  16.         return tmp;
  17.     }

4.比较运算符的重载

  1.     bool operator!=(const Self& s) const
  2.     {
  3.         return _node !=s._node;
  4.     }
  5.  
  6.     bool operator==(const Self& s) const
  7.     {
  8.         return _node ==s._node;
  9.     }

5.*和->的重载

  1. Ref operator*()
  2.     {
  3.         return _node->_data;
  4.     }
  5.     Ptr operator->()
  6.     {
  7.         return &_node->_data;
  8.     }

四、代码的汇总

1.RBTree.h

  1. #ifndef RBTREE_RBTREE_H
  2. #define RBTREE_RBTREE_H
  3. #pragma once
  4.  
  5. enum Colour
  6. {
  7.     //枚举红色和黑色
  8.     RED,
  9.     BLACK
  10. };
  11.  
  12. template<class T>
  13. struct RBTreeNode
  14. {
  15.     //和avl树一样都是三叉链
  16.     RBTreeNode<T>* _right;
  17.     RBTreeNode<T>* _left;
  18.     RBTreeNode<T>* _parent;
  19.  
  20.     //pair<K, V> _kv;
  21.     T _data;//数据
  22.     Colour _col;
  23.  
  24.     RBTreeNode(const T&data)
  25.             :_left(nullptr)
  26.             , _right(nullptr)
  27.             , _parent(nullptr)
  28.             , _data(data)
  29.     {}
  30. };
  31.  
  32. template<class T,class Ref,class Ptr>
  33. struct __RBTreeIterator
  34. {
  35.     typedef RBTreeNode<T> Node;
  36.     typedef __RBTreeIterator<T,Ref,Ptr> Self;
  37.     Node * _node;
  38.  
  39.     __RBTreeIterator(Node* node)
  40.         :_node(node)
  41.     {}
  42.  
  43.     Ref operator*()
  44.     {
  45.         return _node->_data;
  46.     }
  47.     Ptr operator->()
  48.     {
  49.         return &_node->_data;
  50.     }
  51.  
  52.     bool operator!=(const Self& s) const
  53.     {
  54.         return _node !=s._node;
  55.     }
  56.  
  57.     bool operator==(const Self& s) const
  58.     {
  59.         return _node ==s._node;
  60.     }
  61.  
  62.     //前置++
  63.     Self& operator++()
  64.     {
  65.         if(_node->_right)
  66.         {
  67.             //下一个就是右子树的最左节点
  68.             Node *left=_node->_right;
  69.             while(left->_left)
  70.             {
  71.                 left=left->_left;
  72.             }
  73.             _node=left;
  74.  
  75.         }
  76.         else
  77.         {
  78.             //如果右为空
  79.             //找祖先里面孩子不是祖先的右的那一个
  80.             Node* parent=_node->_parent;
  81.             Node* cur=_node;
  82.             //如果是父亲的右子树，就一直往上走
  83.             //如果parent已经为空，那么就停止循环，parent已经到达了我们的end的位置
  84.             while(parent&&cur==parent->_right)
  85.             {
  86.                 cur=cur->_parent;
  87.                 parent=parent->_parent;
  88.             }
  89.  
  90.             _node=parent;
  91.         }
  92.         return *this;
  93.     }
  94.  
  95.     Self operator++(int)
  96.     {
  97.         Self tmp(*this);
  98.  
  99.         ++(*this);
  100.  
  101.         return tmp;
  102.     }
  103.     //前置--
  104.     Self& operator--()
  105.     {
  106.  
  107.         if(_node->_left)
  108.         {
  109.             //下一个是左子树的最右节点
  110.             Node* right=_node->_left;
  111.             while(right->_right)
  112.             {
  113.                 right=right->_right;
  114.             }
  115.             _node=right;
  116.         }
  117.         else
  118.         {
  119.             //孩子不是父亲的左的那个祖先
  120.             Node* parent=_node->_parent;
  121.             Node* cur=_node;
  122.             //如果是父亲的右子树，就一直往上走
  123.             //如果parent已经为空，那么就停止循环，parent已经到达了我们的end的位置
  124.             while(parent&&cur==parent->_left)
  125.             {
  126.                 cur=cur->_parent;
  127.                 parent=parent->_parent;
  128.             }
  129.  
  130.             _node=parent;
  131.         }
  132.         return *this;
  133.     }
  134.  
  135.     Self operator--(int)
  136.     {
  137.         Self tmp(*this);
  138.  
  139.         --(*this);
  140.  
  141.         return tmp;
  142.     }
  143. };
  144. //KeyofT将T里面的key取出来
  145. template<class K, class T,class KeyOfT>
  146. struct RBTree
  147. {
  148.     typedef RBTreeNode<T> Node;
  149. public:
  150.     typedef __RBTreeIterator<T,T&,T*> iterator;
  151.     typedef __RBTreeIterator<T,const T&,const T*> const_iterator;
  152.  
  153.     iterator Begin()
  154.     {
  155.         Node* left=_root;
  156.         while(left&&left->_left)
  157.         {
  158.             left=left->_left;
  159.         }
  160.  
  161.         return iterator(left);
  162.     }
  163.  
  164.     iterator End()
  165.     {
  166.         return iterator(nullptr);
  167.     }
  168.  
  169.     const_iterator Begin() const
  170.     {
  171.         Node* subLeft = _root;
  172.         while (subLeft && subLeft->_left)
  173.         {
  174.             subLeft = subLeft->_left;
  175.         }
  176.  
  177.         return const_iterator(subLeft);
  178.     }
  179.  
  180.     const_iterator End() const
  181.     {
  182.         return const_iterator(nullptr);
  183.     }
  184.     //插入和我们的avl树其实是差不多的
  185.     pair<iterator ,bool>Insert(const T&data)
  186.     {
  187.         //实例化仿函数对象
  188.         KeyOfT kot;
  189.  
  190.         if (_root == nullptr)
  191.         {
  192.             _root = new Node(data);
  193.             //根节点必须是黑色的
  194.             _root->_col = BLACK;
  195.             return make_pair(iterator(_root),true);
  196.         }
  197.  
  198.         Node* parent = nullptr;
  199.         Node* cur = _root;
  200.         while (cur)
  201.         {
  202.             if (kot(cur->_data) < kot(data))
  203.             {
  204.                 parent = cur;
  205.                 cur = cur->_right;
  206.             }
  207.             else if (kot(cur->_data) > kot(data))
  208.             {
  209.                 parent = cur;
  210.                 cur = cur->_left;
  211.             }
  212.             else
  213.             {
  214.                 return make_pair(iterator(cur),true);
  215.             }
  216.         }
  217.  
  218.         cur = new Node(data);
  219.         Node* newnode=cur;
  220.         //新插入的接地那默认是红色的
  221.         cur->_col=RED;
  222.         if (kot(parent->_data) < kot(data))
  223.         {
  224.             parent->_right = cur;
  225.         }
  226.         else
  227.         {
  228.             parent->_left = cur;
  229.         }
  230.  
  231.         cur->_parent = parent;
  232.  
  233.         //如果存在parent并且parent的节点的颜色为红色，按照我们不能有两个红色结点连在一起的原则，我们需要进行调整
  234.         while(parent &&parent->_col==RED)
  235.         {
  236.             Node* grandfather=parent->_parent;
  237.             assert(grandfather);
  238.             //父亲是红色的话，祖父结点一定是黑色的，不然我们的红黑树在我们的本次调整之前就已经不满足红黑树的条件了
  239.             assert(grandfather->_col==BLACK);
  240.             // 关键看叔叔
  241.             //父亲是祖父的左
  242.             if (parent == grandfather->_left)
  243.             {
  244.                 Node* uncle = grandfather->_right;
  245.                 // 情况一 : uncle存在且为红，变色+继续往上处理
  246.                 if (uncle && uncle->_col == RED)
  247.                 {
  248.                     //父亲和叔叔全部都变成黑色的，把祖父变成红色的
  249.                     parent->_col = uncle->_col = BLACK;
  250.                     grandfather->_col = RED;
  251.                     // 继续往上处理，将祖父当成cur结点，然后再将cur的父亲找到
  252.                     cur = grandfather;
  253.                     parent = cur->_parent;
  254.                 }
  255.                 // 情况二+三：uncle不存在 + 存在且为黑
  256.                 //看是单旋还是双旋
  257.                 else
  258.                 {
  259.                     // 情况二：右单旋+变色
  260.                     //     g
  261.                     //   p   u
  262.                     // c
  263.                     //cur是父节点的左子树，左边高，右单旋+变色
  264.                     if (cur == parent->_left)
  265.                     {
  266.                         //对祖父的位置进行右旋
  267.                         RotateR(grandfather);
  268.                         parent->_col = BLACK;
  269.                         grandfather->_col = RED;
  270.                     }
  271.                     else
  272.                     {
  273.                         // 情况三：左右单旋+变色
  274.                         //     g
  275.                         //   p   u
  276.                         //     c
  277.                         RotateL(parent);
  278.                         RotateR(grandfather);
  279.                         cur->_col = BLACK;
  280.                         grandfather->_col = RED;
  281.                     }
  282.  
  283.                     break;
  284.                 }
  285.             }
  286.             //父亲是祖父的右结点
  287.             else // (parent == grandfather->_right)
  288.             {
  289.                 Node* uncle = grandfather->_left;
  290.                 // 情况一
  291.                 if (uncle && uncle->_col == RED)
  292.                 {
  293.                     //变色
  294.                     parent->_col = uncle->_col = BLACK;
  295.                     grandfather->_col = RED;
  296.                     // 继续往上处理
  297.                     cur = grandfather;
  298.                     parent = cur->_parent;
  299.                 }
  300.                 else
  301.                 {
  302.                     // 情况二：左单旋+变色
  303.                     //     g
  304.                     //   u   p
  305.                     //         c
  306.                     if (cur == parent->_right)
  307.                     {
  308.                         RotateL(grandfather);
  309.                         //父亲的颜色变黑，祖父的颜色变红
  310.                         parent->_col = BLACK;
  311.                         grandfather->_col = RED;
  312.                     }
  313.                     else
  314.                     {
  315.                         // 情况三：右左单旋+变色
  316.                         //     g
  317.                         //   u   p
  318.                         //     c
  319.                         //先以parent的位置进行右单旋，然后再祖父结点进行左单旋
  320.                         RotateR(parent);
  321.                         RotateL(grandfather);
  322.                         //cur变黑，祖父变红
  323.                         cur->_col = BLACK;
  324.                         grandfather->_col = RED;
  325.                     }
  326.  
  327.                     break;
  328.                 }
  329.             }
  330.  
  331.         }
  332.         //永远将根节点设置为黑色
  333.         _root->_col = BLACK;
  334.         return make_pair(iterator(newnode),true);
  335.     }
  336.     void InOrder()
  337.     {
  338.         _InOrder(_root);
  339.         cout << endl;
  340.     }
  341.  
  342.     bool IsBalance()
  343.     {
  344.         //空树可以认为是红黑树
  345.         if (_root == nullptr)
  346.         {
  347.             return true;
  348.         }
  349.  
  350.         //根节点的颜色一定要是黑色
  351.         if (_root->_col == RED)
  352.         {
  353.             cout << "根节点不是黑色" << endl;
  354.             return false;
  355.         }
  356.  
  357.         // 黑色节点数量基准值
  358.  
  359.         int benchmark = 0;
  360.         /*Node* cur = _root;
  361.         while (cur)
  362.         {
  363.         if (cur->_col == BLACK)
  364.         ++benchmark;
  366.         cur = cur->_left;
  367.         }*/
  368.  
  369.         return PrevCheck(_root, 0, benchmark);
  370.     }
  371. private:
  372.     //在递归中，blackNum记录根节点--大年结点路径上的黑色结点的数量
  373.     //前序递归遍历即可，深度优先遍历，遍历到根节点，返回这一条路径的所有的黑色结点统计出来的数量
  374.     bool PrevCheck(Node* root, int blackNum, int& benchmark)
  375.     {
  376.         if (root == nullptr)
  377.         {
  378.             //cout << blackNum << endl;
  379.             //return;
  380.             if (benchmark == 0)
  381.             {
  382.                 //记录黑色结点的数量
  383.                 benchmark = blackNum;
  384.                 return true;
  385.             }
  386.  
  387.             if (blackNum != benchmark)
  388.             {
  389.                 cout << "某条黑色节点的数量不相等" << endl;
  390.                 return false;
  391.             }
  392.             else
  393.             {
  394.                 return true;
  395.             }
  396.         }
  397.         //如果是黑色，记录黑色的数量+1
  398.         if (root->_col == BLACK)
  399.         {
  400.             ++blackNum;
  401.         }
  402.  
  403.         if (root->_col == RED && root->_parent->_col == RED)
  404.         {
  405.             cout << "存在连续的红色节点" << endl;
  406.             return false;
  407.         }
  408.  
  409.         //递归遍历当前结点的左子树和右子树
  410.         return PrevCheck(root->_left, blackNum, benchmark)
  411.                && PrevCheck(root->_right, blackNum, benchmark);
  412.     }
  413.  
  414.     void _InOrder(Node* root)
  415.     {
  416.         if (root == nullptr)
  417.         {
  418.             return;
  419.         }
  420.  
  421.         _InOrder(root->_left);
  422.         cout << root->_kv.first << ":" << root->_kv.second << endl;
  423.         _InOrder(root->_right);
  424.     }
  425.  
  426.     void RotateL(Node* parent)
  427.     {
  428.         Node* subR = parent->_right;
  429.         Node* subRL = subR->_left;
  430.  
  431.         parent->_right = subRL;
  432.         if (subRL)
  433.             subRL->_parent = parent;
  434.  
  435.         Node* ppNode = parent->_parent;
  436.  
  437.         subR->_left = parent;
  438.         parent->_parent = subR;
  439.  
  440.         if (_root == parent)
  441.         {
  442.             _root = subR;
  443.             subR->_parent = nullptr;
  444.         }
  445.         else
  446.         {
  447.             if (ppNode->_left == parent)
  448.             {
  449.                 ppNode->_left = subR;
  450.             }
  451.             else
  452.             {
  453.                 ppNode->_right = subR;
  454.             }
  455.  
  456.             subR->_parent = ppNode;
  457.         }
  458.  
  459.     }
  460.  
  461.     void RotateR(Node* parent)
  462.     {
  463.         Node* subL = parent->_left;
  464.         Node* subLR = subL->_right;
  465.  
  466.         parent->_left = subLR;
  467.         if (subLR)
  468.         {
  469.             subLR->_parent = parent;
  470.         }
  471.  
  472.         Node* ppNode = parent->_parent;
  473.  
  474.         subL->_right = parent;
  475.         parent->_parent = subL;
  476.  
  477.         if (_root == parent)
  478.         {
  479.             _root = subL;
  480.             subL->_parent = nullptr;
  481.         }
  482.         else
  483.         {
  484.             if (ppNode->_left == parent)
  485.             {
  486.                 ppNode->_left = subL;
  487.             }
  488.             else
  489.             {
  490.                 ppNode->_right = subL;
  491.             }
  492.  
  493.             subL->_parent = ppNode;
  494.         }
  495.  
  496.     }
  497.     iterator Find(const K& key)
  498.     {
  499.         Node* cur = _root;
  500.         KeyOfT kot;
  501.         while (cur)
  502.         {
  503.             if (kot(cur->_data) < key)
  504.             {
  505.                 cur = cur->_right;
  506.             }
  507.             else if (kot(cur->_data) > key)
  508.             {
  509.                 cur = cur->_left;
  510.             }
  511.             else
  512.             {
  513.                 return iterator(cur);
  514.             }
  515.         }
  516.  
  517.         return End();
  518.     }
  519. private:
  520.     //定义根节点的缺省值
  521.     Node* _root = nullptr;
  522. };
  523.  
  524. #endif //RBTREE_RBTREE_H

2.Map.h

  1. #ifndef RBTREE_MAP_H
  2. #define RBTREE_MAP_H
  3. #include "RBTree.h"
  4. namespace zhuyuan
  5. {
  6.     template<class K, class V>
  7.     class map
  8.     {
  9.         struct MapKeyOfT
  10.         {
  11.             const K& operator()(const pair<K, V>& kv)
  12.             {
  13.                 return kv.first;
  14.             }
  15.         };
  16.     public:
  17.         typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
  18.         typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
  19.  
  20.         iterator begin()
  21.         {
  22.             return _t.Begin();
  23.         }
  24.  
  25.         iterator end()
  26.         {
  27.             return _t.End();
  28.         }
  29.  
  30.         pair<iterator, bool> insert(const pair<K, V>& kv)
  31.         {
  32.             return _t.Insert(kv);
  33.         }
  34.  
  35.         iterator find(const K& key)
  36.         {
  37.             return _t.Find(key);
  38.         }
  39.  
  40.         V& operator[](const K& key)
  41.         {
  42.             pair<iterator, bool> ret = insert(make_pair(key, V()));
  43.             return ret.first->second;
  44.         }
  45.  
  46.     private:
  47.         RBTree<K, pair<K, V>, MapKeyOfT> _t;
  48.     };
  49.  
  50.     void test_map1()
  51.     {
  52.         map<string, int> m;
  53.         m.insert(make_pair("111", 1));
  54.         m.insert(make_pair("555", 5));
  55.         m.insert(make_pair("333", 3));
  56.         m.insert(make_pair("222", 2));
  57.  
  58.         map<string, int>::iterator it = m.begin();
  59.         while (it != m.end())
  60.         {
  61.             cout << it->first << ":" << it->second << endl;
  62.             ++it;
  63.         }
  64.         cout << endl;
  65.  
  66.         for (auto& kv : m)
  67.         {
  68.             cout << kv.first << ":" << kv.second << endl;
  69.         }
  70.         cout << endl;
  71.     }
  72.  
  73.     void test_map2()
  74.     {
  75.         string arr[] = { "ƻ", "", "ƻ", "", "ƻ", "ƻ", "", "ƻ", "㽶", "ƻ", "㽶" };
  76.  
  77.         map<string, int> countMap;
  78.         for (auto& str : arr)
  79.         {
  80.             countMap[str]++;
  81.         }
  82.  
  83.         for (const auto& kv : countMap)
  84.         {
  85.             cout << kv.first << ":" << kv.second << endl;
  86.         }
  87.     }
  88.  
  89.     void test_map3()
  90.     {
  91.         map<string, string> dict;
  92.         dict["insert"];
  93.         dict["insert"] = "";
  94.         dict["left"] = "";
  95.  
  96.     }
  97. }
  98. #endif //RBTREE_MAP_H

3.set.h

  1. #ifndef RBTREE_SET_H
  2. #define RBTREE_SET_H
  3. #include "RBTree.h"
  4. namespace zhuyuan
  5. {
  6.     template<class K>
  7.     class set
  8.     {
  9.         struct SetKeyOfT
  10.         {
  11.             const K& operator()(const K& key)
  12.             {
  13.                 return key;
  14.             }
  15.         };
  16.     public:
  17.         typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
  18.         typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
  19.  
  20.         iterator begin()
  21.         {
  22.             return _t.Begin();
  23.         }
  24.  
  25.         iterator end()
  26.         {
  27.             return _t.End();
  28.         }
  29.  
  30.         pair<iterator, bool> insert(const K& key)
  31.         {
  32.             //pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
  33.             auto ret = _t.Insert(key);
  34.             return pair<iterator, bool>(iterator(ret.first._node), ret.second);
  35.         }
  36.  
  37.         iterator find(const K& key)
  38.         {
  39.             return _t.Find(key);
  40.         }
  41.     private:
  42.         RBTree<K, K, SetKeyOfT> _t;
  43.     };
  44.  
  45.     void test_set1()
  46.     {
  47.         set<int> s;
  48.         s.insert(8);
  49.         s.insert(6);
  50.         s.insert(11);
  51.         s.insert(5);
  52.         s.insert(6);
  53.         s.insert(7);
  54.         s.insert(10);
  55.         s.insert(13);
  56.         s.insert(12);
  57.         s.insert(15);
  58.  
  59.         set<int>::iterator it = s.begin();
  60.         while (it != s.end())
  61.         {
  62.             cout << *it << " ";
  63.             ++it;
  64.         }
  65.         cout << endl;
  66.  
  67.         for (auto e : s)
  68.         {
  69.             cout << e << " ";
  70.         }
  71.         cout << endl;
  72.     }
  73.  
  74.     }
  75. }
  76. #endif //RBTREE_SET_H

4.main.cpp

  1. #include <iostream>
  2. #include <assert.h>
  3. #include <utility>
  4. using namespace std;
  5. #include "RBTree.h"
  6. #include "Map.h"
  7. #include "Set.h"
  8. int main() {
  9. //    zhuyuan::test_map1();
  10. //    zhuyuan::test_map2();
  11. //    zhuyuan::test_map3();
  12.     return 0;
  13. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/246236
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号