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

文章目录

1. 前言
2. 关联式容器
3. pair——键值对
4. 树形结构的关联式容器
- 4.1 set
- - 4.1.1 set 的介绍
  - 4.1.2 set 的使用
- 4.2 map
- - 4.2.1 map 的介绍
  - 4.2.2 map 的使用
- 4.3 multiset
- - 4.3.1 multiset 的介绍
  - 4.3.2 multiset 的使用
- 4.4 multimap
- - 4.4.1 multimap 的介绍
  - 4.4.2 multimap 的使用
5. 底层结构
- 5.1 AVL 树
- - 5.1.1 AVL 树的概念
  - 5.1.2 AVL 树节点的定义
  - 5.1.3 AVL 树的插入
  - 5.1.4 AVL 树的旋转
  - 5.1.5 AVL 树的验证
  - 5.1.6 AVL 树的删除（了解）
  - 5.1.7 AVL 树全部代码
  - 5.1.8 AVL 树的性能
- 5.2 红黑树
- - 5.2.1 红黑树的概念
  - 5.2.2 红黑树的性质
  - 5.2.3 红黑树节点的定义
  - 5.2.4 红黑树的插入
  - 5.2.5 红黑树的验证
  - 5.2.6 红黑树的删除（了解）
  - 5.2.7 红黑树全部代码
  - 5.2.8 红黑树与 AVL 树的比较
- 5.3 红黑树模拟实现 STL 中的 map 与 set
- - 5.3.1 迭代器实现
  - 5.3.2 改造红黑树
  - 5.3.3 map 的模拟实现
  - 5.3.4 set 的模拟实现

1. 前言

在学习二叉搜索树的过程中，我们发现当二叉搜索树为单支树时，其搜索的效率是很低的。为了能让二叉搜索树的搜索效率稳定在 $log_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)
	{}
};
解释：

pair 有两个模板参数，分别命名为 T1 和 T2，用于表示键和值的类型。
pair 有两个公有成员类型别名：first_type 和 second_type，分别表示键和值的类型。
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 的介绍

英文解释：

也就是说：

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

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

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

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

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

注意：

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

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

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

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

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

set 中查找某个元素，时间复杂度为： $log_2 n$ 。

set 中的元素不允许修改。

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

4.1.2 set 的使用

set 的模板参数列表

在这里插入图片描述

说明：

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

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

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

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 的拷贝构造。

set 的容量操作

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

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

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 的元素清空。

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）。

set 的用法举例

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

#include <iostream>
#include <set>
using namespace std;
void TestSet()
{
	// 用数组array中的元素构造set
	int 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 的介绍

英文解释：

也就是说：

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

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

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

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

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

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

注意：

map 中的的元素是键值对。

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

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

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

map 的底层为平衡搜索树（红黑树），查找效率为 $O(log_2 N)$ 。

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

4.2.2 map 的使用

map的模板参数列表

说明：

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

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 的拷贝构造。

map 的容量操作

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

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

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 函数直接抛异常。

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 的元素清空。

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）。

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;
	else
		cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
		<< ret.first->second << " 插入失败" << endl;
	// 删除key为"apple"的元素
	m.erase("apple");
	if (1 == m.count("apple"))
		cout << "apple还在" << endl;
	else
		cout << "apple被吃了" << endl;
}
int main()
{
	TestMap();
	return 0;
}

输出结果：

在这里插入图片描述

4.3 multiset

4.3.1 multiset 的介绍

英文解释：

也就是说：

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

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

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

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

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

注意：

multiset 只存放 value。

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

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

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

multiset 中的元素不能修改。

在 multiset 中找某个元素，时间复杂度为 $O(log_2 N)$ 。

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 的介绍

英文解释：

也就是说：

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

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

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

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

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

注意：

multimap 中的 key 是可以重复的。

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

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

使用时与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(log_2 n)$ ，搜索时间复杂度O( $log_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 factor

	AVLTreeNode(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 树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点。
调整节点的平衡因子。

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

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， 正负2
    1. 如果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 树的旋转分为四种：

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

在这里插入图片描述

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

/*
上图在插入前，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;
}

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

在这里插入图片描述

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

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

在这里插入图片描述

将双旋变成单旋后再旋转，即：先对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);
    }
}

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

在这里插入图片描述

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

总结：

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

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

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

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

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

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

5.1.5 AVL 树的验证

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

验证其为二叉搜索树

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

验证其为平衡树

每个节点子树高度差的绝对值不超过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 factor

	AVLTreeNode(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，这样可以保证查询时高效的时间复杂度，即 $log_2 (N)$ 。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。

5.2 红黑树

5.2.1 红黑树的概念

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

如图所示：

5.2.2 红黑树的性质

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

根节点是黑色的。

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

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

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

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 红黑树的插入

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

按照二叉搜索的树规则插入新节点。
检测新节点插入后，红黑树的性质是否造到破坏。

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

约定：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
            // c
            Node* 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
                    // c
                    RotateR(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else
                {
                    // 双旋
                    //     g
                    //   p
                    //     c
                    RotateL(parent);
                    RotateR(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }

                break;
            }
        }
        else  // parent == grandparent->_right
        {
            //     g
            //   u   p 
            //          c
            Node* 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
                    //      c
                    RotateL(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else
                {
                    // 双旋
                    //    g
                    //       p 
                    //     c
                    RotateR(parent);
                    RotateL(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }

                break;
            }
        }
    }

    _root->_col = BLACK;

    return true;
}

5.2.5 红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树（中序遍历是否为有序序列）。
检测其是否满足红黑树的性质。

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

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
				// c
				Node* 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
						// c
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						// 双旋
						//     g
						//   p
						//     c
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}

					break;
				}
			}
			else  // parent == grandparent->_right
			{
				//     g
				//   u   p 
				//          c
				Node* 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
						//      c
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						// 双旋
						//    g
						//       p 
						//     c
						RotateR(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( $log_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
				// c
				Node* 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
						// c
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						// 双旋
						//     g
						//   p
						//     c
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}

					break;
				}
			}
			else  // parent == grandparent->_right
			{
				//     g
				//   u   p 
				//          c
				Node* 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
						//      c
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						// 双旋
						//    g
						//       p 
						//     c
						RotateR(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;
	};
}