C++进阶(四) map和set

一、关联式容器

在vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？ 关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的 键值对，在数据检索时比序列式容器效率更高。

 二、键值对

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

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;  // 定义类型 T1 为 first_type
    typedef T2 second_type;  // 定义类型 T2 为 second_type
    T1 first;  // 第一个元素
    T2 second;  // 第二个元素
    pair(): first(T1()), second(T2())  // 默认构造函数，初始化 first 和 second
    {}
    pair(const T1& a, const T2& b): first(a), second(b)  // 构造函数，用给定值初始化 first 和 second
    {}
};

下面是对每个部分的详细介绍：

1. template <class T1, class T2>：这是一个模板声明，定义了一个通用的数据结构模板，其中有两个模板参数 T1 和 T2，用于表示键值对中的两个成员的类型。

2. struct pair：定义了一个结构体 pair，用来表示键值对。

3. typedef T1 first_type; 和 typedef T2 second_type;：定义了两个别名，分别为 first_type 和 second_type，用于表示 pair 结构体中的第一个成员和第二个成员的类型。

4. T1 first; 和 T2 second;：pair 结构体中的两个成员变量，分别用来存储键值对中的键和值。

5. pair(): first(T1()), second(T2()) {}：默认构造函数，使用 T1() 和 T2() 分别初始化 first 和 second，即默认构造一个 pair 对象时，会创建一个具有默认值的 pair 对象。

6. pair(const T1& a, const T2& b): first(a), second(b) {}：带参数的构造函数，使用传入的参数 a 和 b 分别初始化 first 和 second，即可以根据传入的参数创建一个特定值的 pair 对象。

三 、树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使 用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面依次介绍每一 个容器。

3.1 set的介绍

set文档介绍

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则(<)进行排序(按照从小到大的顺序进行排序)。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

注意：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放 value，但在底层实际存放的是由构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：log_2 n
7. set中的底层使用二叉搜索树(红黑树)来实现。
8. set中的元素不允许修改

(为什么?因为set是基于红黑树实现的，红黑树是一种自平衡的二叉搜索树。在红黑树中，每个节点都有一个固定的键值，这个键值决定了该节点在树中的位置。

如果允许修改set中的元素，那么当元素的键值发生改变时，它在红黑树中的位置也会发生改变。这就需要对整个红黑树进行重新调整，保持其平衡性，这将导致非常复杂和低效的操作。为了保持set的有序性和高效性，C++标准库决定了set中的元素不允许修改。如果需要修改元素，可以先从set中删除该元素，然后再插入修改后的元素。) 

​3.2 set的使用

3.2.1 set的模板参数列表

T: set中存放元素的类型，实际在底层存储的键值对。

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

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

3.2.2  set的构造

 3.2.3  set的迭代器

 3.2.4  set的容量

 3.2.5  set修改操作

 3.2.6  set的使用举例

#define _CRT_SECURE_NO_WARNINGS	
#include <iostream>
using namespace std;
#include <set>
void TestSet() {
    // 用数组array中的元素构造set
    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    set<int> s(array, array + sizeof(array) / sizeof(array[0]));
    cout << s.size() << endl;
    // 正向打印set中的元素，从打印结果中可以看出：set可去重
    for (auto& e : s)
        cout << e << " ";
    cout << endl;
    // 使用迭代器逆向打印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;
}

3.3 map的介绍

map的文档简介

1.  map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2.  在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair: typedef pair value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6.  map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

3.4 map的使用

3.4.1 map的模板参数说明

key: 键值对中key的类型

T： 键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比 较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户 自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的 空间配置器

3.4.2 map的构造

3.4.3 map的迭代器

3.4.4 map的容量与元素访问

问题：当key不在map中时，通过operator获取对应value时会发生什么问题？

注意：在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过 key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]会创建一个具有默认值的新元素并插入到map中，然后返回该默认值的引用。这可能导致意外的结果，因为可能会意外改变map的大小和内容，at()函数直接抛异常。 

3.4.5 map中元素的修改

3.4.6 map的使用举例

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <string>
#include <map>
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;
}

1.  pair是C++标准模板库（STL）中的一个模板类，用于存储两个不同类型的值。它提供了一种方便的方式来将两个值组合在一起，并可以通过pair.first和pair.second来访问这两个值。
2. make_pair是一个模板函数，用于创建一个pair对象。它接受两个参数，并返回一个pair对象，其中第一个参数将成为pair对象的第一个值，第二个参数将成为pair对象的第二个值。

【总结】

1. map中的的元素是键值对
2.  map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4.  map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5.   map的底层为平衡搜索树(红黑树)，查找效率比较高O(log_2 N)
6. 支持[]操作符，operator[]中实际进行插入查找。

3.5 multiset的介绍

multiset文档介绍

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成 的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器 中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭 代器遍历时会得到一个有序序列。
5. multiset底层结构为二叉搜索树(红黑树)。

 注意：

1. multiset中再底层中存储的是<value,value>的键值对
2. mtltiset的插入接口中只需要插入即可
3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
4.   使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
5.  multiset中的元素不能修改
6. 在multiset中找某个元素，时间复杂度为O(log_2 N)
7. multiset的作用：可以对元素进行排序

3.6 multiset的使用

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

#define _CRT_SECURE_NO_WARNINGS	
#include <iostream>
using namespace std;
#include <set>
void TestMutiSet()
{
    int array[] = { 2, 1, 2, 3, 9, 6, 6, 0, 5, 8, 4, 7 };

    // 注意：multiset在底层实际存储的是<int, int>的键值对
    multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
    for (auto& e : s)
        cout << e << " ";
    cout << endl;

}
int main()
{
    TestMutiSet();
    return 0;
}

3.7 multimap的介绍

multimap文档介绍

1. Multimaps是关联式容器，它按照特定的顺序，存储由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在底层用二叉搜索树(红黑树)来实现。

 3.8 multimap的使用

注意：

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

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

3. multimap中没有重载operator[]操作(为什么?)。

multimap没有重载 operator[] 操作符的原因是，operator[] 通常用于访问关联容器中与特定键关联的值。然而，在 multimap 中，一个键可以对应多个值，因此使用 operator[] 来获取值的操作就变得模糊不清。

multimap中的接口可以参考map，功能都是类似的。 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
#include <map>

void TestMutiMap() {
    multimap<int, string> myMultiMap;

    // 插入键值对
    myMultiMap.insert({ 1, "apple" });
    myMultiMap.insert({ 2, "banana" });
    myMultiMap.insert({ 1, "apple" }); // 相同的key和相同的value
    myMultiMap.insert({ 3, "grape" });
    myMultiMap.insert({ 2, "banana" }); // 相同的key和相同的value

    // 遍历输出
    for (const auto& pair : myMultiMap) {
        cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

}
int main() {
    TestMutiMap();
    return 0;
}

 四、底层结构

前面对map/multimap/set/multiset进行了简单的介绍，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

4.1 AVL 树

4.1.1 AVL树的概念

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

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  从图中可以发现，当左边高时，它的高度差就是 -1，当右边高当，高度差就是1。两边一样高时，那么高度差就是 0 。所以可以用平衡因子来确定它的一个高度差,这样可以更好的控制它的高度。

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

 4.1.2 AVL树节点与类的定义

这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，将新构造结点的平衡因子初始设置为0即可。

template<class K,class V>
struct AVLNode
{
	AVLNode<K, V>* _left;     // 该节点的左孩子
	AVLNode<K, V>* _right;    // 该节点的右孩子
	AVLNode<K, V>* _parent;    // 该节点的双亲
	int _bf; //平衡因子，记录高度差
	pair<K, V> _kv; //存储的一对数据
	//构造函数
	AVLNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0) //新增节点肯定是叶子节点，所以高度默认0
		,_kv(kv){}
};

AVL类创建,只需要一个成员变量 root 来指向整颗树的根即可。构造函数就把root初始化为空。

template <class K, class V>
class AVLTree
{
    typedef AVLNode<K, V> Node; 
public:
    AVLTree() :_root(nullptr){} // AVL树构造函数，初始化根节点为空指针
private:
    Node* _root; // AVL树的根节点指针
};

4.1.3 AVL树的插入

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

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

二叉搜索树的插入规则：

1. 待插入结点的key值比当前结点小就插入到该结点的左子树。
2. 待插入结点的key值比当前结点大就插入到该结点的右子树。
3. 待插入结点的key值与当前结点的key值相等就插入失败。

结束条件:直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。

插入结点后需要倒着往上更新平衡因子，更新规则如下：

1. 新增结点在parent的右边，parent的平衡因子++。
2. 新增结点在parent的左边，parent的平衡因子--。

更新完一个parent结点的平衡因子变化情况：

为了保持平衡性，需要根据情况进行不同的旋转操作。

1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。 在这种情况下，parent和cur节点都在左侧子树，而且深度较大，导致失衡。此时进行右旋操作可以恢复平衡。

2. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。 在这种情况下，parent在左侧子树，但是cur在右侧子树，这就导致了parent的左侧子树深度大于右侧子树。此时需要进行双旋操作：先对cur节点进行左旋，再对parent节点进行右旋，以恢复平衡。

3. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。 这是上一种情况的镜像，parent在右侧子树，而cur在左侧子树，导致parent的右侧子树深度大于左侧子树。此时需要进行双旋操作：先对cur节点进行右旋，再对parent节点进行左旋，以恢复平衡。

4. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。 在这种情况下，parent和cur节点都在右侧子树，而且深度较大，导致失衡。此时进行左旋操作可以恢复平衡。

	//插入
	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;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent)
		{
			//  更新双亲的平衡因子
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			// 更新后检测双亲的平衡因子
			if (parent->_bf == 0)
			{
				break;
			}

			/*插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 - 1 ，
			说明以双亲为根的二叉树的高度增加了一层，
			因此需要继续向上调整*/
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			/*双亲的平衡因子为正负2，违反了AVL树的平衡性，
			需要对以pParent为根的树进行旋转处理*/
			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)
				{
					RotateLR(parent); // 左右双旋
				}
				else
				{
					RotateRL(parent); // 右左双旋
				}

				break;
			}
			else
			{
				//插入之前AVL树就有问题
				assert(false);
			}
		}

		return true;
	}

4.1.4 AVL树的旋转

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

1. 左边一边高/新节点插入较高左子树的左侧---左左：右单旋

   右单旋的步骤:
   1.让parent的左节点连接subLR
   2.subLR的父节点连接parent，如果为空则不连接
   3.subL的右节点连接parent
   4.parent的父节点连接subL
   5.让subL作为整个子树的根

   6.更新平衡因子。

   
   （上图h表示是一颗高为h的子树）

   图中parent和subL的平衡因子都变了0,也就意味着这颗子树达到了平衡,无需继续往上更新平衡因子。

   	void RotateR(Node* parent)
   	{
   		// SubL: parent的左孩子
   	// SubLR: parent左孩子的右孩子
   		Node* subL = parent->_left;
   		Node* subLR = subL->_right;
   
   		// 旋转完成之后，30的右孩子subLR作为双亲parent的左孩子
   		parent->_left = subLR;
   		// 如果30的右孩子不为空存在，更新双亲
   		if (subLR)
   			subLR->_parent = parent;
   
   		// 将 parent 60 作为 subL 30的右孩子
   		subL->_right = parent;
   
   		// 因为60可能是棵子树，因此在更新其双亲前必须先保存60的双亲
   		Node* ppnode = parent->_parent;
   		parent->_parent = subL;
   
   		// 若 parent 60是根节点，则更新树的根节点为 subL
   		if (parent == _root)
   		{
   			_root = subL;
   			subL->_parent = nullptr;
   		}
   		else
   		{  // 如果60是子树，可能是其双亲的左子树，也可能是右子树
   			// 更新父节点指向 subL
   			if (ppnode->_left == parent)
   			{
   				ppnode->_left = subL;
   			}
   			else
   			{
   				ppnode->_right = subL;
   			}
   			// 更新30的双亲
   			subL->_parent = ppnode;
   		}
   
   		// 调整旋转后节点的平衡因子
   		subL->_bf = 0;
   		parent->_bf = 0;
   	}

2. 右边一边高/新节点插入较高右子树的右侧---右右：左单旋

   左单旋的步骤:

   1.让parent的右节点连接subRL

   2.subRL的父节点连接parent，如果为空则不连接

   3.subR的左节点连接parent

   4.parent的父节点连接subR

   5.让subR作为整个子树的根

   6.更新平衡因子。

   

   图中parent和subR的平衡因子都变了0,也就意味着这颗子树达到了平衡,,无需继续往上更新平衡因子。

   	void RotateL(Node* parent)
   	{
   		// subR: parent的右孩子
   		Node* subR = parent->_right;
   		// subRL:parent右孩子的左孩子
   		Node* subRL = subR->_left;
   
   		// 旋转完成之后，60的左孩子作为双亲30的右孩子
   		parent->_right = subRL;
   		// 如果60的左孩子不为空存在，更新双亲
   		if (subRL)
   			subRL->_parent = parent;
   
   		// 将parent 30作为subR 60的左孩子
   		subR->_left = parent;
   		// 因为30可能是棵子树，因此在更新其双亲前必须先保存30的双亲
   		Node* ppnode = parent->_parent;
   		parent->_parent = subR;
   
   		// 若 parent 30是根节点，则更新树的根节点为 subR，并将subR的父节点置为空
   		if (parent == _root)
   		{
   			_root = subR;
   			subR->_parent = nullptr;
   		}
   		else
   		{
   			// 如果30是子树，可能是其双亲的左子树，也可能是右子树
   		   // 更新父节点指向 subR
   			if (ppnode->_left == parent)
   			{
   				ppnode->_left = subR;
   			}
   			else
   			{
   				ppnode->_right = subR;
   			}
   			// 更新60的双亲
   			subR->_parent = ppnode;
   		}
   
   		// 调整旋转后节点的平衡因子
   		parent->_bf = 0;
   		subR->_bf = 0;
   	}

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

   左右双旋的步骤：
   1.以subL为旋转点进行左单旋。
   2.以parent为旋转点进行右单旋。
   3.更新平衡因子。

   

   左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

   (注意:下面三张图仅为旋转前后parent、subL、subLR平衡因子变化情况)

   1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。

   

   2、当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。

   3、当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。

   

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

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

   右左双旋的步骤：

   1.以subR为旋转点进行右单旋。
   2.以parent为旋转点进行左单旋。
   3.更新平衡因子。
   

   右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

   (注意:下面三张图仅为旋转前后parent、subR、subRL平衡因子变化情况)

   1、当subRL原始平衡因子是1时，左右双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0。

   

   2、当subRL原始平衡因子是-1时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、1、0。

   

   3、当subRL原始平衡因子是0时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、0、0。

   

   	void RotateRL(Node* parent)
   	{
   		// 保存父节点的左子节点和左子节点的右子节点
   		Node* subR = parent->_right;
   		Node* subRL = subR->_left;
   
   		/*旋转之前，保存subRL的平衡因子，旋转完成之后，
   		需要根据该平衡因子来调整其他节点的平衡因子*/
   		int bf = subRL->_bf;
   
   		// 先对90右旋转
   		RotateR(subR);
   		// 再对30进行左单旋
   		RotateL(parent);
   
   		
   		// 根据 subLR 的平衡因子进行调整
   		if (bf == 1)
   		{
   			subRL->_bf = 0;
   			subR->_bf = 0;
   			parent->_bf = -1;
   		}
   		else if (bf == -1)
   		{
   			subRL->_bf = 0;
   			parent->_bf = 0;
   			subR->_bf = 1;
   		}
   		else if (bf == 0)
   		{
   			subRL->_bf = 0;
   			parent->_bf = 0;
   			subR->_bf = 0;
   		}
   		else
   		{
   			assert(false); //在旋转前树的平衡因子就有问题
   		}
   	}

总结：

假如以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为根的子树个高度降低，已经平衡，不需要再向上更新。 

可结合AVL可视化图网站理解,网站中数字为树的高度,Animation Speed改变变化速度。 

4.1.5 AVL树的验证

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

1.  验证其为二叉搜索树:
   如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

   	//中序遍历子函数
   	void _InOrder(Node* root)
   	{
   		if (root == nullptr)
   			return;
   		_InOrder(root->_left);
   		cout << root->_kv.first << "[" << root->_bf << "]" << endl;
   		_InOrder(root->_right);
   	}
   
   	//中序遍历
   	void InOrder()
   	{
   		_InOrder(_root);
   	}
   

2. 验证其为平衡树 :
   一.每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
   二.节点的平衡因子是否计算正确

	// 计算以root为根节点的树的高度
	int _Height(Node* root)
	{
		// 如果当前节点为空，返回高度0
		if (root == nullptr)
			return 0;

		// 递归计算左子树的高度
		int leftHeight = _Height(root->_left);
		// 递归计算右子树的高度
		int rightHeight = _Height(root->_right);

		// 返回当前节点的左右子树中较大的高度加上自身的高度作为当前节点的高度
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	// 返回整棵树的高度
	int Height()
	{
		// 计算整棵树的高度，初始从根节点开始
		return _Height(_root);
	}

	// 检查以root为根节点的树是否平衡，并更新当前节点的高度信息
	bool _IsBalance(Node* root, int& height)
	{
		// 如果当前节点为空，高度为0，认为是平衡的
		if (root == nullptr)
		{
			height = 0;
			return true;
		}

		int leftHeight = 0, rightHeight = 0;
		// 递归检查左子树和右子树是否平衡
		if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight))
		{
			return false;
		}

		// 检查当前节点是否平衡
		if (abs(rightHeight - leftHeight) >= 2)
		{
			cout << root->_kv.first << "不平衡" << endl;
			return false;
		}

		// 检查当前节点的平衡因子是否异常
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		// 更新当前节点的高度
		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

		return true;
	}

	// 检查整棵树是否平衡
	bool IsBalance()
	{
		int height = 0;
		// 检查整棵树是否平衡，初始从根节点开始
		return _IsBalance(_root, height);
	}

4.1.6 AVL树的查找

AVL树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：

若树为空树，则查找失败，返回nullptr。
若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
若key值等于当前结点的值，则查找成功，返回对应结点。

	//查找
	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; // 没有找到目标节点，返回空指针
	}

4.1.7 AVL树的性能

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