【Cpp】第十六章-关联式容器

发表于 | 分类于
字数统计: 12.6k

关联式容器

  STL中关联式容器有以下几种map/set/multimap/multiset/unordered_map/unordered_set/unordered_multimap/unordered_multiset，所谓关联式容器即他们内部存储的是具有关联性的key-value形式的键值对。本文先从他们的基础使用开始讲起，逐渐深入到底层实现原理，并且最后从二叉搜索树到红黑树再到哈希桶逐步手动实现各个版本的关联式容器，我已经预感到了这将是一篇非常之长的博客，但是为了知识的连贯性我并不打算将他们分开。

pair

  关联式容器中诸如map都可以通过一个key来查找value，十分类似于查字典，这就得益于关联式容器中所存储的数据结构都是由一个一个键值对组成，因此我们对其的操作就更像是在查字典，要了解关联式容器我们就得先了解其内部存储的键值对的结构pair。
  我们首先看一下SGI版本中对键值对pair的定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;
    
    T1 first;
    T2 second;
    pair()
        :first(T1())
        ,second(T2()) 
    {}
    pair(const T1 &a, const T2 &b)
        :first(a)
        ,second(b) 
    {}
};

  pair的结构非常简单，简单来说其中就是存储了一个键值对，first对应key值，second对应value，同时提供了两个构造函数，仅此而已，不过不要忘记这个结构，在关联式容器的使用中，pair的使用也是必不可少。通常我们可以使用make_pair()函数快速帮助我们构造一个pair。

map

  map方便我们存储映射，并且会自动帮助我们根据key排序。

模板参数

1
2
3
4
5
6
template <class Key,                                  // key的类型
          class T,                                    // value的类型
          class Compare = less<Key>,                  // 比较器
          class Alloc = allocator<pair<const Key, T>> // 空间配置器
          >
class map;

  Key和T很好理解，那么这里的比较器和空间配置器是什么呢？Compare比较器是用来使用在容器内部辅助完成数据排序的，默认按照小于来比较，一般情况下不需要特殊比较方式的话不需要传入，我们也可以利用仿函数自定义比较方式。对于比较器我们之前在priority_queue中也有使用过。关于空间配置器我们会发现很多容器模板中都存在这个参数，容器通过使用空间配置器申请底层空间，我们会在之后的章节进行整理，一般情况下也不需要我们手动传入。

构造函数

1
2
3
4
5
6
7
8
9
explicit map(const key_compare &comp = key_compare(),
             const allocator_type &alloc = allocator_type());//创建一个空map

template <class InputIterator>
map(InputIterator first, InputIterator last,
    const key_compare &comp = key_compare(),
    const allocator_type &alloc = allocator_type());//用一个迭代器区间中的数据构造map
    
map (const map& x);//拷贝构造

迭代器相关

1
2
3
4
5
6
7
8
iterator begin();                      //返回第一个元素的位置
iterator end();                        //返回最后一个元素的下一个位置
const_iterator begin() const;          //返回第一个元素的const迭代器
const_iterator end() const;            //返回最后一个元素下一个位置的const迭代器
reverse_iterator rbegin();             //返回第一个元素位置的反向迭代器即rend
reverse_iterator rend();               //返回最后一个元素下一个位置的反向迭代器即 rbegin
const_reverse_iterator rbegin() const; //返回第一个元素位置的const反向迭代器即rend
const_reverse_iterator rend() const;   //返回最后一元素下一个位置的反向迭代器即rbegin

元素修改

1
2
3
4
5
6
7
8
9
10
11
12
pair<iterator, bool> insert(const value_type &x);        //在map中插入键值对x，注意x是一个键值对，返回 值也是键值对：iterator代表新插入元素的位置， bool代表释放插入成功
iterator insert(iterator position, const value_type &x); //在position位置插入值为x的键值对，返回该键值对 在map中的位置，注意：元素不一定必须插在 position位置，该位置只是一个参考
template <class InputIterator>
void insert(InputIterator first, InputIterator last); //在map中插入[first, last)区间中的元素
void erase(iterator position);                        //删除position位置上的元素
size_type erase(const key_type &x);                   //删除键值为x的元素
void erase(iterator first, iterator last);             //删除[first, last)区间中的元素
void swap(map<Key, T, Compare, Allocator> &mp);       //交换两个map中的元素
void clear();                                         //将map中的元素清空
iterator find(const key_type &x);                      //在map中插入key为x的元素，找到返回该元素的位 置的迭代器，否则返回end
const_iterator find(const key_type &x) const;          //在map中插入key为x的元素，找到返回该元素的位 置的const迭代器，否则返回cend
size_type count(const key_type &x) const;             //返回key为x的键值在map中的个数，注意map中 key是唯一的，因此该函数的返回值要么为0，要么 为1，因此也可以用该函数来检测一个key是否在 map中

  要注意map中一个key值仅存在一份，如果我们重复插入key相同的键值对，则会插入失败，并且insert的第一个重载要求插入的元素是一个pair并且返回的也是一个pair，返回的pair的类型为std::pair<std::map::iterator, bool>，第一个迭代器参数标识了结点插入的位置，如果已经存在该节点，则返回map中该节点的迭代器，如果不存在则插入新结点后返回新插入的结点的迭代器，bool标识了插入是否成功，也就是说无论如何当我们插入一个节点时返回的pair中都会给我们返回一个key对应的节点的迭代器。

容量及元素访问

1
2
3
bool empty() const;                         //检测map中的元素是否为空，是返回true，否则 返回false
size_type size() const;                     //返回map中有效元素的个数
mapped_type &operator[](const key_type &k); //返回去key对应的value

  这里要注意map也重载了operator[]，那么如果我们去访问一个不存在的值会怎样呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
#include <map>
int main()
{
    std::map<std::string, int> map;//空map
    //访问不存在的key值
    map["1"] = 1;
    map["2"] = 2;
    for(auto e : map)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
}


1 1
2 2

  我们会发现map自动在找不到这个节点的时候会自动插入新的节点，并且返回其value的应用，这里贴出其底层实现。

1
(*((this->insert(make_pair(k,mapped_type()))).first)).second

  对只有这么一句话，我们应该就已经明白了为什么它可以帮助我们插入新节点了，因为它在底层调用了insert方法，insert方法之前已经说过他的返回值是一个特定的pair，其中的key包含了对应结点的迭代器，因此我们也就可以方便的取到对应结点的value并将其返回出来。

总结

  1、map中的元素是键值对的形式存在的。
  2、map中key值是唯一的，并且不能修改key只。
  3、map底层是一个红黑树，因此查找效率较高OlogN。
  4、map会自动根据key进行排序，当然这也是因为底层是一个红黑树。
  5、默认按照小于的方式进行排序，排序结果升序。
  6、支持[]操作，在底层调用insert方法。

multimap

  map中的元素key值不允许相同，由此便延伸出了multimap，multimap中允许元素key值相同，其他与map并没有太大区别。因此接口不再介绍，不过唯一要注意的是insert相关的接口永远都会插入新的元素，并不会存在因为key值存在而插入失败的情况。

set

  set在上层使用时我们很容易将其看成是一个会自动排序和去重的vector但是实际上在底层实现大有不同，这也是它被称为关联式容器的原因。其底层依然存储着一个pair不过其中key值和value值都是相同的即<value, value>，并且和map一样它的key一样是不允许修改的，这也就导致了set中的元素是不可修改的，只允许插入和删除。set插入元素时也是只需提供value即可。

模板参数

1
2
3
4
5
template <class T,                   // value类型
          class Compare = less<T>,   // 比较器
          class Alloc = allocator<T> // 空间配置器
          >
class set;

构造函数

1
2
3
set(const Compare &comp = Compare(), const Allocator & = Allocator());                                         //构造空的set
set(InputIterator first, InputIterator last, const Compare &comp = Compare(), const Allocator & = Allocator()); //用[first, last)区间 中的元素构造set
set(const set<Key, Compare, Allocator> &x);

迭代器相关

1
2
3
4
5
6
7
8
iterator begin();                       //返回set中起始位置元素的迭代器
iterator end();                         //返回set中最后一个元素后面的迭代器
const_iterator cbegin() const;          //返回set中起始位置元素的const迭代器
const_iterator cend() const;            //返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin();              //返回set第一个元素的反向迭代器，即end
reverse_iterator rend();                //返回set最后一个元素下一个位置的反向迭代器，即 rbegin
const_reverse_iterator crbegin() const; //返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const;   //返回set最后一个元素下一个位置的反向const迭代器， 即crbegin

容量和修改

1
2
3
4
5
6
7
8
9
10
11
12
13
bool empty() const;                                      //检测set是否为空，空返回true，否则返回true
size_type size() const;                                  //返回set中有效元素的个数
pair<iterator, bool> insert(const value_type &x);        //在set中插入元素x，实际插入的是<x, x>构成的键值对， 如果插入成功，返回<该元素在set中的位置，true>,如果 插入失败，说明x在set中已经存在，返回<x在set中的位 置，false>
iterator insert(iterator position, const value_type &x); //在set的position位置插入x，实际插入的是<x, x>构成的 键值对，注意：position位置只是参考，x最终不一定在该 位置
template <class InputIterator>
void insert(InputIterator first, InputIterator last); //在set中插入[first, last)区间中的元素
void erase(iterator position);                       //删除set中position位置上的元素
size_type erase(const key_type &x);                  //删除set中值为x的元素，返回删除的元素的个数
void erase(iterator first, iterator last);            //删除set中[first, last)区间中的元素
void swap(set<Key, Compare, Allocator> &st);         //交换set中的元素
void clear();                                        //将set中的元素清空
iterator find(const key_type &x) const;               //返回set中值为x的元素的位置
size_type count(const key_type &x) const;            //返回set中值为x的元素的个数

  set的接口与map的接口几乎没有差别，不同的是set的迭代器取值直接*it即可，并没有map中first和second的取值方式了。取消了[]操作，因为set的key和value一致并且不允许修改于是这个接口也不再有存在的必要。

总结

  1、set和map几乎一致，不同是value和key值相同，因此不能修改。
  2、底层依然是一个红黑树进行实现，因此可以实现自动排序，查找速度也较快能够达到OlogN>
  3、set插入元素只需提供value即可。
  4、set中的元素不可重复，因此可以达到驱虫的效果。
  5、set中的元素默认按照小于的方式排序，结果升序。
  6、set中的依然存储键值对pair，知识key值与value值相同。

multiset

  multiset与set的区别与multimap与map的区别相同，set中不允许存储相同的元素而multiset中允许存储，仅此而已。

底层实现

  以上介绍的几种关联式容器底层都是一颗红黑树，什么是红黑树呢，这就得从BS树说起，于是接下来我们着重底层实现，从BS Tree开始逐步升级直到最终实现红黑树，并用其封装成map/set。

BS Tree

什么是BS Tree

  BS Tree即二叉搜索树，在一个二叉树的基础上使其满足某些要求，让其更加便于搜索。那么一棵二叉搜索树要满足哪些要求呢？
  1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 。
  2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
  3、它的左右子树也分别为二叉搜索树。
  中序遍历二叉搜索树结果即为有序序列。如下即为一颗二叉搜搜树。

BS Tree

  二叉搜索树的插入思路就是用一个cur结点和parent结点找到目标插入位置和其夫结点插入即可，位置的找法就是key值比cur的key大则往左子树走，小则往右子树走，相等则失败，查找也是相同的思路，而删除略微麻烦一些，要分为三种情况进行删除，有两个孩子的结点较难删除，需要找到合适的值进行替换再删除。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#pragma once
#include <iostream>
#include <utility>
template<class K, class V>
//结点
struct BSTreeNode
{
    BSTreeNode(const std::pair<K, V>& kv)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_kv(kv)
    {

    }
    std::pair<K, V> _kv;
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    //BSTree可以暂时先不使用_parent
    BSTreeNode<K, V>* _parent;
};
//二叉搜索树
template<class K, class V>
class BSTree
{
    typedef BSTreeNode<K, V> Node;
public:
    //这里先暂时忽略拷贝构造，析构，赋值的问题
    BSTree()
        :_root(nullptr)
    {
    }
    //插入结点
    bool Insert(const std::pair<K, V>& kv)
    {
        //插入第一个结点
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while(cur)
        {
            //比当前结点小，插在左边
            if(cur->_kv.first > kv.first)
            {
                //记录上一个结点
                parent = cur;
                cur = cur->_left;
            }
            //比当前结点大，插在右边
            else if(cur->_kv.first < kv.first)
            {
                //记录上一个结点
                parent = cur;
                cur = cur->_right;
            }
            //相等则说明已存在，插入失败
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if(parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        return true;
    }
    //查找，返回结点的指针
    Node* Find(const K& key)
    {
        Node* cur = _root;
        while(cur)
        {
            if(cur->_kv.first < key)
            {
                cur = cur->_right;
            }
            else if(cur->_kv.first > key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }
    //删除结点
    bool Remove(const K& key)
    {
        //1、叶子结点，直接删除，父结点对应指针指向空
        //2、有一个孩子，如果左为空，父结点对应指针指向右，如果右为空，父结点对应指针指向左
        //3、找右子树最左结点或左子树最右结点替代他，然后删除替代结点
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_kv.first < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            //找到相等可以删除此结点了
            else
            {
                //只有0/1个孩子
                //对于只有一个孩子或者没有孩子的结点来说要删除的结点就是cur
                Node* del = cur;
                //要删除的结点左孩子为空
                if(cur->_left == nullptr)
                {
                    
                    //如果要删除的是根结点，父结点为空
                    if(parent == nullptr)
                    {
                        //直接改变根
                        _root = cur->_right;
                        return true;
                    }
                    //判断要删除的结点是其父结点的左孩子还是右孩子
                    if(cur == parent->_left)
                    {
                        parent->_left = cur->_right;
                    }
                    else
                    {
                        parent->_right = cur->_right;
                    }
                }
                //要删除的结点右孩子为空
                else if(cur->_right == nullptr)
                {
                    //如果要删除的是根结点，父结点为空
                    if(parent == nullptr)
                    {
                        _root = cur->_left;
                        return true;
                    }
                    //判断要删除的结点是其父结点的左孩子还是右孩子
                    if(cur == parent->_left)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }
                }
                //有两个孩子，找右树的最左结点
                else
                {
                    //找到右树的最左结点和其父结点
                    Node* rpParent = cur;
                    Node* replace = cur->_right;
                    while(replace->_left)
                    {
                        rpParent = replace;
                        replace = replace->_left;
                    }
                    //此时要释放的结点是替代结点
                    del = replace;
                    //找到后开始替换
                    cur->_kv = replace->_kv;
                    //替换结点不一定一定是其父结点的左结点，因此做一次判断
                    if(rpParent->_left == replace)
                    {
                        rpParent->_left = replace->_right;
                    }
                    else
                    {
                        rpParent->_right = replace->_right;
                    }
                    
                }
                //释放结点
                delete del;
                std::cout << "del success" << std::endl;
                return true;
            }
        }
        return false;
    }
    //中序遍历
    void InOrder()
    {
        _InOrder(_root);
        std::cout << std::endl;
    }
private:
    void _InOrder(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        std::cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }
private:
    Node* _root;

};

  二叉搜索树的搜索速度在理想状况下可以达到OlogN，此时二叉树为一棵完全二叉树，如果是一颗满二叉树更好，因为每次搜索都可以淘汰一半的数据。但是往往并不是理想的，如果插入的树本身就是有序的，则使二叉树可能会变成一条链，二叉树会完全失去平衡，此时的搜索便是ON的。为了让二叉树尽可能保持平衡，使其尽可能成为一颗完全二叉树，所有状况下都能达到理想状态，优化时间复杂度，于是我们需要在改变树的状态的时候维持它自身的平衡，便出现了AVLTree。

AVLTree

什么是AVLTree

  AVLTree也叫高度平衡二叉搜索树，其是对BSTree的一个改进，为了保证其在高度上的平衡性，使其可以尽可能的达到理想状态中的完全二叉树的形式，AVLTree引入了平衡因子的概念，平衡因子即左右子树的高度差。AVLTree要求树上每一个结点的平衡因子都不能大于1，其它要求与BSTree一致。
  这样一来AVLTree上任何状态下的操作都将与理想状态下BSTree的操作有着同样的时间复杂度OlogN，可以说AVLTree的存在就是为了任何时候都可以将BSTree限定在理想状态。

AVLTree平衡因子的更新

  我们这里都先假设平衡因子bf = 右子树高度 - 左子树高度。AVLTree引入平衡因子概念后我们在插入一个节点后必须要更新整棵树的平衡因子，那么我们该如何更新才能让整棵树的平衡因子能重新回到正确的状态下呢？
  以下是一棵AVLTree，我用蓝色标识了每个结点的bf。

AVLTree

  接下来我们假设插入7.5，或者任意一个比7大比8小的值，我们可以发现新插入的结点bf == 0，因为其没有左右孩子，所以并不受影响。新结点的插入只会影响它的祖先们，因此我们必须依次去更新他们的祖先。这里我们首当其冲更新了插入结点的父亲。更新其父亲的bf规律很好总结，如果我们插入在父亲的左则bf = bf - 1，插入在父亲的右则bf = bf + 1。此时其父亲bf == 0。

AVLTree

  在一次更新后我们是否还应该继续更新？当然，我们必须迭代上去继续更新，让cur = parent, parent = parent->parent。但是我们再次按照刚才的规律更新会发现7这个元素结点的平衡因子会被更新为2，但是这样的更新明显是错误的，因为虽然插入的新节点但7的右子树高度并没有增高，我们并不应该更新它，那么我们的更新该到何时为止呢？

AVLTree

  经过实验我们可以总结出以下几种parent更新bf后的情况，由此来判断是否需要进一步更新或者执行其他操作：
  1、|bf| == 0则说明此时当前父结点所在的子树高度并没有增加，我们自然也不需要再迭代上去继续更新其他祖先。
  2、parent == nullptr，此时父结点已经指向空说明我们已经更新完了插入结点的所有祖先，没有祖先可以继续更新，这是更新的最坏情况。
  3、|bf| == 1，此时当前父结点所在子树的高度增加了，但是父结点bf依然符合AVLTree的要求，我们需要继续向上迭代更新其祖先。
  4、|bf| == 2，此时当前父结点所在子树的高度增加了，并且父结点bf不再符合AVLTree的要求，我们就此停止不再更新，并且利用旋转来解决眼下的问题。

AVLTree的旋转

  我们在更新平衡因子的过程中难免会遇到bf == 2的情况，此时这棵树不再满足AVLTree的要求，当然我们也有方法可以使其继续成为一棵AVLTree，就是旋转。
  旋转分为一共四种情况，以下一一列举。

左单旋

  使用场景：

AVLTree

AVLTree

  由此我们可以归纳出这种情况的抽象图来。
AVLTree

右单旋

  右单旋与左单旋类似：

AVLTree

  抽象图。
AVLTree

先右旋再左旋

  使用场景：

AVLTree

  抽象图：

AVLTree

  但是这里要注意，两次旋转后结点的平衡因子更新并不像单旋呢么简单，需要根据实际情况进行判断，具体请看代码中的实现。

先左旋再右旋

  与先右旋再左旋类似，直接给出抽象图：

AVLTree

  但是这里要注意，两次旋转后结点的平衡因子更新并不像单旋呢么简单，需要根据实际情况进行判断，具体请看代码中的实现。

旋转场景

  四种旋转搞明白后，AVLTree的调整就只剩最后一件事要考虑，那就是我们什么情况下应该使用哪种旋转来调整呢？
  回到我们用cur和parent来更新插入结点祖先的平衡因子。以下我们分为四种情况：
  1、parent->_bf == 2 && cur->_bf == 1说明parent右子树高，并且cur的右子树也高，说明此时结点插入在了parent右子树的外侧，我们左单旋即可。
  2、parent->bf == 2 && cur->bf == -1说明parent右子树高，但是cur左子树高，说明此时结点插入在了parent右子树的内侧，我们要先右旋再左旋。
  3、parent->bf == -2 && cur->bf == -1说明此时parent左子树高，cur也是左子树高，则结点插入在了parent左子树的外侧，右单旋即可。
  4、parent->bf == -2 && cur->bf == 1说明此时parent左子树高，但是cur右子树高，说明此时结点插入在了parent左子树的内侧，我们要先左旋再右旋。

实现

  这里仅仅实现了AVLTree的插入，删除与插入类似，需要用到BSTree的删除思想并且和AVLTree的插入中的调整平衡的思想相结合来实现。
  直接上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
#pragma once
#include <iostream>
#include <utility>
#include <assert.h>
//结点
template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode(const std::pair<K, V>& kv)
        :_kv(kv)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_bf(0)
    {}
    std::pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf; //平衡因子 = 右子树高度 - 左子树高度
};
template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const std::pair<K, V>& kv)
    {
        //插入结点，思路与BSTree一致，额外需要加入更新平衡因子
        //插入的为第一个结点
        if(_root == nullptr)
        {
            _root = new Node(kv);
            _root->_bf = 0;
            return true;
        }
        Node* cur = _root;
        Node* parent = nullptr;
        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);
        if(parent->_kv.first < kv.first)
        {
            cur->_parent = parent;
            parent->_right = cur;
        }
        else
        {
            cur->_parent = parent;
            parent->_left = cur;
        }
        //调整平衡
        //1、更新平衡因子
        //新增在左，父亲bf - 1，新增在右，父亲bf + 1
        //如果父亲的更新后|bf|:
        //|bf| == 0 || 父结点为空时停止更新
        //因为bf更新为0则说明当前父亲所在子树此时的高度并未发生变化，父结点为空说明此时更新完了整棵树
        //|bf| == 2也停止更新，及时调整，旋转处理
        //|bf| == 1则继续向上更新
        while(parent)
        {
            if(cur == parent->_right)
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
            //|bf| == 0
            if(parent->_bf == 0)//更新完成
            {
                break;
            }
            else if(abs(parent->_bf) == 1)//继续向上更新
            {
                cur = parent;
                parent = parent->_parent;
            }
            else if(abs(parent->_bf) == 2)//不满足AVLTree要求及时旋转调整
            {
                //2、旋转
                if(parent->_bf == 2)
                {
                    if(cur->_bf == 1)
                    {
                        RotateL(parent);
                    }
                    else if(cur->_bf == -1)
                    {
                        RotateRL(parent);
                    }
                }
                else if(parent->_bf == -2)
                {
                    if(cur->_bf == -1)
                    {
                        RotateR(parent);
                    }
                    else if(cur->_bf == 1)
                    {
                        RotateLR(parent);
                    }
                }
                break;//调整完一定要记着break
            }
            else//在三种情况外，说明出现问题
            {
                assert(false);
            }
        }
        return true;
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        //根
        if(ppNode == nullptr)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subR;
            }
            else
            {
                ppNode->_left = subR;
            }
            subR->_parent = ppNode;
        }
        //更新平衡因子
        subR->_bf = parent->_bf = 0;
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;

        parent->_left = subLR;
        if(subLR)//subLR可能会为空，当h == 0时subLR为空
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;//subL不可能为空
        //记录下parent原来的父结点，为了方便parent移动可以找到这棵子树的父结点
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        //更新这棵子树的新父结点subL与其父结点的连接
        if(ppNode == nullptr)//如果子树的父结点为空则说明parent原本是整棵树的根节点
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subL;
            }
            else
            {
                ppNode->_left = subL;
            }
            subL->_parent = ppNode;
        }
        parent->_bf = subL->_bf = 0;
    }
    //先左旋再右旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        //保存subRL的平衡因子，之后要根据这个判断parent和subR的平衡因子分别更新为多少
        int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);
        //注意这里双旋过后父结点的平衡因子不一定会为0
        if(bf == 0)
        {
            parent->_bf = subLR->_bf = subL->_bf = 0;
        }
        else if(bf == 1)
        {
            subL->_bf = -1;
            parent->_bf = 0;
            subLR->_bf = 0;
        }
        else if(bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }

    }
    //先右旋再左旋
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        //保存subRL的平衡因子，之后要根据这个判断parent和subR的平衡因子分别更新为多少
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        //注意这里双旋过后父结点的平衡因子不一定会为0
        //这里三个结点的平衡因子更新要根据新节点到底插在哪里来决定
        if(bf == 0)//此时说明subRL为新增结点
        {
            parent->_bf = subRL->_bf = subR->_bf = 0;
        }
        else if(bf == 1)//此时说明新增节点插在c树上
        {
            subR->_bf = 0;
            parent->_bf = -1;
            subRL->_bf = 0;
        }
        else if(bf == -1)//此时说明新增结点插在b树上
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
    }
    //中序
    void InOrder()
    {
        _InOrder(_root);
        std::cout << std::endl;
    }
    //为了判定它是一棵平衡树我们写一个求树高度的函数
    int _Height(Node* root)
    {
        if(root == nullptr)
        {
            return 0;
        }
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }
    //判断这是否是一颗平衡二叉树
    bool IsBalance()
    {
        return _IsBalance(_root);
    }
    bool _IsBalance(Node* root)
    {
        if(root == nullptr)
        {
            return true;
        }
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        //也有可能会出现平衡因子更新错误的情况，这里再做二次判断
        if(rightHeight - leftHeight != root->_bf)
        {
            std::cout << root->_kv.first << " is error" << std::endl;
        }
        return (abs(leftHeight - rightHeight) < 2) && _IsBalance(root->_left) && _IsBalance(root->_right);
    }
private:
    void _InOrder(Node* parent)
    {
        if(parent == nullptr)
        {
            return;
        }
        _InOrder(parent->_left);
        std::cout << parent->_kv.first << " ";
        _InOrder(parent->_right);
    }
    Node* _root = nullptr;
};
void TestAVLTree()
{
    AVLTree<int, int> t;
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    int b[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for(auto e : b)
    {
        t.Insert(std::make_pair(e, e));
    }
    t.InOrder();
    //验证是否平衡
    std::cout << t.IsBalance() << std::endl;
}


在主函数中调用TestAVLTree()
1 2 3 4 5 6 7 14 15 16
1

  因为AVLTree总能通过旋转来调节自身的平衡，使自己变成一棵近完全二叉树以追求搜索二叉树的理想状态，因此它在搜索上的时间复杂度确实得到了极大的改进，可以一直维持在OlogN，但是这棵树它虽然近乎完美但是依然达不到要求，首先的原因就是它的调整，可以说调整虽然加快了它的搜索过程，但是也正是调整使它变得更为复杂。我们在根部插入新结点时，最坏情况下我们要从叶子调整到根，它的调整实在是太多了。其次，它的实现也因为调整变得十分复杂繁琐，虽然我们希望一棵BSTree搜索起来尽可能追求理想状态，但是这样的调整未免付出的代价也有点过大了。于是便有了接下来的RBTree的诞生。

RBTree

什么是RBTRee

  RBTree即红黑树，它相比AVLTree更为简单，并且它大大减少了要调整的次数，在追求理想状态的过程中与调整次数达成了妥协，这也使得它成为STL中map/set/multimap/multiset的底层数据结构。
  一棵树要是红黑树必须满足以下几条规则：
  1、每个结点不是红色就是黑色的。
  2、根节点是黑色的。
  3、如果一个结点时红色的，则它两个孩子结点是黑色的。
  4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑结点。
  5、每个叶子结点都是黑色的（此处的叶子结点指空结点）。

RBTree的调整

  我们在插入新节点的时候要考虑的就是新节点的颜色默认应该为什么颜色。我们首先分析如果新节点颜色如果为黑色，那么就意味着当前叶子的祖先路径上黑色必然会多出来一个，为了维持第4条规则，必然要对树进行调整，这就意味着如果新插入结点默认为黑色那么我们必然要进行调整，因为黑色结点对整棵树整体的影响是比较大的。那么如果新插入结点默认为红色呢？如果为红色只要它的父结点不为红色，那么此时我们是不需要进行调整的，因此调整的几率从必然要调整降低到了有可能不会需要调整，因此我们默认新插入的结点颜色为红色是最优的选择。
  新插入结点默认为红色也有可能会遇到需要调整的情况，比如它的父结点也为红色那么此时该如何调整呢？这里的情况判断相比AVLTree更为复杂一些。
  为了方便讨论，这里约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

情况一

  cur为红，p为红，g为黑，u存在且为红。

AVLTree

  这种情况下肯定是要调整了，这种情况下要做的操作也很简单，变色即可。为了让红色不连续我们将p变为黑色，为了维持每条路径上黑色结点数量一致，我们将u也变为黑色，而g变为红色。如果g调整后和它的父结点再次出现了连续红色则再次根据情况进行调整。

情况二

  cur为红，p为红，g为黑，u不存在或为黑。

AVLTree

  这种情况下调整方式为：如果p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转。最后p变黑，g变红。这里的旋转方法和AVLTree的相同。

情况三

  cur为红，p为红，g为黑，u不存在或u为黑
。
AVLTree

  p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 则转换成了情况2 。
  这种情况与AVLTree中的双旋场景类似，cur在了内侧，因此我们必须旋转两次，好在这里旋转一次就可以变为情况二我们可以很方便的处理这种问题。要注意的是，旋转一次完毕后我们要交换cur和parent来让当前结点的情况和情况二完全一致。

实现

  直接上代码，这里暂且没有实现删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
#pragma once
#include <iostream>
#include <utility>
enum Color
{
    RED,
    BLACK
};
template<class K, class V>
struct RBTNode
{
    RBTNode(const std::pair<K, V>& data = std::pair<K, V>())
        :_data(data)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_color(RED)
    {
    }
    std::pair<K, V> _data;
    RBTNode<K, V>* _left;
    RBTNode<K, V>* _right;
    RBTNode<K, V>* _parent;
    Color _color;
};

template<class K, class V>
class RBTree
{
    typedef RBTNode<K, V> Node;
public:
    RBTree(const std::pair<K, V>& data = std::pair<K, V>())
        :_header(new Node(data))
    {
        _header->_left = _header;
        _header->_right = _header;
        _header->_parent = nullptr;
    }
    bool Insert(const std::pair<K, V>& data)
    {
        //空树，插入的为根结点
        if(_header->_parent == nullptr)
        {
            Node* root = new Node(data);
            //根节点颜色必须为黑色
            root->_color = BLACK;
            _header->_parent = root;
            root->_parent = _header;
            _header->_left = root;
            _header->_right = root;
            return true;
        }
        Node* cur = _header->_parent;
        Node* parent = _header;
        while(cur)
        {
            if(cur->_data.first < data.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_data.first > data.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(data);
        if(parent->_data.first < data.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        //_header->_left = cur;
        //调整：修改颜色，旋转
        while(cur != _header->_parent && cur->_parent->_color == RED)
        {
            Node* parent = cur->_parent;
            Node* gParent = parent->_parent;
            if(gParent->_left == parent)
            {
                Node *uncle = gParent->_right;
                //情况一
                if(uncle && uncle->_color == RED)
                {
                    //更新颜色
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    //向上继续更新
                    cur = gParent;
                }
                //情况二/三
                else
                {
                    //叔叔不存在或者叔叔为黑色
                    //判断这里是否存在双旋的场景
                    if(cur = parent->_right)
                    {
                        //情况三
                        //此时就是一个折现的形态就需要两次旋转了
                        RotateL(parent);
                        //左旋后，父亲变子，子变父亲，重回情况er
                        std::swap(cur, parent);
                    }
                    else
                    {
                        //情况二
                        RotateR(gParent);
                        //更改颜色
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        //此时这课子树的根为黑色，所以不需要再继续向上调整
                        break;
                    }
                }
            }
            else
            {
                Node* uncle = gParent->_left;
                if(uncle && uncle->_color == RED)
                {
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    cur = gParent;
                }
                else
                {
                    if(cur == parent->_left)
                    {
                        RotateR(parent);
                        std::swap(cur, parent);
                    }
                    else
                    {
                        RotateL(gParent);
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        break;
                    }
                }
            }
        }
        //根结点的颜色必须为黑色
        _header->_parent->_color = BLACK;
        //更新头节点
        _header->_left = LeftMost();
        _header->_right = RightMost();
        return true;
    }
    //左旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        //根
        if(ppNode == _header)
        {
            _header->_parent = subR;
            subR->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subR;
            }
            else
            {
                ppNode->_left = subR;
            }
            subR->_parent = ppNode;
        }
    }
    //右旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;

        parent->_left = subLR;
        if(subLR)//subLR可能会为空，当h == 0时subLR为空
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;//subL不可能为空
        //记录下parent原来的父结点，为了方便parent移动可以找到这棵子树的父结点
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        //更新这棵子树的新父结点subL与其父结点的连接
        if(ppNode == _header)//如果子树的父结点为空则说明parent原本是整棵树的根节点
        {
            _header->_parent= subL;
            subL->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subL;
            }
            else
            {
                ppNode->_left = subL;
            }
            subL->_parent = ppNode;
        }
    }
    //找到当前树的最左结点
    Node* LeftMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }
    //找到当前树的最有结点
    Node* RightMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_right)
        {
            cur = cur->_right;
        }
        return cur;
    }
    //中序遍历
    void Inorder()
    {
        _Inorder(_header->_parent);
    }
    void _Inorder(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _Inorder(root->_left);
        std::cout << root->_data.first << " ";
        _Inorder(root->_right);
    }
    //判断是否是一个红黑树
    bool IsRBTree()
    {
        Node* root = _header->_parent;
        if(root == nullptr)
        {
            return true;
        }
        if(root->_color == RED)
        {
            return false;
        }
        //统计一条路径黑结点的数量
        int blackCount = 0;
        Node* cur = root;
        while(cur)
        {
            if(cur->_color == BLACK)
            {
                blackCount++;
            }
            cur = cur->_left;
        }
        //前序遍历
        return _IsRBTree(root, blackCount, 0);
    }
    bool _IsRBTree(Node* root, int blackCount, int curBlackCount)
    {
        if(root == nullptr)
        {
            if(curBlackCount != blackCount)
            {
                return false;
            }
            return true;
        }
        //统计黑色结点的数量
        if(root->_color == BLACK)
        {
            curBlackCount++;
        }
        //判断是否有红色连续
        if(root->_parent->_color == RED && root->_color == RED)
        {
            return false;
        }
        return _IsRBTree(root->_left, blackCount, curBlackCount) 
        && _IsRBTree(root->_right, blackCount, curBlackCount);
    }
private:
    //Node* _root;
    //这里为了方便后续封装成map/set我们将其结构改造成一棵带头结点的环形树
    //这里的头和环形类似于实现过的带头双向环形链表
    //头节点的右孩子连接最右结点，左孩子连接最左结点，用头指向树真正的根结点
    //相当于这个头结点是倒过来的，和真正的根结点头连着头，连个孩子和最左最右结点构成两个环
    //封装成这种结构都是为了方便我们后续进一步封装，尽量和库中的保持一致
    Node* _header;
};
void TestRBTree()
{
    RBTree<int, int> rbt;
    rbt.Insert(std::make_pair(1, 1));
    rbt.Insert(std::make_pair(10, 1));
    rbt.Insert(std::make_pair(2, 1));
    rbt.Insert(std::make_pair(5, 1));
    rbt.Insert(std::make_pair(3, 1));
    rbt.Insert(std::make_pair(4, 1));
    rbt.Insert(std::make_pair(7, 1));
    rbt.Inorder();
    std::cout << std::endl;
    //验证
    std::cout << (rbt.IsRBTree()) << std::endl;
}

执行TestRBTree:
1 2 3 4 5 7 10 
1

  RBTree相比AVLTree性能更好，降低了需要旋转的次数，并且RBTree实现起来相比AVLTree较简单。

封装

  STL库中的map/set的底层数据结构就是一棵红黑树，到了这一步我们从最基本的BSTree一路过关斩将最终实现了RBTree的基本功能，接下来我们要做的就是对RBTree进一步封装，使其完成map/set的基本功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
RBTreeMod.hpp:
#pragma once
#include <iostream>
#include <utility>
//为了方便封装进行的修改版本的红黑树
enum Color
{
    RED,
    BLACK
};
template<class V>
struct RBTNode
{
    RBTNode(const V& data = V())
        :_data(data)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_color(RED)
    {
    }
    V _data;
    RBTNode<V>* _left;
    RBTNode<V>* _right;
    RBTNode<V>* _parent;
    Color _color;
};

//每个容器都有自己的迭代器，我们的Map/Set也必须有！
//在这里封装实现迭代器，Map/Set结构都是一致的，所以是现在RBTree的头文件中
template<class V>
class _RBTreeIterator
{
    //封装红黑树的结点
    typedef RBTNode<V> Node;
    typedef _RBTreeIterator<V> Self;
public:
    _RBTreeIterator(Node* node)
        :_node(node)
    {
    }
    V& operator*()
    {
        return _node->_data;
    }
    V* operator->()
    {
        return &_node->_data;
    }
    bool operator!=(const Self& it)
    {
        return _node != it._node;
    }
    bool operator==(const Self& it)
    {
        return _node == it._node;
    }
    //我们之前更改红黑树的结构使其变成带头的就是为这里迭代器的遍历做铺垫
    //1、_node->_right存在，走到右子树的最左结点
    //2、_node->_right不存在，向上回溯，只要_node == parent->_right就继续向上回溯，不满足条件则停止回溯，更新_node的值为parent
    Self& operator++()
    {
        if(_node->_right)
        {
            //找到右子树最左结点
            _node = _node->_right;
            while(_node->_left)
            {
                _node = _node->_left;
            }
        }
        else
        {
            Node* parent = _node->_parent;
            while(_node == parent->_right)
            {
                _node = parent;
                parent = parent->_parent;
            }
            //这个判断是为了避免树中没有右子树导致死循环的情况
            if(_node->_right != parent)
            {
                _node = parent;
            }
        }
        return *this;
    }
    //1、_node->_left存在，找左子树的最有结点
    //2、_node->_left不存在，只要_node != parent->_right，向上回溯，条件不满足则更新_node为parent
    Self& operator--()
    {
        if(_node->_left)
        {
            _node = _node->_left;
            while(_node->_right)
            {
                _node = _node->_right;
            }
        }
        else
        {
            Node* parent = _node->_parent;
            while(_node != parent->_right)
            {
                _node = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
private:
    Node* _node;
};
//此时的结构仿照STL中的内容，K依然代表Key，而V代表节点中data的类型
//如果是map则V->std::pair<K, V>，如果是set则V->K
//这样实现的原因是为了方便红黑树更为灵活的可以分别实现map和set
template<class K, class V, class KeyOfValue>
class RBTree
{
    typedef RBTNode<V> Node;
public:
    typedef _RBTreeIterator<V> iterator;
    //中序遍历的头即树中的最左结点
    iterator begin()
    {
        return iterator(_header->_left);
    }
    //尾注意是它本身
    iterator end()
    {
        return iterator(_header);
    }
    RBTree(const V& data = V())
        :_header(new Node(data))
    {
        _header->_left = _header;
        _header->_right = _header;
        _header->_parent = nullptr;
    }
    std::pair<iterator, bool> Insert(const V& data)
    {
        //空树，插入的为根结点
        if(_header->_parent == nullptr)
        {
            Node* root = new Node(data);
            //根节点颜色必须为黑色
            root->_color = BLACK;
            _header->_parent = root;
            root->_parent = _header;
            _header->_left = root;
            _header->_right = root;
            return std::make_pair(iterator(root), true);
        }
        Node* cur = _header->_parent;
        Node* parent = _header;
        KeyOfValue kov;
        while(cur)
        {
            //修改
            if(kov(cur->_data) < kov(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kov(cur->_data) > kov(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                //return false;
                return std::make_pair(iterator(cur), false);
            }
        }
        cur = new Node(data);
        if(kov(parent->_data) < kov(data))
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        Node* newNode = cur;
        //_header->_left = cur;
        //调整：修改颜色，旋转
        while(cur != _header->_parent && cur->_parent->_color == RED)
        {
            Node* parent = cur->_parent;
            Node* gParent = parent->_parent;
            if(gParent->_left == parent)
            {
                Node *uncle = gParent->_right;
                //情况一
                if(uncle && uncle->_color == RED)
                {
                    //更新颜色
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    //向上继续更新
                    cur = gParent;
                }
                //情况二/三
                else
                {
                    //叔叔不存在或者叔叔为黑色
                    //判断这里是否存在双旋的场景
                    if(cur = parent->_right)
                    {
                        //情况三
                        //此时就是一个折现的形态就需要两次旋转了
                        RotateL(parent);
                        //左旋后，父亲变子，子变父亲，重回情况er
                        std::swap(cur, parent);
                    }
                    else
                    {
                        //情况二
                        RotateR(gParent);
                        //更改颜色
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        //此时这课子树的根为黑色，所以不需要再继续向上调整
                        break;
                    }
                }
            }
            else
            {
                Node* uncle = gParent->_left;
                if(uncle && uncle->_color == RED)
                {
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    cur = gParent;
                }
                else
                {
                    if(cur == parent->_left)
                    {
                        RotateR(parent);
                        std::swap(cur, parent);
                    }
                    else
                    {
                        RotateL(gParent);
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        break;
                    }
                }
            }
        }
        //根结点的颜色必须为黑色
        _header->_parent->_color = BLACK;
        //更新头节点
        _header->_left = LeftMost();
        _header->_right = RightMost();
        //return true;
        return std::make_pair(iterator(newNode), true);
    }
    //左旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        //根
        if(ppNode == _header)
        {
            _header->_parent = subR;
            subR->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subR;
            }
            else
            {
                ppNode->_left = subR;
            }
            subR->_parent = ppNode;
        }
    }
    //右旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;

        parent->_left = subLR;
        if(subLR)//subLR可能会为空，当h == 0时subLR为空
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;//subL不可能为空
        //记录下parent原来的父结点，为了方便parent移动可以找到这棵子树的父结点
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        //更新这棵子树的新父结点subL与其父结点的连接
        if(ppNode == _header)//如果子树的父结点为空则说明parent原本是整棵树的根节点
        {
            _header->_parent= subL;
            subL->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subL;
            }
            else
            {
                ppNode->_left = subL;
            }
            subL->_parent = ppNode;
        }
    }
    //找到当前树的最左结点
    Node* LeftMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }
    //找到当前树的最有结点
    Node* RightMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_right)
        {
            cur = cur->_right;
        }
        return cur;
    }
    //中序遍历
    void Inorder()
    {
        _Inorder(_header->_parent);
    }
    void _Inorder(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _Inorder(root->_left);
        std::cout << root->_data.first << " ";
        _Inorder(root->_right);
    }
    //判断是否是一个红黑树
    bool IsRBTree()
    {
        Node* root = _header->_parent;
        if(root == nullptr)
        {
            return true;
        }
        if(root->_color == RED)
        {
            return false;
        }
        //统计一条路径黑结点的数量
        int blackCount = 0;
        Node* cur = root;
        while(cur)
        {
            if(cur->_color == BLACK)
            {
                blackCount++;
            }
            cur = cur->_left;
        }
        //前序遍历
        return _IsRBTree(root, blackCount, 0);
    }
    bool _IsRBTree(Node* root, int blackCount, int curBlackCount)
    {
        if(root == nullptr)
        {
            if(curBlackCount != blackCount)
            {
                return false;
            }
            return true;
        }
        //统计黑色结点的数量
        if(root->_color == BLACK)
        {
            curBlackCount++;
        }
        //判断是否有红色连续
        if(root->_parent->_color == RED && root->_color == RED)
        {
            return false;
        }
        return _IsRBTree(root->_left, blackCount, curBlackCount) 
        && _IsRBTree(root->_right, blackCount, curBlackCount);
    }
private:
    //Node* _root;
    //这里为了方便后续封装成map/set我们将其结构改造成一棵带头结点的环形树
    //这里的头和环形类似于实现过的带头双向环形链表
    //头节点的右孩子连接最右结点，左孩子连接最左结点，用头指向树真正的根结点
    //相当于这个头结点是倒过来的，和真正的根结点头连着头，连个孩子和最左最右结点构成两个环
    //封装成这种结构都是为了方便我们后续进一步封装，尽量和库中的保持一致
    Node* _header;
};
//void TestRBTree()
//{
//    RBTree<int, int> rbt;
//    rbt.Insert(std::make_pair(1, 1));
//    rbt.Insert(std::make_pair(10, 1));
//    rbt.Insert(std::make_pair(2, 1));
//    rbt.Insert(std::make_pair(5, 1));
//    rbt.Insert(std::make_pair(3, 1));
//    rbt.Insert(std::make_pair(4, 1));
//    rbt.Insert(std::make_pair(7, 1));
//    rbt.Inorder();
//    std::cout << std::endl;
//    //验证
//    std::cout << (rbt.IsRBTree()) << std::endl;
//}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Map.hpp:
#include "RBTreeMod.hpp"
template<class K, class V>
class Map
{
    //为了让红黑树可以根据调用它的不同类型得以确定比较条件
    //我们这里用内部类创建一个反函数用域返回当前结构下的Key值
    struct MapKeyOfValue
    {
        const K& operator()(const std::pair<K, V>& data)
        {
            return data.first;
        }
    };
public:
    //这里为了能够动态识别这是一个类型要在前面加上typename关键字
    typedef typename RBTree<K, std::pair<K, V>, MapKeyOfValue>::iterator iterator;
    std::pair<iterator, bool> Insert(const std::pair<K, V>& data)
    {
       return  _rbt.Insert(data);
    }

    //实现迭代器
    iterator begin()
    {
        return _rbt.begin();
    }

    iterator end()
    {
        return _rbt.end();
    }
    
    V& operator[](const K& key)
    {
        std::pair<iterator, bool> ret = _rbt.Insert(std::make_pair(key, V()));
        return ret.first->second;
    }
private:
    RBTree<K, std::pair<K, V>, MapKeyOfValue> _rbt;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Set.hpp:
#include "RBTreeMod.hpp"
template<class K>
class Set
{
    struct SetKeyOfValue
    {
        const K& operator()(const K& data)
        {
            return data;
        }
    };
public:
    typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;
    std::pair<iterator, bool> Insert(const K& data)
    {
        return _rbt.Insert(data);
    }

    //实现迭代器
    iterator begin()
    {
        return _rbt.begin();
    }

    //实现迭代器
    iterator end()
    {
        return _rbt.end();
    }
    

private:
    RBTree<K, K, SetKeyOfValue> _rbt;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
test.cpp:
#include "Map.hpp"
#include "Set.hpp"
void TestMapSet()
{
    Map<int, int> M;
    M.Insert(std::make_pair(10, 1));
    M.Insert(std::make_pair(3, 1));
    M.Insert(std::make_pair(9, 1));
    M.Insert(std::make_pair(2, 1));
    M.Insert(std::make_pair(1, 1));
    for(auto e : M)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    M[1] = 100;
    M[500] = 50;
    std::cout << std::endl;
    for(auto e : M)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    Set<int> S;
    S.Insert(1);
    S.Insert(3);
    S.Insert(5);
    S.Insert(6);
    S.Insert(2);
    S.Insert(6);
    std::cout << std::endl;
    for(auto e : S)
    {
        std::cout << e << " ";
    }
}
int main()
{
    //TestBsTree1();
    //TestAVLTree()m
    //TestRBTree();
    TestMapSet();
}


1 1 
2 1 
3 1
9 1
10 1

1 100
2 1
3 1
9 1
10 1
500 50

1 2 3 5 6

  map/set这种链式容器，也存在迭代器失效问题，但其的插入不会造成迭代器失效，删除会造成删除结点的迭代器失效。
  由此一来，我们就完全实现了map/set两个容器，我们一路从BSTree到最终的RBTree，中间充满了坎坷和艰辛，不过这一趟学习下来，我们对map/set及其multi版本的底层实现有了进一步的理解，我们今后对其的使用也会变得更加得心应手。
  但是至此我们的关联式容器部分还并没有完全结束，我们接下来会讨论unordered版本的关联式容器，他们的底层与普通版本的底层数据结构大相径庭，用到了哈希有关知识。

-------------本文结束感谢您的阅读!-------------
记录学习每一分，感谢您的赞助