[数据结构与算法]第十五章：map和set

第十五章：map和set

序列式容器：vector / list / deque / ···

【底层为线性序列的数据结构，里面存储的是元素本身 】

关联式容器：map / set / unordered_map / underored_set / ···

【里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高】

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

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

1.1 set的介绍和使用

set的文档

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

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

• 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

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

• set在底层是用二叉搜索树(红黑树)实现的。

注意：

①与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。

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

③set中的元素不可以重复(因此可以使用set进行去重)。

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

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

⑦set中查找某个元素，时间复杂度为：log?n

⑧set中的元素不允许修改

⑨set中的底层使用二叉搜索树(红黑树)来实现

set的构造

set的迭代器

set的容量

set修改操作

使用举例：

#include <set>
void TestSet()
{
	// 用数组array中的元素构造set
	int array[] = { 1, 3, 5, 7, 3, 2, 4, 6, 3, 0, 1, 3, 5, 7, 9, 2, 3, 6, 8, 0 };
	set<int> s(array, array+sizeof(array)/sizeof(array[0]));
    s.insert(10);
	cout << s.size() << endl;

    // 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (const auto& e : s)
		cout << e << " ";
	cout << endl;

    // 使用迭代器逆向打印set中的元素
	set<int>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
    
    //删除set中的元素
	auto pos = s.find(10);
	s.erase(pos);
	s.erase(9);
	for (const auto& e : s)
		cout << e << " ";
	cout << endl;

    // set中值为3的元素出现了几次
	cout << s.count(3) << endl;
    
    //检查单词拼写是否正确
    //把词库中单词放入set的对象中，把每个写出来的单词在set中查一下
    //这里用find来寻找带有特定键的元素
    set<string> strSet;
	strSet.insert("hello");
	strSet.insert("world");
	strSet.insert("left");
	strSet.insert("right");
	strSet.insert("sort");
	set<string>::iterator ret = strSet.find("sort");
	if (ret != strSet.end())
	{
		cout << "找到了" << *ret << endl;
	}
	else 
	{
		cout << "没找到" << endl;
	}
}
int main()
{
    TestSet();
    return 0;
}
/*
11
0 1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8
1
找到了sort
*/

1.2 map的介绍和使用[重点]

map的文档

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

• 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;

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

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

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

• map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map的构造

map的迭代器

map的容量与元素访问

map中元素的修改

使用举例：

#include <string>
#include <map>
void TestMap1()
{
	map<string, string> m;
	
    // 调用pair的构造函数，构造一个匿名对象插入
    // 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
	m.insert(pair<string, string>("peach", "桃子"));
    m.insert(pair<string, string>("watermelon", "西瓜"));
	
    // 调用函数模板，构造对象，好处是不需要去声明pair的参数
    // 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
	m.insert(make_pair("banana", "香蕉"));
	m.insert(make_pair("cherry", "樱桃"));

    // 借用operator[]向map中插入元素
    // 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，
	m["apple"] = "苹果";
    m["grape"] = "葡萄";
    
    // key不存在时抛异常
	//m.at("blueberry") = "蓝莓";

	cout << "map_size：" << m.size() << endl;

    // 用范围for去遍历map中的元素，可以得到一个按照key排序的序列
	for (auto& e : m)
		cout << e.first << "---" << e.second << endl;
	cout << endl;
    
    // 用迭代器去遍历map中的元素(范围for和迭代器等价的)
    map<string,string>::iterator it = m.begin();
    while(it != m.end())
    {
        cout << it->first << "---" << it->second << endl;
        ++it;
    }
    cout << endl;

    // map中的键值对key一定是唯一的，如果key存在将插入失败
	auto ret = m.insert(make_pair("peach", "桃子"));
	if (ret.second)
	{
		cout << "<peach, 桃子>不在map中, 已经插入" << endl;
	}
	else
	{
		cout << "键值为peach的元素已经存在：";
        cout << ret.first->first << "---" << ret.first->second;
        cout << " 插入失败" << endl;
	}

    // 删除key为"apple"的元素，然后遍历
	m.erase("apple");
	if (1 == m.count("apple"))
		cout << "apple还在" << endl;
	else
		cout << "apple被吃了" << endl;
    for (auto& e : m)
		cout << e.first << "---" << e.second << endl;
	cout << endl;
}
/*
map_size：6
apple---苹果
banana---香蕉
cherry---樱桃
grape---葡萄
peach---桃子
watermelon---西瓜

apple---苹果
banana---香蕉
cherry---樱桃
grape---葡萄
peach---桃子
watermelon---西瓜

键值为peach的元素已经存在：peach---桃子 插入失败
apple被吃了
banana---香蕉
cherry---樱桃
grape---葡萄
peach---桃子
watermelon---西瓜
*/

void TestMap2()
{
	string arr[] = { "香蕉","香蕉","西瓜","西瓜","樱桃","水蜜桃","樱桃","西瓜","西瓜","葡萄","水蜜桃","樱桃","菠萝","蓝莓","菠萝" };
	
	//统计次数的方法1
	map<string, int>countMap1;
	for (const auto& str : arr)
	{
		map<string, int>::iterator ret = countMap1.find(str);
		if (ret != countMap1.end())
		{
			ret->second++;
		}
		else
		{
			countMap1.insert(make_pair(str, 1));
		}
	}
	for (const auto& e : countMap1)
	{
		cout << e.first << "---" << e.second << endl;
	}
	
	cout << "==========================================" << endl;
	
	map<string, int>countMap2;
    /*
	for (const auto& str : arr)
	{
		//pair<map<string, int>::iterator, bool> ret = countMap2.insert(make_pair(str, 1));
        auto ret = countMap2.insert(make_pair(str, 1));
        if (ret.second == false)
		{
			ret.first->second++;
		}
	}
	*/
    //map提供了更简便的方法
    for (const auto& str : arr)
	{
		countMap2[str]++;
	}
    
	for (const auto& e : countMap2)
	{
		cout << e.first << "---" << e.second << endl;
	}
}
/*
菠萝---2
蓝莓---1
葡萄---1
水蜜桃---2
西瓜---4
香蕉---2
樱桃---3
==========================================
菠萝---2
蓝莓---1
葡萄---1
水蜜桃---2
西瓜---4
香蕉---2
樱桃---3
*/

总结：

①map中的的元素是键值对

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

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

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

⑤map的底层为平衡搜索树(红黑树)，查找效率比较高O(log?N)

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

? operator[]的原理：

? 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中。

? 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器；

? 如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器；

? operator[]函数最后将insert返回值键值对中的value返回。

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

? at()函数(该函数不常用)与operator[]类似，都是通过key找到与key对应的value然后返回其引用。

? 不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value；

? at()函数直接抛异常。

1.3 multiset的介绍和使用

multiset的文档

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

• 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。

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

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

• multiset底层结构为二叉搜索树(红黑树)。

注意：

①multiset中再底层中存储的是<value, value>的键值对

②mtltiset的插入接口中只需要插入即可

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

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

⑤multiset中的元素不能修改

⑥在multiset中找某个元素，时间复杂度为

⑦multiset的作用：可以对元素进行排序

使用举例：

//此处只简单演示set与multiset的不同，其他接口接口与set相同，可参考set
#include <set>
void TestSet()
{
	int array[] = { 1, 3, 5, 7, 3, 2, 4, 6, 3, 0, 1, 3, 5, 7, 9, 2, 3, 6, 8, 0 };

	// 注意：multiset在底层实际存储的是<int, int>的键值对
	// 排序，不去重，multiset允许键值冗余
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;

	//find查找的val有多个的时候，那么找到的是中序的第一个
	multiset<int>::iterator pos = s.find(3);
	while (*pos==3)
	{
		cout << *pos << endl;
		++pos;
	}
	cout << endl;

	//可以返回匹配特定键的元素数量
	cout << s.count(3) << endl;
    
    //multiset删除，是全部删除
    s.erase(3);
    for (auto& e : s)
		cout << e << " ";
	cout << endl;
}
/*
0 0 1 1 2 2 3 3 3 3 3 4 5 5 6 6 7 7 8 9
3
3
3
3
3

5
0 0 1 1 2 2 4 5 5 6 6 7 7 8 9
*/

1.4 multimap的介绍和使用

multimap的文档

• Multimaps是关联式容器，它按照特定的顺序，存储由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中的接口可以参考map，功能都是类似的。

注意：

①map中的key是唯一的，而multimap中key是可以重复的。

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

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

④使用时与map包含的头文件相同：

1.5 一道例题

前k个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序排序。

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 用<单词，单词出现次数>构建键值对，然后将vector中的单词放进去，统计每个单词出现的次数
        map<string,int> countMap;
        for(size_t i=0;i<words.size();++i)
        {
            countMap[words[i]]++;
        }
        
        // 使用multimap特性进行排序
        multimap<int,string,greater<int>> sortMap;
        for(auto pr:countMap)
        {
            sortMap.insert(make_pair(pr.second,pr.first));
        }

        vector<string> retV;
        auto it = sortMap.begin();
        while(k--)
        {
            retV.push_back(it->second);
            ++it;
        }
        return retV;
    }
};

2.底层架构

2.1 AVL树

2.1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

• 它的左右子树都是AVL树

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

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

2.1.2 AVL树节点的定义

AVL树节点的定义：

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;    // 该节点的左孩子
	AVLTreeNode<K, V>* _right;   // 该节点的右孩子
	AVLTreeNode<K, V>* _parent;  // 该节点的双亲

	int _bf;                     // 该节点的平衡因子

	pair<K, V> _kv;

	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

2.1.3 AVL树的插入

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

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

②调整节点的平衡因子。

? 新增节点在parent右边，parent->_bf++

? 新增节点在parent左边，parent->_bf–

? a.如果parent的平衡因子等于 1 或者 -1 ，继续往上更新

? b.如果parent的平衡因子等于 0 ，停止更新

? c. 如果parent的平衡因子等于 2 或者 -2， 出现不平衡，需要进行旋转处理

bool Insert(const T& data)
{
    // 1. 先按照二叉搜索树的规则将节点插入到AVL树中
	// ...

    // 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性
	while (cur != _root)
	{
		// 更新双亲的平衡因子
		if (cur == parent->_right)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}
		// 更新后检测双亲的平衡因子
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = parent;
			parent = cur->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//双亲的平衡因子为正负2，违反了AVL树的平衡性，需要旋转处理
            //......
		}
		else
		{
			//插入节点之前，树已经不平衡了
			assert(false);
		}
	}
	return true;
}

2.1.4 AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。

根据节点插入位置的不同，AVL树的旋转分为四种：

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

• 当subL的平衡因子为-1是，执行右单旋（新节点插入较高左子树的左侧）

  void _RotateR(Node parent)   //右旋
  {
  	Node* subL = parent->_left;   //subL: parent的左孩子
  	Node* subLR = subL->_right;   //subLR: parent左孩子的右孩子
  
  	//让subLR成为parent的左孩子 
  	parent->_left = subLR;
  	//如果subLR存在，更新其双亲
  	if (subLR)
  	{
  		subLR->_parent = parent;
  	}
  
  	//让parent成为subL的右孩子
  	subL->_right = parent;
  	//parent可能是棵子树，保留其双亲
  	Node temp = parent->_parent;
  	//更新parent的双亲
  	parent->_parent = subL;
  	//更新subL的双亲
  	subL->_parent = temp;
  		
  	if (temp == nullptr)
  	{
  		//如果parent原本是根节点，则更新指向新的根节点的指针
  		_root = subL;
  		subL->_parent = nullptr;
  	}
  	else
  	{
  		//如果parent是子树，可能是其双亲的左子树或者右子树
  		if (temp->_left == parent)
  		{
  			temp->_left = subL;
  		}
  		else
  		{
  			temp->_right = subL;
  		}
  	}
  	//根据调整后的结构更新部分节点的平衡因子
  	parent->_bf = subL->_bf = 0;
  }
  

• 当subL的平衡因子为1时，执行左右双旋 （新节点插入较高左子树的右侧）

  void _RotateLR(Node* parent)   //左右双旋
  {
  	Node* subL = parent->_left;
  	Node* subLR = subL->_right;
  	int bf = subLR->_bf;
  
  	_RotateL(parent->_left);
  	_RotateR(parent);
  
  	//平衡因子调节
  	if (bf == -1) //subLR的左子树高度+1
  	{
  		subL->_bf = 0;
  		parent->_bf = 1;
  		subLR->_bf = 0;
  	}
  	else if (bf == 1) //subLR的右子树高度+1 
  	{
  		subL->_bf = -1;
  		parent->_bf = 0;
  		subLR->_bf = 0;
  	}
  	else if (bf == 0) //subLR为新增节点
  	{
  		subL->_bf = 0;
  		parent->_bf = 0;
  		subLR->_bf = 0;
  	}
  	else
  	{
  		assert(false);
  	}
  }
  

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

• 当subR的平衡因子为1时，执行左单旋（新节点插入较高右子树的右侧）

  //左旋与右旋类似，就不过多注释了
  void _RotateL(Node parent)   //左旋
  {
  	Node* subR = parent->_right;
  	Node* subRL = subR->_left;
  		
  	parent->_right = subRL;
  	if (subRL)
  	{
  		subRL->_parent = parent;
  	}
  	subR->_left = parent;
  	Node* temp = parent->_parent;
  	parent->_parent = subR;
  	subR->_parent = temp;
  	if (temp == nullptr)
  	{
  		_root = subR;
  		subR->_parent = nullptr;
  	}
  	else
  	{
  		if (temp->_left == parent)
  		{
  			temp->_left = subR;
  		}
  		else
  		{
  			temp->_right = subR;
  		}
  	}
  	parent->_bf = subR->_bf = 0;
  }
  

• 当subR的平衡因子为-1时，执行右左双旋（新节点插入较高右子树的左侧）

  void _RotateRL(Node* parent)   //右左双旋
  {
  	Node* subR = parent->_right;
  	Node* subRL = subR->_left;
  	int bf = subRL->_bf;
  
  	_RotateR(parent->_right);
  	_RotateL(parent);
  
  	if (bf == 1)
  	{
  		subR->_bf = 0;
  		parent->_bf = -1;
  		subRL->_bf = 0;
  	}
  	else if (bf == -1)
  	{
  		parent->_bf = 0;
  		subR->_bf = 1;
  		subRL->_bf = 0;
  	}
  	else if (bf == 0)
  	{
  		parent->_bf = 0;
  		subR->_bf = 0;
  		subRL->_bf = 0;
  	}
  	else
  	{
  		assert(false);
  	}
  }
  

2.1.5 AVL树的验证

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

①验证其为二叉搜索树

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

②验证其为平衡树

• 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

• 节点的平衡因子是否计算正确

bool IsAVLTree()
{
	return _IsBalance(_root);
}

bool _IsBalance(Node* root)
{
	if (root == nullptr)
	{
		return true;
	}

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	// 检查一下平衡因子是否正确
	if (rightHeight - leftHeight != root->_bf)
	{
		cout << "平衡因子异常:" << root->_kv.first << endl;
		return false;
	}

	return abs(rightHeight - leftHeight) < 2
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);
}

2.1.6 AVL树的删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点分类删除，然后再更新平衡因子。

2.1.7 AVL树的性能

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

2.1.8 模拟实现完整代码

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;    // 该节点的左孩子
	AVLTreeNode<K, V>* _right;   // 该节点的右孩子
	AVLTreeNode<K, V>* _parent;  // 该节点的双亲

	int _bf;                     // 该节点的平衡因子

	pair<K, V> _kv;

	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;

public:
	AVLTree()
		:_root(nullptr)
	{}

	//拷贝构造和赋值需要实现深拷贝

	~AVLTree()
	{
		_Destory(_root);
		_root = nullptr;
	}

	V& operator[](const K& key)
	{
		pair<Node*, bool> ret = Insert(make_pair(key, V()));
		return ret.first->_kv.second;
	}

	pair<Node*, bool> Insert(const pair<K, V>& kv)   //插入
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return make_pair(_root, true);
		}

		//插入节点
		Node* parent = _root, * cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, true);
			}
		}

		cur = new Node(kv);
		Node* newnode = cur;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

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

			// 更新后检测双亲的平衡因子
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//双亲的平衡因子为正负2，违反了AVL树的平衡性，需要旋转处理
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
					{
						//右单旋
						_RotateR(parent);
					}
					else
					{	//左右双旋
						_RotateLR(parent);
					}
				}
				else
				{
					if (cur->_bf == 1)
					{
						//左单旋
						_RotateL(parent);
					}
					else
					{
						//右左双旋
						_RotateRL(parent);
					}
				}
				break;
			}
			else
			{
				//插入节点之前，树已经不平衡了
				assert(false);
			}
		}
		return make_pair(newnode, true);
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	bool IsAVLTree()
	{
		return _IsBalance(_root);
	}

private:

	Node* _root;

	void _Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
	}

	void _RotateR(Node* parent)   //右旋
	{
		Node* subL = parent->_left;   //subL: parent的左孩子
		Node* subLR = subL->_right;   //subLR: parent左孩子的右孩子

		//让subLR成为parent的左孩子 
		parent->_left = subLR;
		//如果subLR存在，更新其双亲
		if (subLR)
		{
			subLR->_parent = parent;
		}

		//让parent成为subL的右孩子
		subL->_right = parent;
		//parent可能是棵子树，保留其双亲
		Node* temp = parent->_parent;
		//更新parent的双亲
		parent->_parent = subL;
		//更新subL的双亲
		subL->_parent = temp;
		
		if (temp == nullptr)
		{
			//如果parent原本是根节点，则更新指向新的根节点的指针
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			//如果parent是子树，可能是其双亲的左子树或者右子树
			if (temp->_left == parent)
			{
				temp->_left = subL;
			}
			else
			{
				temp->_right = subL;
			}
		}
		//根据调整后的结构更新部分节点的平衡因子
		parent->_bf = subL->_bf = 0;
	}

	void _RotateL(Node* parent)   //左旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		subR->_left = parent;
		Node* temp = parent->_parent;
		parent->_parent = subR;
		subR->_parent = temp;
		if (temp == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (temp->_left == parent)
			{
				temp->_left = subR;
			}
			else
			{
				temp->_right = subR;
			}
		}
		parent->_bf = subR->_bf = 0;
	}

	void _RotateLR(Node* parent)   //左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		_RotateL(parent->_left);
		_RotateR(parent);

		//平衡因子调节
		if (bf == -1) //subLR的左子树高度+1
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1) //subLR的右子树高度+1 
		{
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 0) //subLR为新增节点
		{
			subL->_bf = 0;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void _RotateRL(Node* parent)   //右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		_RotateR(parent->_right);
		_RotateL(parent);

		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 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);
	}
};

2.2 红黑树

2.2.1 红黑树的概念

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

2.2.2 红黑树的性质

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

②根节点是黑色的

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

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

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

2.2.3 红黑树节点的定义

// 节点的颜色
enum Color{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)
	{}
};

2.2.4 红黑树的插入

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 _parent 域指向红黑树的根节点，_left域指向红黑树中最小的节点，_pright域指向红黑树中最大的节点。

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return make_pair(_root, 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 make_pair(cur, false);
		}
	}

	Node* newnode = new Node(kv);
	newnode->_col = RED;
	if (parent->_kv.first < kv.first)
	{
		parent->_right = newnode;
		newnode->_parent = parent;
	}
	else
	{
		parent->_left = newnode;
		newnode->_parent = parent;
	}
	cur = newnode;

	// 如果父亲存在，且颜色为红色就需要处理
	// ......
		
    return make_pair(newnode, true);
}

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

关键点是看叔叔节点（uncle）

①uncle存在且为红色

把parent和uncle变黑，把grandfather变红

②uncle不存在 或者 uncle存在且为黑

? a.新增节点(cur)，parent，grandfather呈直线

? 单旋

? b.新增节点(cur)，parent，grandfather呈折线

? 双旋

Node* grandfather = parent->_parent;
//假设parent为grandfather的左孩子，以此为例
if (parent == grandfather->_left)
{
	Node* uncle = grandfather->_right;
	if (uncle && uncle->_col == RED)
	{
		parent->_col = uncle->_col = BLACK;
		grandfather->_col = RED;
		cur = grandfather;
		parent = cur->_parent;
	}
	else
	{
		if (cur == parent->_left)
		{
			RotateR(grandfather);
			grandfather->_col = RED;
			parent->_col = BLACK;
		}
		else
		{
			RotateL(parent);
			RotateR(grandfather);
			cur->_col = BLACK;
			grandfather->_col = RED;
		}
		break;
	}
}

2.2.5 红黑树的验证

红黑树的检测分为两步：

①检测其是否满足二叉搜索树(中序遍历是否为有序序列)

②检测其是否满足红黑树的性质

bool CheckBlance()
{
	if (_root == nullptr)
	{
		return true;
	}

	if (_root->_col == RED)
	{
		cout << "根节点是红色的" << endl;
		return false;
	}

	// 找最左路径做黑色节点数量参考值
	int blackNum = 0;
	Node* left = _root;
	while (left)
	{
		if (left->_col == BLACK)
		{
			blackNum++;
		}

		left = left->_left;
	}

	int count = 0;
	return _CheckBlance(_root, blackNum, count);
}

bool _CheckBlance(Node* root, int blackNum, int count)
{
	if (root == nullptr)
	{
		if (count != blackNum)
		{
			cout << "黑色节点的数量不相等" << endl;
			return false;
		}

		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "存在连续的红色节点" << endl;
		return false;
	}

	if (root->_col == BLACK)
	{
		count++;
	}

	return _CheckBlance(root->_left, blackNum, count)
		&& _CheckBlance(root->_right, blackNum, count);
}

4.2.6 红黑树与AVL树的比较

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

4.2.7 红黑树的应用

• C++ STL库 – map/set、mutil_map/mutil_set

• Java 库

• linux内核

• 其他一些库

4.2.8 模拟实现完整代码

#pragma once
#include <iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK,
};

//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>
struct __TreeIterator
{
	typedef RBTreeNode<K, V> Node;
	Node* _node;
	__TreeIterator(Node* node)
		:_node(node)
	{}

    //迭代器，这里大概介绍一下，具体实现会在之后map和set的模拟实现里讲解
	//operator*();
	//operator++();
	//operator--();
    //......
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	// 拷贝构造和operator=与二叉搜索树类似，这里不具体实现了

	void Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	~RBTree()
	{
		Destory(_root);
		_root = nullptr;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, 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 make_pair(cur, false);
			}
		}

		Node* newnode = new Node(kv);
		newnode->_col = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = newnode;
			newnode->_parent = parent;
		}
		else
		{
			parent->_left = newnode;
			newnode->_parent = parent;
		}
		cur = newnode;

		// 如果父亲存在，且颜色为红色就需要处理
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			// 关键是看叔叔
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 情况1：uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // uncle不存在 或者 uncle存在且为黑
				{
					// 情况2：单旋
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else // 情况3：双旋
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				// 情况1：
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2：+ 情况3：
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // cur == parent->_left
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					// 插入结束
					break;
				}
			}
		}

		_root->_col = BLACK;
		return make_pair(newnode, true);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}
	}

	bool _CheckBlance(Node* root, int blackNum, int count)
	{
		if (root == nullptr)
		{
			if (count != blackNum)
			{
				cout << "黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			count++;
		}

		return _CheckBlance(root->_left, blackNum, count)
			&& _CheckBlance(root->_right, blackNum, count);
	}

	bool CheckBlance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根节点是红色的" << endl;
			return false;
		}

		// 找最左路径做黑色节点数量参考值
		int blackNum = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				blackNum++;
			}

			left = left->_left;
		}

		int count = 0;
		return _CheckBlance(_root, blackNum, count);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	Node* _root;
};