C++ pair+map+set+multimap+multiset+AVL树+红黑树（深度剖析）

---

1. 前言

在学习二叉搜索树的过程中，我们发现当二叉搜索树为单支树时，其搜索的效率是很低的。为了能让二叉搜索树的搜索效率稳定在$lo{g}_{2}N$，我们引入两种新的二叉搜索树—— AVL 树和红黑树。而 STL 库中的 map 和 set 在底层中用到的数据结构就是红黑树。

本篇文章将着重讲解关联式容器、键值对、树形结构的关联式容器（set、map、multiset 和 multimap）、AVL 树的模拟实现、红黑树的模拟实现以及 map 和 set 的模拟实现。

2. 关联式容器

在此之前，我们已经接触过 STL 中的部分容器，比如：vector、list、deque、forward_list 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

3. pair——键值对

键值对用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表键值，value 表示与 key 对应的信息。
比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL 中关于键值对的定义：

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){}
};

解释：

1. pair 有两个模板参数，分别命名为 T1 和 T2，用于表示键和值的类型。
2. pair 有两个公有成员类型别名：first_type 和 second_type，分别表示键和值的类型。
3. pair 有两个公有成员变量：first 和 second，用于存储键值对的具体值。

补充：

我们构造键值对时常调用 make_pair 函数，其定义为：

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{return (pair<T1, T2>(x, y));
}

4. 树形结构的关联式容器

根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器：树型结构与哈希结构。

树型结构的关联式容器主要有四种：map、set、multimap、multiset。
这四种容器的共同点是：使用平衡搜索树（即红黑树）作为其底层结构，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

4.1 set

4.1.1 set 的介绍

英文解释：

也就是说：

1. set 是按照一定次序存储元素的容器。

2. 在 set 中，元素的 value 也是其标识符（value 就是 key ，类型为 T），并且每个 value 必须是唯一的。set 中的元素不能在容器中修改（元素总是 const），但是可以从容器中插入或删除它们。

3. 在内部，set 中的元素总是按照其内部比较规则（类型为 Compare）所指示的特定严格弱排序准则进行排序。

4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。

5. set 在底层是用二叉搜索树（红黑树）实现的。

注意：

1. 与 map/multimap 不同，map/multimap 中存储的是真正的键值对 <key, value>，set 中只存放 value。

2. set 中插入元素时，只需要插入 value 即可，不需要构造键值对。

3. set 中的元素不可以重复（因此可以使用set进行去重）。

4. 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列。

5. set 中的元素默认按照小于来比较。

6. set 中查找某个元素，时间复杂度为：$lo{g}_{2}n$。

7. set 中的元素不允许修改。

8. set 中的底层使用二叉搜索树（红黑树）来实现。

4.1.2 set 的使用

1. set 的模板参数列表

说明：

• T：set中存放元素的类型。

• Compare：set 中元素默认按照小于来比较。

• Alloc：set 中元素空间的管理方式，使用 STL 提供的空间配置器管理。

2. set 的构造函数

函数声明	功能介绍
explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());	构造空的 set。
template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());	用 [first, last) 区间中的元素构造 set。
set (const set& x);	set 的拷贝构造。

3. set 的容量操作

   函数名称	函数声明	功能介绍
   empty	bool empty() const;	检测 set 是否为空，空返回 true，否则返回 false。
   size	size_t size() const;	返回 set 中有效元素的个数。

4. set 的修改操作

   函数名称	函数声明	功能介绍
   insert	pair<iterator,bool> insert (const value_type& val);	在 set 中插入元素 val。如果插入成功，返回 <val 位置的迭代器，true>；如果插入失败，说明 val 在 set 中已经存在，返回 <val 位置的迭代器，false>。
   erase	void erase (iterator position); size_t erase (const value_type& val);	删除 set 中 position 位置上的元素。 删除 set 中值为 val 的元素，返回删除的元素的个数（这里只会返回0或1）。
   swap	void swap (set& x);	与 x 交换元素。
   clear	void clear();	将 set 的元素清空。

5. set 的其它操作

   函数名称	函数声明	功能介绍
   find	iterator find (const value_type& val) const;	在 set 中查找值为 val 的元素，如果找到则返回该元素位置的迭代器，未找到则返回 end 迭代器。
   count	size_t count (const value_type& val) const;	返回 set 中值为 val 的元素的个数（这里只会返回0或1）。

6. set 的用法举例

   代码举例：（相关说明在代码注释中）

   #include <iostream>
   #include <set>
   using namespace std;
   void TestSet()
   {// 用数组array中的元素构造setint array[] = { 1,3,5,7,9,9,7,5,3,1 };set<int> s(array, array + sizeof(array) / sizeof(array[0]));cout << s.size() << endl;// 正向打印set中的元素，从打印结果中可以看出：set可去重for (auto& e : s)cout << e << " ";cout << endl;// 插入pair<set<int>::iterator, bool> p1 = s.insert(0);pair<set<int>::iterator, bool> p2 = s.insert(1);cout << "val: " << *(p1.first) << " bool: " << p1.second << endl; // 插入成功cout << "val: " << *(p2.first) << " bool: " << p2.second << endl; // 原容器中已存在1，插入失败// 查找+删除set<int>::iterator it = s.find(9);s.erase(it);s.erase(7);// 使用迭代器逆向打印set中的元素for (auto it = s.rbegin(); it != s.rend(); ++it)cout << *it << " ";cout << endl;// set中值为3的元素出现了几次cout << s.count(3) << endl;
   }
   int main()
   {TestSet();return 0;
   }
   

   运行结果：

   

4.2 map

4.2.1 map 的介绍

英文解释：

也就是说：

1. map 是关联容器，它按照特定的次序（按照 key 来比较）存储由键值 key 和值 value 组合而成的元素。

2. 在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起：pair: typedef pair<const key, T> value_type;

3. 在内部，map中的元素总是按照键值 key 进行比较排序的。

4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代（即对 map 中的元素进行迭代时，可以得到一个有序的序列）。

5. map 支持下标访问符，即在 [] 中放入 key，就可以找到与 key 对应的 value。

6. map 通常被实现为二叉搜索树（红黑树）。

注意：

1. map 中的的元素是键值对。

2. map 中的 key 是唯一的，并且不能修改。

3. 默认按照小于的方式对 key 进行比较。

4. map 中的元素如果用迭代器去遍历，可以得到一个有序的序列。

5. map 的底层为平衡搜索树（红黑树），查找效率为$O(lo{g}_{2}N)$。

6. 支持 [] 操作符，operator[] 中实际进行插入查找。

4.2.2 map 的使用

1. map的模板参数列表

   

   说明：

   key：键值对中 key 的类型。
   T：键值对中 value 的类型。
   Compare：比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元素）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）。
   Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

2. map 的构造函数

   函数声明	功能介绍
   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());	用 [first, last) 区间中的元素构造 map。
   map (const map& x);	map 的拷贝构造。

3. map 的容量操作

   函数名称	函数声明	功能简介
   empty	bool empty ( ) const;	检测 map 中的元素是否为空，是返回 true，否则返回 false。
   size	size_t size() const;	返回 map 中有效元素的个数。

4. map 的元素访问操作

   函数名称	函数声明	功能简介
   operator[]	mapped_type& operator[] (const key_type& k);	返回 k 对应的 value。
   at	mapped_type& at (const key_type& k); const mapped_type& at (const key_type& k) const;	返回 k 对应的 value。

   区分：

   在元素访问时，有一个与 operator[] 类似的操作 at 函数（该函数不常用），都是通过 key 找到与 key 对应的 value 然后返回其引用，不同的是：当 key 不存在时，operator[] 用默认 value 与 key 构造键值对然后插入，返回该默认 value；at 函数直接抛异常。

5. map 的修改操作

   函数名称	函数声明	功能介绍
   insert	pair<iterator,bool> insert (const value_type& val);	在 map 中插入键值对 val。如果插入成功，返回 <val 位置的迭代器，true>；如果插入失败，说明 val 在 map 中已经存在，返回 <val 位置的迭代器，false>。
   erase	void erase (iterator position); size_t erase (const key_type& k);	删除 map 中 position 位置上的元素。 删除 map 中键值为 k 的元素，返回删除的元素的个数（这里只会返回0或1）。
   swap	void swap (map& x);	与 x 交换元素。
   clear	void clear();	将 map 的元素清空。

6. map 的其它操作

   函数名称	函数声明	功能介绍
   find	iterator find (const key_type& k); const_iterator find (const key_type& k) const;	在 map 中查找 key 为 x 的元素，找到返回该元素位置的迭代器，否则返回 end。 在 map 中查找 key 为 x 的元素，找到返回该元素位置的 const 迭代器，否则返回 cend。
   count	size_t count (const key_type& k) const;	返回 map 中值为 k 的键值在 map 中的个数（这里只会返回0或1）。

7. map 的用法举例

   代码举例：（相关说明在代码注释中）

   #include <iostream>
   #include <string>
   #include <map>
   using namespace std;
   void TestMap()
   {map<string, string> m;// 向map中插入元素的方式：// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对m.insert(pair<string, string>("peach", "桃子"));// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对m.insert(make_pair("banan", "香蕉"));// 借用operator[]向map中插入元素/*operator[]的原理是：用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回*/// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，m["apple"] = "苹果";// key不存在时抛异常//m.at("waterme") = "水蜜桃";cout << m.size() << endl;// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列for (auto& e : m)cout << e.first << "--->" << e.second << endl;cout << endl;// map中的键值对key一定是唯一的，如果key存在将插入失败auto ret = m.insert(make_pair("peach", "桃色"));if (ret.second)cout << "<peach, 桃色>不在map中, 已经插入" << endl;elsecout << "键值为peach的元素已经存在：" << ret.first->first << "--->"<< ret.first->second << " 插入失败" << endl;// 删除key为"apple"的元素m.erase("apple");if (1 == m.count("apple"))cout << "apple还在" << endl;elsecout << "apple被吃了" << endl;
   }
   int main()
   {TestMap();return 0;
   }
   

   输出结果：

   

4.3 multiset

4.3.1 multiset 的介绍

英文解释：

也就是说：

1. multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。

2. 在 multiset 中，元素的 value 是其识别符（value 本身就是 key，key 就是 value，类型为 T)。 multiset 元素的值不能在容器中进行修改（因为元素总是 const 的），但可以从容器中插入或删除。

3. 在内部，multiset 中的元素总是按照其内部比较规则（类型为 Compare）所指示的特定严格弱排序准则进行排序。

4. multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列。

5. multiset 底层结构为二叉搜索树（红黑树）。

注意：

1. multiset 只存放 value。

2. multiset 只需要插入 value 即可，不需要构造键值对。

3. 与 set 的区别是，multiset 中的元素可以重复，set 是中 value 是唯一的。

4. 使用迭代器对 multiset 中的元素进行遍历，可以得到有序的序列。

5. multiset 中的元素不能修改。

6. 在 multiset 中找某个元素，时间复杂度为$O(lo{g}_{2}N)$。

7. multiset 的作用：可以对元素进行排序。

4.3.2 multiset 的使用

此处只简单演示 set 与 multiset 的不同，其他接口接口与 set 相同，可参考 set。

#include <iostream>
using namespace std;
#include <set>
void TestMultiset()
{int array[] = { 2,1,3,9,6,0,5,8,4,7,7,9,3,1,5 };// multiset 中的元素可以重复multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));for (auto& e : s)cout << e << " ";cout << endl;return;
}
int main()
{TestMultiset();return 0;
}

输出结果：

4.4 multimap

4.4.1 multimap 的介绍

英文解释：

也就是说：

1. multimap 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对 <key, value>，其中多个键值对之间的 key 是可以重复的。

2. 在 multimap 中，通常按照 key 排序和唯一地标识元素，而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type是组合key和value的键值对：typedef pair<const Key, T> value_type;

3. 在内部，multimap 中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对 key 进行排序的。

4. multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢，但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列。

5. multimap 在底层用二叉搜索树（红黑树）来实现。

注意：

1. multimap 中的 key 是可以重复的。

2. multimap 中的元素默认将 key 按照小于来比较。

3. multimap 中没有重载 operator[] 操作。

4. 使用时与map包含的头文件相同。

4.4.2 multimap 的使用

multimap 中的接口可以参考 map，功能都是类似的。不同点就是 multimap 中没有 operator[] ，key 值可以重复。此处只简单演示一下不同点。

#include <iostream>
using namespace std;
#include <map>
void TestMultimap()
{multimap<string, string> m;m.insert(make_pair("sort", "种类"));m.insert(make_pair("sort", "排序"));m.insert(make_pair("left", "左边"));m.insert(make_pair("left", "离开"));m.insert(make_pair("apple", "苹果"));for (auto& e : m)cout << e.first << "--->" << e.second << endl;return;
}
int main()
{TestMultimap();return 0;
}

输出结果：

5. 底层结构

5.1 AVL 树

5.1.1 AVL 树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是 AVL 树。

• 左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/0/1）。

如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在$O(lo{g}_{2}n)$，搜索时间复杂度O($lo{g}_{2}n$)。

5.1.2 AVL 树节点的定义

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

AVLTreeNode 中的成员包括：

• _left：指向左子节点的指针。
• _right：指向右子节点的指针。
• _parent：指向父节点的指针。
• _kv：存储键值对的 pair 对象，其中键的类型为 K，值的类型为 V。
• _bf：平衡因子，用于表示节点的平衡状态。

5.1.3 AVL 树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点。

2. 调整节点的平衡因子。

代码实现：（相关说明在代码注释中）

bool Insert(const pair<K, V>& kv)
{// 1. 先按照二叉搜索树的规则将节点插入到AVL树中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->_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){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，// 并检测是否破坏了AVL树的平衡性/*cur插入后，parent的平衡因子一定需要调整，在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可此时：parent的平衡因子可能有三种情况：0，正负1， 正负21. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理，具体细节请看后文*/while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;
}

5.1.4 AVL 树的旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL 树的旋转分为四种：

1. 新节点插入较高左子树的左侧—左左：右单旋

代码实现：（相关说明在代码注释中）

/*
上图在插入前，AVL树是平衡的，新节点插入到30的左子树（注意：此处不是左孩子）中，30左
子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，
右子树增加一层，即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，
而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，
更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
*/       
void RotateR(Node* parent)
{// subL: parent的左孩子// subLR: parent左孩子的右孩子Node* subL = parent->_left;Node* subLR = subL->_right;// 30的右孩子作为双亲的左孩子parent->_left = subLR;// 如果60的左孩子的右孩子存在，更新节点双亲if (subLR)subLR->_parent = parent;// 60作为30的右孩子subL->_right = parent;// 因为60可能是棵子树，因此在更新其双亲前必须先保存60的双亲Node* grandparent = parent->_parent;// 更新60的双亲parent->_parent = subL;// 如果60是根节点，更新指向根节点的指针if (_root == parent){_root = subL;// 更新30的双亲subL->_parent = nullptr;}else{// 如果60是子树，可能是其双亲的左子树，也可能是右子树if (grandparent->_left == parent){grandparent->_left = subL;}else{grandparent->_right = subL;}// 更新30的双亲subL->_parent = grandparent;}// 根据调整后的结构更新部分节点的平衡因子subL->_bf = parent->_bf = 0;
}

2. 新节点插入较高右子树的右侧—右右：左单旋

实现及情况考虑可参考右单旋。代码会在最后整体给出。

3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。

代码实现：（相关说明已在代码注释中）

// 旋转之前，60的平衡因子可能是-1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 旋转之前，保存subLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子int bf = subLR->_bf;// 先对30进行左单旋RotateL(subL);// 再对90进行右单旋RotateR(parent);if (0 == bf){// subLR自己就是新增parent->_bf = subL->_bf = subLR->_bf = 0;}else if (-1 == bf){// subLR的左子树新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (1 == bf){// subLR的右子树新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}
}

4. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

参考右左双旋。代码会在最后整体给出。

总结：

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为2或者-2，分以下情况考虑

1. parent 的平衡因子为2，说明 parent 的右子树高，设 parent 的右子树的根为 subR：

• 当 subR 的平衡因子为1时，执行左单旋。
• 当 subR 的平衡因子为-1时，执行右左双旋。

2. parent 的平衡因子为-2，说明 parent 的左子树高，设 parent 的左子树的根为 subL：

• 当 subL 的平衡因子为-1是，执行右单旋。
• 当 subL 的平衡因子为1时，执行左右双旋。

旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新。

5.1.5 AVL 树的验证

AVL 树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证 AVL 树，可以分两步：

1. 验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。

2. 验证其为平衡树

每个节点子树高度差的绝对值不超过1（注意节点中如果没有平衡因子）节点的平衡因子是否计算正确。

代码实现：（相关说明在代码注释中）

bool _IsBalance(Node* root)
{// 空树也是AVL树if (root == nullptr)return true;// 计算root节点的平衡因子：即root左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 如果计算出的平衡因子与root的平衡因子不相等，则一定不是AVL树if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// root平衡因子的绝对值超过1，则一定不是AVL树// root的左和右如果都是AVL树，则该树一定是AVL树return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}bool IsBalance()
{return _IsBalance(_root);
}

5.1.6 AVL 树的删除（了解）

因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

具体实现可参考：平衡二叉树。

5.1.7 AVL 树全部代码

#pragma once
#include<assert.h>template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const 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->_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){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;Node* grandparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (grandparent->_left == parent){grandparent->_left = subR;}else{grandparent->_right = subR;}subR->_parent = grandparent;}subR->_bf = parent->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* grandparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (grandparent->_left == parent){grandparent->_left = subL;}else{grandparent->_right = subL;}subL->_parent = grandparent;}subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (0 == bf){// subRL自己就是新增parent->_bf = subR->_bf = subRL->_bf = 0;}else if (-1 == bf){// subRL的左子树新增parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (1 == bf){// subRL的右子树新增parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (0 == bf){// subLR自己就是新增parent->_bf = subL->_bf = subLR->_bf = 0;}else if (-1 == bf){// subLR的左子树新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (1 == bf){// subLR的右子树新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}bool IsBalance(){return _IsBalance(_root);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}private:Node* _root = nullptr;
};

5.1.8 AVL 树的性能

AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$lo{g}_2(N)$。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。

5.2 红黑树

5.2.1 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

如图所示：

5.2.2 红黑树的性质

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

2. 根节点是黑色的。

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点。

5. 每个叶子结点都是黑色的（此处的叶子结点指的是空结点）。

5.2.3 红黑树节点的定义

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

RBTreeNode 中的成员包括：

• _left：指向左子节点的指针。
• _right：指向右子节点的指针。
• _parent：指向父节点的指针。
• _kv：存储键值对的 pair 对象，其中键的类型为 K，值的类型为 V。
• _col：节点的颜色，用枚举类型 Colour 表示，可能的取值为 RED 和 BLACK。

构造函数默认将 _col 初始化为 RED。

5.2.4 红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点。

2. 检测新节点插入后，红黑树的性质是否造到破坏。

因为新节点的默认颜色是红色，因此，如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。

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

  

  解决方式：将 p，u 改为黑，g 改为红，然后把 g 当成 cur，继续向上调整。

• 情况二：cur 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑。

  

  解决方式：p 为 g 的左孩子，cur 为 p 的左孩子，则针对 p 进行右单旋转；相反，p 为 g 的右孩子，cur 为 p 的右孩子，则针对 p 进行左单旋转。p，g 变色，p 变黑，g 变红。

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

  

  解决方式：p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 进行左单旋转；相反，p 为 g 的右孩子，cur 为 p 的左孩子，则针对 p 进行右单旋转，此时转换成了情况2。

针对每种情况进行相应的处理即可。

代码实现：（相关说明在代码注释中）

bool Insert(const pair<K, V>& kv)
{// 1. 先按照二叉搜索树的规则将节点插入到红黑树中if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 2. 检测新节点插入后，红黑树的性质是否造到破坏。while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){//     g//   p   u// cNode* uncle = grandparent->_right;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上更新处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){// 单旋//     g//   p// cRotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// 双旋//     g//   p//     cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else  // parent == grandparent->_right{//     g//   u   p //          cNode* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){// 单旋//  g//    p//      cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// 双旋//    g//       p //     cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

5.2.5 红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树（中序遍历是否为有序序列）。

2. 检测其是否满足红黑树的性质。

代码实现：（相关说明在代码注释中）

bool Check(Node* root, int blacknum, const int refVal)
{//走到 null 之后，判断blacknum和refVal是否相等if (root == nullptr){if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}// 检测当前节点与其双亲是否都为红色if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}// 统计黑色节点的个数if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);
}
bool IsBalance()
{// 空树也是红黑树if (_root == nullptr)return true;// 检测根节点是否满足情况if (_root->_col == RED){cout << "根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}// 检测是否满足红黑树的性质，blacknum用来记录路径中黑色节点的个数int blacknum = 0;return Check(_root, blacknum, refVal);
}

5.2.6 红黑树的删除（了解）

红黑树的删除本节不做讲解，具体实现可参考：红黑树。

5.2.7 红黑树全部代码

#pragma once
#include <assert.h>enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){//     g//   p   u// cNode* uncle = grandparent->_right;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上更新处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){// 单旋//     g//   p// cRotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// 双旋//     g//   p//     cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else  // parent == grandparent->_right{//     g//   u   p //          cNode* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){// 单旋//  g//    p//      cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// 双旋//    g//       p //     cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* grandparent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (grandparent->_left == parent){grandparent->_left = subR;}else{grandparent->_right = subR;}subR->_parent = grandparent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* grandparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (grandparent->_left == parent){grandparent->_left = subL;}else{grandparent->_right = subL;}subL->_parent = grandparent;}}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED){cout << "根节点必须为黑色" << endl;return false;}// 参考值int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}int Height(){return _Height(_root);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}bool Empty(){return _root == nullptr;}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 NULL;}private:Node* _root = nullptr;
};

5.2.8 红黑树与 AVL 树的比较

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是O($lo{g}_{2}N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

5.3 红黑树模拟实现 STL 中的 map 与 set

5.3.1 迭代器实现

template<class T>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T> Self;Node* _node;__TreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator--(){if (_node->_left){// 上一个就是左子树的最右节点Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{// 左为空，找孩子是父亲右的那个父亲结点Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}assert(parent);_node = parent;}return *this;}Self& operator++(){assert(_node);if (_node->_right){// 下一个就是右子树的最左节点Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{// 右为空，找孩子是父亲左的那个父亲结点Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

5.3.2 改造红黑树

为了方便封装 map 和 set，我们插入了迭代器的操作，然后将之前节点的模板参数<K, V>改成<T>，将红黑树的模板参数<K, V>改成<K, T, KeyOfT>，解释如下：

• k：key 的类型。
• T：如果是 map，则为 pair<K, V>；如果是 set，则为 k。
• KeyOfT：通过 T 来获取 key 的一个仿函数类。

改造后代码实现：

// 文件名：RBTree.h
enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T> iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), 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(iterator(cur), false);}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){//     g//   p   u// cNode* uncle = grandparent->_right;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上更新处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){// 单旋//     g//   p// cRotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// 双旋//     g//   p//     cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else  // parent == grandparent->_right{//     g//   u   p //          cNode* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){// 单旋//  g//    p//      cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// 双旋//    g//       p //     cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* grandparent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (grandparent->_left == parent){grandparent->_left = subR;}else{grandparent->_right = subR;}subR->_parent = grandparent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* grandparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (grandparent->_left == parent){grandparent->_left = subL;}else{grandparent->_right = subL;}subL->_parent = grandparent;}}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << kot(root->_data) << " ";_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}int Height(){return _Height(_root);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}bool Empty(){return _root == nullptr;}Node* Find(const K& key){Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}private:Node* _root = nullptr;KeyOfT kot;
};

5.3.3 map 的模拟实现

map 的底层结构就是红黑树，因此在 map 中直接封装一棵红黑树，然后将其接口包装下即可。

代码实现如下：

#pragma once
#include "RBTree.h"namespace my_map
{template<class K, class V>class map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};// 对类模板取内嵌类型，加typename告诉编译器这里是类型typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}size_t size(){return _t.Size();}bool empty(){return _t.Empty();}iterator find(const K& key){return iterator(_t.Find(key));}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}

5.3.4 set 的模拟实现

set 的底层为红黑树，因此只需在 set 内部封装一棵红黑树，然后将其接口包装下即可。

代码实现如下：

#pragma once
#include"RBTree.h"namespace my_set
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};// 对类模板取内嵌类型，加typename告诉编译器这里是类型typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}size_t size(){return _t.Size;}bool empty(){return _t.Empty();}iterator find(const K& key){return iterator(_t.Find(key));}private:RBTree<K, K, SetKeyOfT> _t;};
}