• 19.set和map

    目录

    1.关联式容器

    2.set（key模型）

    2.1set

    2.2mutiset

    3.map(key 、value模型)

    4.AVL树

    4.1AVL树的概念

    4.2AVL树的实现

    5.红黑树

    5.1红黑树的概念

    5.2红黑树的性质

    5.3红黑树的实现

    6.set和map的模拟实现

    1.关联式容器

    序列是容器：vector、list、deque、forward_list等，主要用来存储数据的。

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

    键值对：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的消息。

    2.set（key模型）

    2.1set

    set是去重+排序

    1.insert 插入函数以及迭代器：

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. void test1()
    6. {
    7. 	set<int> s;
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(4);
    12. 	s.insert(5);
    13. 	//插入两个相等值时，直接去重
    14. 	s.insert(6);
    15. 	s.insert(6);
    16. 	s.insert(8);
    17. 	
    18. 	//迭代器 为中序
    19. 	set<int>::iterator it = s.begin();
    20. 	while (it != s.end())
    21. 	{
    22. 		cout << *it << " ";
    23. 		++it;
    24. 	}
    25. 	cout << endl;
    26. }
    27. int main()
    28. {
    29. 	test1();
    30. 	return 0;
    31. }

    迭代器默认打印就是中序打印： 

    2.erase 删除函数

    值删除和迭代器删除的区别：

    size_type erase (const value_type& val);

    会返回一个size_type,是一个无符号整数，返回删除的数据个数。

    在set传值删除的时候，只有1或0.

    1. #include
    2. #include
    3. using namespace std;
    4. void test2()
    5. {
    6. 	set<int> s;
    7. 	s.insert(1);
    8. 	s.insert(3);
    9. 	s.insert(2);
    10. 	s.insert(4);
    11. 	s.insert(5);
    12. 	s.insert(6);
    13. 	s.insert(8);
    14. 	//迭代器删除
    15. 	set<int>::iterator pos = s.find(3);
    16. 	if (pos!=s.end()) //这里是必须检查的,必须保证迭代器有效
    17. 	{
    18. 		s.erase(pos);
    19. 	}
    20. 	//set::iterator pos = s.find(30);
    21. 	//s.erase(pos); //这里删除30 不存在的，迭代器失效会报错的
    22.  
    23. 	//直接值删除，是不用考虑迭代器失效的问题
    24. 	//当值存在时我就删除。当值不存在时我也不会报错，不会删除。
    25. 	s.erase(30);//这里不会报错，值不存在就不删除，相当于封装了一个迭代器检查if (pos!=s.end())
    26. 	s.erase(8);
    27.  
    28. 	for (auto e : s)
    29. 	{
    30. 		cout << e << " ";
    31. 	}
    32. 	cout << endl;
    33. }
    34. int main()
    35. {
    36. 	test2();
    37. 	return 0;
    38. }

     

    3.swap

     这个函数交换的是两个对象的根节点指针。

    2.2mutiset

    仅排序(不去重)

     1.插入函数

    1. #include
    2. #include
    3. using namespace std;
    4. void test3()
    5. {
    6. 	//排序
    7. 	multiset<int> s;
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(4);
    12. 	s.insert(5);
    13. 	s.insert(6);
    14. 	s.insert(6);
    15. 	s.insert(6);
    16. 	s.insert(8);
    17.  
    18. 	for (auto e : s)
    19. 	{
    20. 		cout << e << " ";
    21. 	}
    22. 	cout << endl;
    23.  
    24. }
    25. int main()
    26. {
    27. 	test3();
    28. 	return 0;
    29. }

    2.erase删除函数

     当有多个相同的值时：find返回中序的第一个值。

    1. #include
    2. #include
    3. using namespace std;
    4. void test3()
    5. {
    6. 	//排序
    7. 	multiset<int> s;
    8. 	s.insert(1);
    9. 	s.insert(1);
    10. 	s.insert(1);
    11. 	s.insert(3);
    12. 	s.insert(2);
    13. 	s.insert(4);
    14. 	s.insert(5);
    15. 	s.insert(5);
    16. 	
    17. 	//find的val有多个值时，返回中序第一个val值所在节点的迭代器。
    18. 	multiset<int>::iterator pos = s.find(5);
    19. 	while (pos!=s.end())
    20. 	{
    21. 		cout << *pos << " ";
    22. 		++pos;
    23. 	}
    24. 	cout << endl;
    25.  
    26. 	for (auto e : s)
    27. 	{
    28. 		cout << e << " ";
    29. 	}
    30. 	cout << endl;
    31.  
    32. }
    33. int main()
    34. {
    35. 	test3();
    36. 	return 0;
    37. }

    如果我想删除所有的1这个值呢？

    使用迭代器：

    1. #include
    2. #include
    3. using namespace std;
    4. void test3()
    5. {
    6. 	//排序
    7. 	multiset<int> s;
    8. 	s.insert(1);
    9. 	s.insert(1);
    10. 	s.insert(1);
    11. 	s.insert(3);
    12. 	s.insert(2);
    13. 	s.insert(4);
    14. 	s.insert(5);
    15. 	s.insert(5);
    16. 	
    17. 	//find的val有多个值时，返回中序第一个val值所在节点的迭代器。
    18. 	multiset<int>::iterator pos = s.find(1);
    19. 	while (pos!=s.end() && *pos==1)
    20. 	{
    21. 		auto next = pos;
    22. 		++next;
    23. 		s.erase(pos); //删除所有的1
    24. 		pos = next;
    25. 	}
    26.  
    27.  
    28. 	for (auto e : s)
    29. 	{
    30. 		cout << e << " ";
    31. 	}
    32. 	cout << endl;
    33.  
    34. }
    35. int main()
    36. {
    37. 	test3();
    38. 	return 0;
    39. }

    使用值删除时最方便的，它会自己删除所有等于1的节点：会返回删除数据的个数。它其实是对上面迭代器的封装。

    1. #include
    2. #include
    3. using namespace std;
    4. void test3()
    5. {
    6. 	//排序
    7. 	multiset<int> s;
    8. 	s.insert(1);
    9. 	s.insert(1);
    10. 	s.insert(1);
    11. 	s.insert(3);
    12. 	s.insert(2);
    13. 	s.insert(4);
    14. 	s.insert(5);
    15. 	s.insert(5);
    16. 	
    17. 	cout << s.erase(1)<//这里会返回删除1的个数
    18. 	for (auto e : s)
    19. 	{
    20. 		cout << e << " ";
    21. 	}
    22. 	cout << endl;
    23.  
    24. }
    25. int main()
    26. {
    27. 	test3();
    28. 	return 0;
    29. }

    set能否借助迭代器进行节点值的修改呢？

    1. #include
    2. #include
    3. using namespace std;
    4. void test3()
    5. {
    6. 	//排序
    7. 	multiset<int> s;
    8. 	s.insert(1);
    9. 	s.insert(1);
    10. 	s.insert(1);
    11. 	s.insert(3);
    12. 	s.insert(2);
    13. 	s.insert(4);
    14. 	s.insert(5);
    15. 	s.insert(5);
    16. 	auto pos = s.find(1);
    17. 	if (pos != s.end())
    18. 	{
    19. 		*pos += 10;//这里是不能进行修改的，如果修改了有可能破坏搜索二叉树，因此这里去调用operator*()的时候，返回的是const 的引用
    20. 	}
    21. 	
    22. 	for (auto e : s)
    23. 	{
    24. 		cout << e << " ";
    25. 	}
    26. 	cout << endl;
    27.  
    28. }
    29. int main()
    30. {
    31. 	test3();
    32. 	return 0;
    33. }

    直接标红报错：

    3.map(key 、value模型)

    在map里面不是存的两个值key和value，而是有进行了一层的封装，封装了一层类(结构体) ,map里面存的就是一个对象。封装的这个结构体就是pair，pair里面有2个值。

    1.插入函数

     pair的构造函数：

     make_pair:对pair的封装，是函数模板

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. void test1()
    6. {
    7. 	map dict;
    8. 	//直接创建pair对象，就行插入
    9. 	pair kv1("sort","排序");
    10. 	dict.insert(kv1);
    11. 	//创建匿名对象插入
    12. 	dict.insert(pair("left","左"));
    13. 	//使用make_pair,可以自动推导类型
    14. 	dict.insert(make_pair("string","字符串"));//常用
    15. 	//map::iterator it = dict.begin();
    16. 	auto it = dict.begin();
    17. 	while (it!=dict.end())
    18. 	{
    19. 		//cout << *it << " ";  //去调用*重载，_node->value_type  去调用pair结构体,结构体没有重载流提取，因此不行
    20. 		//cout << (*it).first << ':' << (*it).second <
    21. 		//最好使用-> 看起来就知道是个自定义类型的数据
    22. 		cout << it->first << ':' << it->second << endl;
    23. 		++it;
    24. 	}
    25. 	cout << endl;
    26. 	//支持迭代器，就支持范围for
    27. 	for (auto & kv : dict) //最好使用引用，存在拷贝构造
    28. 	{
    29. 		//kv=*it
    30. 		cout << kv.first << ':' << kv.second << endl;
    31. 	}
    32. }
    33. int main()
    34. {
    35. 	test1();
    36. 	return 0;
    37. }

    其他函数和set的基本差不多的。省略

    2.水果统计次数

    第一种代码：

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. void test2()
    6. {
    7. 	string arr[] = { "苹果", "香蕉", "草莓", "樱桃", "香蕉", "苹果" };
    8. 	mapint> countMap; 
    9. 	//map的key不支持修改，但是value是支持修改的
    10. 	for (auto& str:arr)
    11. 	{
    12. 		auto ret = countMap.find(str);
    13. 		if (ret==countMap.end())
    14. 		{
    15.             //没有对应的水果，就插入
    16. 			countMap.insert(make_pair(str,1));
    17. 		}
    18. 		else
    19. 		{
    20.             //有对应的水果就次数+1
    21. 			ret->second++;
    22. 		}
    23. 	}
    24.  
    25. 	for (auto & kv : countMap)
    26. 	{
    27. 		//kv=*it
    28. 		cout << kv.first << ':' << kv.second << endl;
    29. 	}
    30.  
    31. }
    32. int main()
    33. {
    34. 	test2();
    35. 	return 0;
    36. }

    上面的代码比较冗余：你find查找了依次，若是没有查找到，insert又去查找了依次，所以查找了2次。

    对代码进行优化：

    insert函数的返回值，是一个pair对象

    insert函数的返回值，是一个pair对象，如果插入的元素或该元素与map中的key相等，那么就返回这个节点的迭代器，pair的first存储这个迭代器。pair的second 存储bool值，当插入一个新节点，则返回true,若是map中存在该key,那么就返回false。

    代码改进：

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. void test3()
    6. {
    7. 	string arr[] = { "苹果", "香蕉", "草莓", "樱桃", "香蕉", "苹果" };
    8. 	mapint> countMap;
    9. 	for (auto &str : arr)
    10. 	{
    11. 		//pair::iterator, bool> ret = countMap.insert(make_pair(str, 1));
    12. 		auto ret = countMap.insert(make_pair(str, 1));
    13. 		if (ret.second==false)//说明这个节点key存在了
    14. 		{
    15. 			ret.first->second++; //次数+1，这里去调用迭代器中的operator->()重载
    16. 		}
    17. 	}
    18. 	for (auto & kv : countMap)
    19. 	{
    20. 		//kv=*it
    21. 		cout << kv.first << ':' << kv.second << endl;
    22. 	}
    23.  
    24. }
    25. int main()
    26. {
    27. 	test3();
    28. 	return 0;
    29. }

    方括号：

    这里是去调用insert，返回一个pair的对象，pair对象中第一个first存的map是迭代器，*这个迭代器，会去调用迭代器的*重载，找到map节点的value_type（pair对象）, .second 取第二个值。

     返回值是mapped_type& ，这里是引用，对pair对象第二个变量(value)的引用。

     对代码改进:

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. void test3()
    6. {
    7. 	string arr[] = { "苹果", "香蕉", "草莓", "樱桃", "香蕉", "苹果" };
    8. 	mapint> countMap;
    9. 	for (auto &str : arr)
    10. 	{
    11. 		countMap[str]++; //直接取调用operator[]
    12. 	}
    13. 	for (auto & kv : countMap)
    14. 	{
    15. 		//kv=*it
    16. 		cout << kv.first << ':' << kv.second << endl;
    17. 	}
    18.  
    19. }
    20. int main()
    21. {
    22. 	test3();
    23. 	return 0;
    24. }

    [ ]的功能：1.插入2.查找3.修改(value的值)

    1. void test4()
    2. {
    3. 	mapdict;
    4. 	dict.insert(make_pair("sort","排序"));
    5. 	dict.insert(make_pair("left", "左边"));
    6. 	dict.insert(make_pair("left", "剩余"));//不会插入
    7.  
    8. 	dict["left"] = "剩余";  //修改
    9. 	dict["test"]; //插入
    10. 	cout << dict["sort"] << endl;//查找
    11. 	dict["string"] = "字符串"; //插入+修改
    12. }
    13.  
    14.  
    15. int main()
    16. {
    17. 	test4();
    18. 	return 0;
    19. }

    multimap 用法基本都是差不多的，key相同也会插入。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. void test5()
    7. {
    8. 	multimapdict;
    9. 	dict.insert(make_pair("sort", "排序"));
    10. 	dict.insert(make_pair("left", "左边"));
    11. 	dict.insert(make_pair("left", "剩余"));//会插入
    12. 	dict.insert(make_pair("left", "向左"));
    13.  
    14. 	cout << dict.count("left") << endl;//查找次数
    15.  
    16. 	auto it = dict.begin();
    17. 	while (it!=dict.end())
    18. 	{
    19. 		cout << it->first<<':'<second << endl;
    20. 		++it;
    21. 	}
    22. 	cout << endl;
    23. }
    24.  
    25. int main()
    26. {
    27. 	test5();
    28. 	return 0;
    29. }

    3.排序

    找出前K个最喜欢吃的水果

    1.利用sort

    第一种写法：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. //提供一个仿函数
    9. struct CountVal
    10. {
    11. 	bool operator()(const pairint>& p1,const pairint>& p2)
    12. 	{
    13. 		return p1.second > p2.second;
    14. 	}
    15. };
    16. void GetFavoriteFruit1(const vector& fruits, size_t k) 
    17. {
    18. 	mapint> coutMap;
    19. 	for (auto& str:fruits)
    20. 	{
    21. 		coutMap[str]++;//统计次数
    22. 	}
    23. 	//找前k个
    24. 	vectorint>> Vsort;
    25. 	for (auto& e : coutMap)
    26. 	{
    27. 		Vsort.push_back(e);
    28. 	}
    29. 	//因为sort是随机迭代器，而map是双向迭代器，不行的，所以必须使用vector<>
    30. 	sort(Vsort.begin(), Vsort.end(), CountVal()); //pair提供了排序，但是不是我们想要的。需要自己写仿函数，排降序
    31.  
    32. 	for (size_t i = 0; i < k;i++)
    33. 	{
    34. 		cout << Vsort[i].first << ':' << Vsort[i].second << endl;
    35. 	}
    36. 	cout << endl;
    37.  
    38. }
    39. int main()
    40. {
    41. 	vector v = { "苹果", "苹果", "香蕉", "草莓", "草莓", "苹果", "苹果", "樱桃", "香蕉","葡萄"};
    42. 	GetFavoriteFruit1(v,3);
    43. 	return 0;
    44. }

    pair提供的排序，不适合我们这里

    第一种写法存在大量的深拷贝，因此使用存迭代器，继续改进第二种：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. //提供一个仿函数
    8. struct CountVal
    9. {
    10. 	bool operator()(mapint>::iterator& it1, mapint>::iterator& it2)
    11. 	{
    12. 		return it1->second > it2->second;
    13. 	}
    14. };
    15. void  GetFavoriteFruit2(const vector& fruits, size_t k)
    16. {
    17. 	mapint> coutMap;
    18. 	for (auto& str : fruits)
    19. 	{
    20. 		coutMap[str]++;//统计次数
    21. 	}
    22. 	vectorint>::iterator> Vsort;//直接存迭代器，最多4个字节
    23. 	auto it = coutMap.begin();
    24. 	while (it != coutMap.end())
    25. 	{
    26. 		Vsort.push_back(it);
    27. 		++it;
    28. 	}
    29. 	sort(Vsort.begin(), Vsort.end(), CountVal());
    30. 		for (size_t i = 0; i < k;i++)
    31. 		{
    32. 			cout << Vsort[i]->first << ':' << Vsort[i]->second << endl;
    33. 		}
    34. 		cout << endl;
    35. 	 
    36. }
    37.  
    38. int main()
    39. {
    40. 	vector v = { "苹果", "苹果", "香蕉", "草莓", "草莓", "苹果", "苹果", "樱桃", "香蕉","葡萄"};
    41. 	GetFavoriteFruit2(v,3);
    42. 	return 0;
    43. }

    2.使用multimap

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. using namespace std;
    9. void GetFavoriteFruit3(const vector& fruits, size_t k)
    10. {
    11. 	mapint> coutMap;
    12. 	for (auto& str : fruits)
    13. 	{
    14. 		coutMap[str]++;//统计次数
    15. 	}
    16.  
    17. 	multimap<int, string, greater<int>> sortMap; //这里可以控制升降序，利用仿函数
    18. 	for (auto& kv : coutMap)
    19. 	{
    20. 		sortMap.insert(make_pair(kv.second,kv.first)); //这里使用second做为第一个值，first做第二个值
    21. 	}
    22.  
    23. 	auto it = sortMap.begin();
    24. 	for (size_t i = 0; i < k; i++)
    25. 	{
    26. 		cout << it->second << ':' << it->first << endl;
    27. 		++it;
    28. 	}
    29.  
    30.  
    31. }
    32.  
    33. int main()
    34. {
    35. 	vector v = { "苹果", "苹果", "香蕉", "草莓", "草莓", "苹果", "苹果", "樱桃", "香蕉","葡萄"};
    36. 	GetFavoriteFruit3(v,3);
    37. 	return 0;
    38. }

    3.使用优先级队列

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. using namespace std;
    9. //提供一个仿函数
    10. struct CountVal
    11. {
    12. 	bool operator()(const pairint>&it1, const pairint>& it2)
    13. 	{
    14. 		return it1.second < it2.second; //给小于建大堆
    15. 	}
    16. };
    17. void GetFavoriteFruit4(const vector& fruits, size_t k)
    18. {
    19. 	mapint> coutMap;
    20. 	for (auto& str : fruits)
    21. 	{
    22. 		coutMap[str]++;//统计次数
    23. 	}
    24.  
    25. 	priority_queueint>, vectorint>>, CountVal> pq;
    26. 	for (auto&kv : coutMap)
    27. 	{
    28. 		pq.push(kv);
    29. 	}
    30.  
    31. 	while (k--)
    32. 	{
    33. 		cout << pq.top().first << ':' << pq.top().second << endl;
    34. 		pq.pop();
    35. 	}
    36. 	cout << endl;
    37. }
    38. int main()
    39. {
    40. 	vector v = { "苹果", "苹果", "香蕉", "草莓", "草莓", "苹果", "苹果", "樱桃", "香蕉","葡萄"};
    41. 	GetFavoriteFruit4(v,3);
    42. 	return 0;
    43. }

    这里也存在多次深拷贝，因此继续改进：存迭代器

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. using namespace std;
    9. //提供一个仿函数
    10. struct CountVal
    11. {
    12. 	bool operator()(const mapint>::iterator&it1, const mapint>::iterator& it2)
    13. 	{
    14. 		return it1->second < it2->second;
    15. 	}
    16. };
    17. void GetFavoriteFruit5(const vector& fruits, size_t k)
    18. {
    19. 	mapint> coutMap;
    20. 	for (auto& str : fruits)
    21. 	{
    22. 		coutMap[str]++;//统计次数
    23. 	}
    24.  
    25. 	priority_queueint>::iterator, vectorint>::iterator>, CountVal> pq;
    26. 	auto it = coutMap.begin();
    27. 	while (it!=coutMap.end())
    28. 	{
    29. 		pq.push(it);
    30. 		++it;
    31. 	}
    32.  
    33. 	while (k--)
    34. 	{
    35. 		cout << pq.top()->first << ':' << pq.top()->second << endl;
    36. 		pq.pop();
    37. 	}
    38. 	cout << endl;
    39. }
    40. int main()
    41. {
    42. 	vector v = { "苹果", "苹果", "香蕉", "草莓", "草莓", "苹果", "苹果", "樱桃", "香蕉","葡萄"};
    43. 	GetFavoriteFruit5(v,3);
    44. 	return 0;
    45. }

    4.OJ题

    力扣https://leetcode.cn/problems/top-k-frequent-words/description/

    1. class Solution {
    2. public:
    3.     vector topKFrequent(vector& words, int k) {
    4.         mapint> countMap;
    5.         for(auto& kv:words)
    6.         {
    7.             countMap[kv]++; //统计次数
    8.         }
    9.  
    10.         multimap<int,string,greater<int>> sortmap;//利用mutilmap进行排序
    11.         for(auto& e:countMap)
    12.         {
    13.             //e=*it
    14.             sortmap.insert(make_pair(e.second,e.first));//这里反着使用，使用value进行排序
    15.         }
    16.         auto it=sortmap.begin();
    17.         vector v;
    18.         for(int i=0;i
    19.         {
    20.             v.push_back(it->second);
    21.             ++it;
    22.  
    23.         }
    24.         return v;
    25.  
    26.     }
    27. };

    4.AVL树

    4.1AVL树的概念

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

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

    1.它的左右子树都是AVL树

    2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。平衡因子不一定需要，使用平衡因子是一种控制实现方式。平衡因子：右子树-左子树。这里规定一下，后面代码都是这样。也可以左减右。

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

    4.2AVL树的实现

    1.AVL树的框架

    1. template<class K,class V>
    2. struct AVLTreeNode
    3. {
    4. 	//3叉链
    5. 	AVLTreeNode* _left;
    6. 	AVLTreeNode* _right;
    7. 	AVLTreeNode* _parent;
    8. 	pair _kv;
    9. 	int _bf;//平衡因子
    10.  
    11. 	AVLTreeNode(const pair& kv)
    12. 		:_left(nullptr)
    13. 		,_right(nullptr)
    14. 		,_parent(nullptr)
    15. 		,_kv(kv)
    16.         ,_bf(0)
    17. 	{}
    18.  
    19. };
    20.  
    21.  
    22. template<class K,class V>
    23. class AVLTree
    24. {
    25. 	typedef struct AVLTreeNode Node;
    26. public:
    27. 	AVLTree()
    28. 		:_root(nullptr)
    29. 	{}
    30.  
    31. ///在这里写成员函数
    32.  
    33. private:
    34. 	Node* _root;
    35. };

    2.插入函数

    插入函数：

    1.搜索二叉树一样的插入，但是需要注意3叉链，需要链上

    2.对树进行平衡控制

      2.1插入结点后先更新平衡因子

      2.2根据平衡因子，是旋转还是不旋转

    更新平衡因子的过程，根据平衡因子分析什么时候需要旋转：

    更新平衡因子的结束条件：while(parent) ,插入节点有可能影响整条子树。

     这段代码就是插入结点，并且更新平衡因子：

    1. 	bool insert(const pair& kv)
    2. 	{
    3. 		//1.插入数据，和搜索二叉树一样，先插入数据
    4.  
    5. 		if (_root == nullptr)
    6. 		{
    7. 			_root = new Node(kv);
    8. 			return true;
    9. 		}
    10.  
    11. 		Node*cur = _root;
    12. 		Node*parent = nullptr;
    13. 		while (cur)
    14. 		{
    15. 			if (cur->_kv.first > kv.first)
    16. 			{
    17. 				parent = cur;
    18. 				cur = cur->_left;
    19. 			}
    20. 			else if (cur->_kv.first < kv.first)
    21. 			{
    22. 				parent = cur;
    23. 				cur = cur->_right;
    24. 			}
    25. 			else
    26. 			{
    27. 				//有这个结点之后，就去重了
    28. 				return false;
    29. 			}
    30. 		}
    31. 		//没有这个结点
    32. 		cur = new Node(kv);
    33. 		if (parent->_kv.first > kv.first)
    34. 		{
    35. 			parent->_left = cur;
    36. 			cur->_parent = parent;
    37. 		}
    38. 		else 
    39. 		{
    40. 			parent->_right = cur;
    41. 			cur->_parent = parent;
    42. 		}
    43.  
    44. 		//2.控制平衡
    45. 		//   1.更新平衡因子
    46. 		//   2.出现异常平衡因子，那么需要旋转平衡处理
    47.  
    48. 		while (parent) //判断条件是根结点的_parent 为nullptr
    49. 		{
    50. 			//更新平衡因子
    51. 			if (parent->_left == cur)
    52. 			{
    53. 				parent->_bf--;
    54. 			}
    55. 			else 
    56. 			{
    57. 				parent->_bf++;
    58. 			}
    59.  
    60. 			if (parent->_bf==0)
    61. 			{
    62. 				break;
    63. 			}
    64. 			//根据平衡因子判断是旋转还是继续更新平衡因子
    65. 			else if (parent->_bf==1 || parent->_bf==-1)
    66. 			{
    67. 				//子树变成了1或-1，需要继续向上更新
    68. 				cur = parent;
    69. 				parent = parent->_parent;
    70. 			}
    71. 			else if (parent->_bf == -2 || parent->_bf == 2)
    72. 			{
    73. 				//此时需要进行旋转了。
    74. 				if (parent->_bf == -2 && cur->_bf == -1)//向右单旋的条件
    75. 				{
    76. 					RoateR(parent);
    77. 				}
    78. 				else if (parent->_bf==2 && cur->_bf ==1)//向左单旋的条件
    79. 				{
    80. 					RoateL(parent);
    81. 				}
    82. 				else if (parent->_bf==-2 && cur->_bf==1)//左右旋的条件
    83. 				{
    84. 					RoateLR(parent);
    85. 				}
    86. 				else if (parent->_bf == 2 && cur->_bf == -1)//右左旋的条件
    87. 				{
    88. 					RoateRL(parent);
    89. 				}
    90.  
    91. 				break;//旋转完，就结束了，树已经平衡了
    92. 			}
    93. 			else
    94. 			{
    95. 				//这里说明上一次平衡因子出现了问题，不出问题不会到这里
    96. 				assert(false); //出现问题了。
    97. 			}
    98.  
    99. 		}
    100. 		return true;
    101.  
    102. 	}

    简单的插入过程： 

    3.AVL树的旋转

    1.右单旋

    由下图看出：parent->_bf==-2 && cur->_bf==-1 进行右单旋

    右单旋代码： 

    1. 	void RoateR(Node*parent)//右单旋
    2. 	{
    3. 		Node*subL = parent->_left;
    4. 		Node*subLR = subL->_right;
    5. 		
    6. 		parent->_left = subLR;
    7. 		if (subLR) //subL右边可能为空
    8. 			subLR->_parent = parent;
    9.  
    10. 		subL->_right = parent;
    11. 		Node*parentPrev = parent->_parent; //记录parent的上一个结点
    12. 		parent->_parent = subL;
    13. 		if (parent == _root) //若parent是根节点
    14. 		{
    15. 			_root = subL;
    16. 			subL->_parent = nullptr;
    17. 		}
    18. 		else //若不是根,而是子树
    19. 		{
    20. 			if (parentPrev->_left == parent)//是左边子树
    21. 			{
    22. 				parentPrev->_left = subL;
    23. 			}//是右边子树
    24. 			else
    25. 			{
    26. 				parentPrev->_right = subL;
    27. 			}
    28. 			subL->_parent = parentPrev;
    29. 		}
    30. 		parent->_bf = subL->_bf = 0;//更新一下平衡因子
    31. 	}

    2.左单旋

    由下图看出：parent->_bf==2 && cur->_bf==1 进行左单旋

     左单旋代码：

    1. 	void RoateL(Node*parent)//左单旋
    2. 	{
    3. 		Node* subR = parent->_right;
    4. 		Node*subRL = subR->_left;
    5.  
    6. 		parent->_right = subRL;
    7. 		if (subRL) //subRL有可能为空
    8. 			subRL->_parent = parent;
    9. 		subR->_left = parent;
    10.  
    11. 		Node*parentPrev = parent->_parent;
    12. 		parent->_parent = subR;
    13.  
    14. 		if (_root==parent)//如果是根节点
    15. 		{
    16. 			_root = subR;
    17. 			subR->_parent = nullptr;
    18. 		}
    19. 		else
    20. 		{
    21. 			if (parentPrev->_left==parent)
    22. 			{
    23. 				parentPrev->_left = subR;
    24. 			}
    25. 			else
    26. 			{
    27. 				parentPrev->_right = subR;
    28. 			}
    29. 			subR->_parent = parentPrev;
    30. 		}
    31. 		subR->_bf = parent->_bf = 0;//更新平衡因子
    32. 	}

    有了左单旋和右单旋的条件，以及函数的实现，因此insert继续完善左单旋和右单旋 ：

    1. 	bool insert(const pair& kv)
    2. 	{
    3. 		//1.插入数据，和搜索二叉树一样，先插入数据
    4.  
    5. 		if (_root == nullptr)
    6. 		{
    7. 			_root = new Node(kv);
    8. 			return true;
    9. 		}
    10.  
    11. 		Node*cur = _root;
    12. 		Node*parent = nullptr;
    13. 		while (cur)
    14. 		{
    15. 			if (cur->_kv.first > kv.first)
    16. 			{
    17. 				parent = cur;
    18. 				cur = cur->_left;
    19. 			}
    20. 			else if (cur->_kv.first < kv.first)
    21. 			{
    22. 				parent = cur;
    23. 				cur = cur->_right;
    24. 			}
    25. 			else
    26. 			{
    27. 				//有这个结点之后，就去重了
    28. 				return false;
    29. 			}
    30. 		}
    31. 		//没有这个结点
    32. 		cur = new Node(kv);
    33. 		if (parent->_kv.first > kv.first)
    34. 		{
    35. 			parent->_left = cur;
    36. 			cur->_parent = parent;
    37. 		}
    38. 		else 
    39. 		{
    40. 			parent->_right = cur;
    41. 			cur->_parent = parent;
    42. 		}
    43.  
    44. 		//2.控制平衡
    45. 		//   1.更新平衡因子
    46. 		//   2.出现异常平衡因子，那么需要旋转平衡处理
    47.  
    48. 		while (parent) //判断条件是根结点的_parent 为nullptr
    49. 		{
    50. 			//更新平衡因子
    51. 			if (parent->_left == cur)
    52. 			{
    53. 				parent->_bf--;
    54. 			}
    55. 			else 
    56. 			{
    57. 				parent->_bf++;
    58. 			}
    59. 			//根据平衡因子判断是旋转还是继续更新平衡因子
    60. 			if (parent->_bf==1 || parent->_bf==-1)
    61. 			{
    62. 				//子树变成了1或-1，需要继续向上更新
    63. 				cur = parent;
    64. 				parent = parent->_parent;
    65. 			}
    66. 			else if (parent->_bf == -2 || parent->_bf == 2)
    67. 			{
    68. 				//此时需要进行旋转了。
    69. 				if (parent->_bf == -2 && cur->_bf == -1)//向右单旋的条件
    70. 				{
    71. 					RoateR(parent);
    72. 				}
    73. 				else if (parent->_bf==2 && cur->_bf ==1)//向左单旋的条件
    74. 				{
    75. 					RoateL(parent);
    76. 				}
    77.  
    78. 				break;//旋转完，就结束了，树已经平衡了
    79. 			}
    80. 			else
    81. 			{
    82. 				//这里说明上一次平衡因子出现了问题，不出问题不会到这里
    83. 				assert(false); //出现问题了。
    84. 			}
    85.  
    86. 		}
    87. 		return true;
    88.  
    89. 	}

    当插入结点后，发现并不是单独的一侧高，而是左高和右高，或右高和左高，因此需要双旋。双旋又分为左右旋和右左旋。

    3.先进行左单旋再右旋(左右旋)

    在b或c插入新的结点，都会发生双旋，左右双旋的条件parent->_bf==-2 && cur->_bf==1  进行左单旋再右单旋。

    或者在b点插入新的结点，是一样的：

    因此代码为：但是这里更新平衡因子的时候都是更新成0，也就是上面图，最后的结果是0，0。但是这样是不对的。后面会讲解如何更新平衡因子。

    1. void RoateLR(Node*parent)//左右旋
    2. 	{
    3. 		RoateL(parent->_left);//先进行左单旋
    4. 		RoateR(parent);//在进行右单旋
    5. 	}

    4.先进行右单旋再左旋(右左旋)

    在b或c插入新的结点，都会发生双旋，右左双旋的条件parent->_bf==2 && cur->_bf==-1  进行右单旋再左单旋。

     或者在c插入结点：也是一样的

    因此代码为：但是这里更新平衡因子的时候都是更新成0，也就是上面图，最后的结果是0，0。但是这样是不对的。后面会讲解如何更新平衡因子。

    1. 	void RoateRL(Node*parent)//右左旋
    2. 	{
    3. 		RoateR(parent->_right);//先进行右单旋
    4. 		RoateL(parent);//在进行左单旋
    5. 	}

    所以有了上面的情况代码可以继续更新为：

    1. #include
    2. #include
    3. using namespace std;
    4. #include
    5. template<class K,class V>
    6. struct AVLTreeNode
    7. {
    8. 	//3叉链
    9. 	AVLTreeNode* _left;
    10. 	AVLTreeNode* _right;
    11. 	AVLTreeNode* _parent;
    12. 	pair _kv;
    13. 	int _bf;//平衡因子
    14.  
    15. 	AVLTreeNode(const pair& kv)
    16. 		:_left(nullptr)
    17. 		,_right(nullptr)
    18. 		,_parent(nullptr)
    19. 		,_kv(kv)
    20. 		, _bf(0)
    21. 	{}
    22.  
    23. };
    24.  
    25.  
    26. template<class K,class V>
    27. class AVLTree
    28. {
    29. 	typedef struct AVLTreeNode Node;
    30. public:
    31. 	AVLTree()
    32. 		:_root(nullptr)
    33. 	{}
    34.  
    35.  
    36. 	bool insert(const pair& kv)
    37. 	{
    38. 		//1.插入数据，和搜索二叉树一样，先插入数据
    39.  
    40. 		if (_root == nullptr)
    41. 		{
    42. 			_root = new Node(kv);
    43. 			return true;
    44. 		}
    45.  
    46. 		Node*cur = _root;
    47. 		Node*parent = nullptr;
    48. 		while (cur)
    49. 		{
    50. 			if (cur->_kv.first > kv.first)
    51. 			{
    52. 				parent = cur;
    53. 				cur = cur->_left;
    54. 			}
    55. 			else if (cur->_kv.first < kv.first)
    56. 			{
    57. 				parent = cur;
    58. 				cur = cur->_right;
    59. 			}
    60. 			else
    61. 			{
    62. 				//有这个结点之后，就去重了
    63. 				return false;
    64. 			}
    65. 		}
    66. 		//没有这个结点
    67. 		cur = new Node(kv);
    68. 		if (parent->_kv.first > kv.first)
    69. 		{
    70. 			parent->_left = cur;
    71. 			cur->_parent = parent;
    72. 		}
    73. 		else 
    74. 		{
    75. 			parent->_right = cur;
    76. 			cur->_parent = parent;
    77. 		}
    78.  
    79. 		//2.控制平衡
    80. 		//   1.更新平衡因子
    81. 		//   2.出现异常平衡因子，那么需要旋转平衡处理
    82.  
    83. 		while (parent) //判断条件是根结点的_parent 为nullptr
    84. 		{
    85. 			//更新平衡因子
    86. 			if (parent->_left == cur)
    87. 			{
    88. 				parent->_bf--;
    89. 			}
    90. 			else 
    91. 			{
    92. 				parent->_bf++;
    93. 			}
    94. 			//根据平衡因子判断是旋转还是继续更新平衡因子
    95. 			if (parent->_bf==1 || parent->_bf==-1)
    96. 			{
    97. 				//子树变成了1或-1，需要继续向上更新
    98. 				cur = parent;
    99. 				parent = parent->_parent;
    100. 			}
    101. 			else if (parent->_bf == -2 || parent->_bf == 2)
    102. 			{
    103. 				//此时需要进行旋转了。
    104. 				if (parent->_bf == -2 && cur->_bf == -1)//向右单旋的条件
    105. 				{
    106. 					RoateR(parent);
    107. 				}
    108. 				else if (parent->_bf==2 && cur->_bf ==1)//向左单旋的条件
    109. 				{
    110. 					RoateL(parent);
    111. 				}
    112. 				else if (parent->_bf==-2 && cur->_bf==1)//左右旋的条件
    113. 				{
    114. 					RoateLR(parent);
    115. 				}
    116. 				else if (parent->_bf == 2 && cur->_bf == -1)//右左旋的条件
    117. 				{
    118. 					RoateRL(parent);
    119. 				}
    120.  
    121. 				break;//旋转完，就结束了，树已经平衡了
    122. 			}
    123. 			else
    124. 			{
    125. 				//这里说明上一次平衡因子出现了问题，不出问题不会到这里
    126. 				assert(false); //出现问题了。
    127. 			}
    128.  
    129. 		}
    130. 		return true;
    131.  
    132. 	}
    133.  
    134.  
    135. 	void RoateR(Node*parent)//右单旋
    136. 	{
    137. 		Node*subL = parent->_left;
    138. 		Node*subLR = subL->_right;
    139. 		
    140. 		parent->_left = subLR;
    141. 		if (subLR) //subL右边可能为空
    142. 			subLR->_parent = parent;
    143.  
    144. 		subL->_right = parent;
    145. 		Node*parentPrev = parent->_parent; //记录parent的上一个结点
    146. 		parent->_parent = subL;
    147. 		if (parent == _root) //若parent是根节点
    148. 		{
    149. 			_root = subL;
    150. 			subL->_parent = nullptr;
    151. 		}
    152. 		else //若不是根,而是子树
    153. 		{
    154. 			if (parentPrev->_left == parent)//是左边子树
    155. 			{
    156. 				parentPrev->_left = subL;
    157. 			}//是右边子树
    158. 			else
    159. 			{
    160. 				parentPrev->_right = subL;
    161. 			}
    162. 			subL->_parent = parentPrev;
    163. 		}
    164. 		parent->_bf = subL->_bf = 0;//更新一下平衡因子
    165. 	}
    166.  
    167.  
    168. 	void RoateL(Node*parent)//左单旋
    169. 	{
    170. 		Node* subR = parent->_right;
    171. 		Node*subRL = subR->_left;
    172.  
    173. 		parent->_right = subRL;
    174. 		if (subRL) //subRL有可能为空
    175. 			subRL->_parent = parent;
    176. 		subR->_left = parent;
    177.  
    178. 		Node*parentPrev = parent->_parent;
    179. 		parent->_parent = subR;
    180.  
    181. 		if (_root==parent)//如果是根节点
    182. 		{
    183. 			_root = subR;
    184. 			subR->_parent = nullptr;
    185. 		}
    186. 		else
    187. 		{
    188. 			if (parentPrev->_left==parent)
    189. 			{
    190. 				parentPrev->_left = subR;
    191. 			}
    192. 			else
    193. 			{
    194. 				parentPrev->_right = subR;
    195. 			}
    196. 			subR->_parent = parentPrev;
    197. 		}
    198. 		subR->_bf = parent->_bf = 0;//更新平衡因子
    199. 	}
    200.  
    201.  
    202. 	void RoateLR(Node*parent)//左右旋
    203. 	{
    204. 		//保存好2个结点的指针
    205. 		Node* subL = parent->_left;
    206. 		Node*subLR = subL->_right;
    207. 		int bf = subL->_bf;
    208.  
    209. 		RoateL(parent->_left);//先进行左单旋
    210. 		RoateR(parent);//在进行右单旋
    211. 		//if (bf==1)
    212. 		//{
    213. 		//	subL->_bf = -1;
    214. 		//	parent->_bf = 0;
    215. 		//	subLR->_bf = 0;
    216. 		//}
    217. 		//else if (bf==-1)
    218. 		//{
    219. 		//	subL->_bf = 0;
    220. 		//	parent->_bf = 1;
    221. 		//	subLR->_bf = 0;
    222. 		//}
    223. 		//else if (bf==0)
    224. 		//{
    225. 		//	subL->_bf = 0;
    226. 		//	parent->_bf =0;
    227. 		//	subLR->_bf = 0;
    228. 		//}
    229. 		//else
    230. 		//{
    231. 		//	//这里就是出错了
    232. 		//	assert(false);
    233. 		//}
    234. 	}
    235.  
    236. 	void RoateRL(Node*parent)//右左旋
    237. 	{
    238. 		Node* subR = parent->_right;
    239. 		Node* subRL = subR->_left;
    240. 		int bf = subRL->_bf;
    241. 	
    242. 		RoateR(parent->_right);//先进行右单旋
    243. 		RoateL(parent);//在进行左单旋
    244. 		//if (bf == 1)
    245. 		//{
    246. 		//	subRL->_bf = subR->_bf = 0;
    247. 		//	parent->_bf = -1;
    248. 		//}
    249. 		//else if (bf=-1)
    250. 		//{
    251. 		//	subRL->_bf = parent->_bf = 0;
    252. 		//	subR->_bf = 1;
    253. 		//}
    254. 		//else if (bf == 0)
    255. 		//{
    256. 		//	subRL->_bf = subR->_bf = parent->_bf = 0;
    257. 		//}
    258. 		//else
    259. 		//{
    260. 		//	//这里是不可能到达的。
    261. 		//	assert(false);
    262. 		//}
    263. 	}
    264.  
    265. 	void Inorder()
    266. 	{
    267. 		_Inorder(_root);
    268. 	}
    269.  
    270. 	void _Inorder(Node* root)//中序遍历
    271. 	{
    272. 		if (root == nullptr)
    273. 			return;
    274. 		_Inorder(root->_left);
    275. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
    276. 		_Inorder(root->_right);
    277. 	}
    278.  
    279.  
    280. private:
    281. 	Node* _root;
    282. };

    5.AVL树调试

    1.中序遍历只是检查是否为搜索二叉树，没办法检查是否为平衡二叉树。

    1. void Inorder()
    2. 	{
    3. 		_Inorder(_root);
    4. 	}
    5.  
    6. 	void _Inorder(Node* root)//中序遍历
    7. 	{
    8. 		if (root == nullptr)
    9. 			return;
    10. 		_Inorder(root->_left);
    11. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
    12. 		_Inorder(root->_right);
    13. 	}

    2.检查高度，仅检查高度是不行的，有可能平衡因子有问题。

    1. 	int TreeHigh(Node*root)
    2. 	{
    3. 		if (root == nullptr)
    4. 			return 0;
    5. 		int left_high = TreeHigh(root->_left);
    6. 		int right_high = TreeHigh(root->_right);
    7. 	
    8. 		return left_high > right_high ? left_high + 1 : right_high + 1;
    9. 	}
    10.  
    11. 	bool IsBanlance()
    12. 	{
    13. 		return  _IsBanlance(_root);
    14. 	}
    15.  
    16. 	bool _IsBanlance(Node*root)
    17. 	{
    18. 		if (root==nullptr)
    19. 		{
    20. 			return true;
    21. 		}
    22. 		int left_high = TreeHigh(root->_left);
    23. 		int right_high = TreeHigh(root->_right);
    24. 		//平衡因子有异常
    25. 		if (right_high - left_high != root->_bf)
    26. 		{
    27. 			cout << root->_kv.first << "现在是:" << root->_bf << endl;
    28. 			cout << root->_kv.first << "应该是:" << right_high - left_high << endl;
    29. 			return false;
    30. 		}
    31. 		return abs(left_high - right_high)< 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);
    32. 	}

    测试代码：在插入的时候顺便检查一下平衡因子

    1. #include"AVLTreeNode.h"
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.  
    7. 	//int a[] = { 5, 4, 3, 2, 1 ,0};
    8. 	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    9. 	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    10. 	AVLTree<int, int> AVL;
    11. 	for (auto&e :a)
    12. 	{
    13. 		AVL.insert(make_pair(e,e));
    14. 		cout << "insert"<":"<IsBanlance() << endl;
    15. 	}
    16. 	AVL.Inorder();
    17. 	
    18.  
    19. 	return 0;
    20. }

    是在插入14的时候出现了问题： 

     因此对照插入数据，进行画图分析，怎么错了。就能找到问题所在。

    6.分析平衡因子

    1.左右旋的平衡因子分析

    所以我们需要把平衡因子修改对，对于平衡因子的分析：

    第一种情况：

    第二种情况： 

    第三种情况： 

    因此代码左右旋的正确代码：

    1. 	void RoateLR(Node*parent)//左右旋
    2. 	{
    3. 		//保存好2个结点的指针
    4. 		Node* subL = parent->_left;
    5. 		Node*subLR = subL->_right;
    6. 		int bf = subL->_bf;
    7.  
    8. 		RoateL(parent->_left);//先进行左单旋
    9. 		RoateR(parent);//在进行右单旋
    10.         //从新更新一下平衡因子
    11. 		if (bf==1)
    12. 		{
    13. 			subL->_bf = -1;
    14. 			parent->_bf = 0;
    15. 			subLR->_bf = 0;
    16. 		}
    17. 		else if (bf==-1)
    18. 		{
    19. 			subL->_bf = 0;
    20. 			parent->_bf = 1;
    21. 			subLR->_bf = 0;
    22. 		}
    23. 		else if (bf==0)
    24. 		{
    25. 			subL->_bf = 0;
    26. 			parent->_bf =0;
    27. 			subLR->_bf = 0;
    28. 		}
    29. 		else
    30. 		{
    31. 			//这里就是出错了
    32. 			assert(false);
    33. 		}
    34. 	}

    2.右左旋的平衡因子分析

    第一种情况：

    第二种情况：

    第三种情况：60本身这个结点就是新增结点，也就是h==0

     因此右左旋代码实现：

    1. 	void RoateRL(Node*parent)//右左旋
    2. 	{
    3. 		Node* subR = parent->_right;
    4. 		Node* sunRL = subR->_left;
    5. 		int bf = subRL->_bf; //提前保存好结点的平衡因子
    6. 	
    7. 		RoateR(parent->_right);//先进行右单旋
    8. 		RoateL(parent);//在进行左单旋
    9.         //更新平衡因子
    10. 		if (bf == 1)
    11. 		{
    12. 			subRL->_bf = subR->_bf = 0;
    13. 			parent->_bf = -1;
    14. 		}
    15. 		else if (bf==-1)
    16. 		{
    17. 			subRL->_bf = parent->_bf = 0;
    18. 			subR->_bf = 1;
    19. 		}
    20. 		else if (bf == 0)//别忘了这种情况
    21. 		{
    22. 			subRL->_bf = subR->_bf = parent->_bf = 0;
    23. 		}
    24. 		else //平衡因子出现问题
    25. 		{
    26. 			//这里是不可能到达的。
    27.             //说明上一次插入已经出现错误了
    28. 			assert(false);
    29. 		}
    30. 	}

    都分析完成后，所有的代码：

    AVLTreeNode.h

    1. #include
    2. #include
    3. using namespace std;
    4. #include
    5. template<class K,class V>
    6. struct AVLTreeNode
    7. {
    8. 	//3叉链
    9. 	AVLTreeNode* _left;
    10. 	AVLTreeNode* _right;
    11. 	AVLTreeNode* _parent;
    12. 	pair _kv;
    13. 	int _bf;//平衡因子
    14.  
    15. 	AVLTreeNode(const pair& kv)
    16. 		:_left(nullptr)
    17. 		,_right(nullptr)
    18. 		,_parent(nullptr)
    19. 		,_kv(kv)
    20. 		, _bf(0)
    21. 	{}
    22.  
    23. };
    24.  
    25.  
    26. template<class K,class V>
    27. class AVLTree
    28. {
    29. 	typedef struct AVLTreeNode Node;
    30. public:
    31. 	AVLTree()
    32. 		:_root(nullptr)
    33. 	{}
    34.  
    35.  
    36. 	bool insert(const pair& kv)
    37. 	{
    38. 		//1.插入数据，和搜索二叉树一样，先插入数据
    39.  
    40. 		if (_root == nullptr)
    41. 		{
    42. 			_root = new Node(kv);
    43. 			return true;
    44. 		}
    45.  
    46. 		Node*cur = _root;
    47. 		Node*parent = nullptr;
    48. 		while (cur)
    49. 		{
    50. 			if (cur->_kv.first > kv.first)
    51. 			{
    52. 				parent = cur;
    53. 				cur = cur->_left;
    54. 			}
    55. 			else if (cur->_kv.first < kv.first)
    56. 			{
    57. 				parent = cur;
    58. 				cur = cur->_right;
    59. 			}
    60. 			else
    61. 			{
    62. 				//有这个结点之后，就去重了
    63. 				return false;
    64. 			}
    65. 		}
    66. 		//没有这个结点
    67. 		cur = new Node(kv);
    68. 		if (parent->_kv.first > kv.first)
    69. 		{
    70. 			parent->_left = cur;
    71. 			cur->_parent = parent;
    72. 		}
    73. 		else 
    74. 		{
    75. 			parent->_right = cur;
    76. 			cur->_parent = parent;
    77. 		}
    78.  
    79. 		//2.控制平衡
    80. 		//   1.更新平衡因子
    81. 		//   2.出现异常平衡因子，那么需要旋转平衡处理
    82.  
    83. 		while (parent) //判断条件是根结点的_parent 为nullptr
    84. 		{
    85. 			//更新平衡因子
    86. 			if (parent->_left == cur)
    87. 			{
    88. 				parent->_bf--;
    89. 			}
    90. 			else 
    91. 			{
    92. 				parent->_bf++;
    93. 			}
    94.  
    95. 			if (parent->_bf==0)
    96. 			{
    97. 				break;
    98. 			}
    99. 			//根据平衡因子判断是旋转还是继续更新平衡因子
    100. 			else if (parent->_bf==1 || parent->_bf==-1)
    101. 			{
    102. 				//子树变成了1或-1，需要继续向上更新
    103. 				cur = parent;
    104. 				parent = parent->_parent;
    105. 			}
    106. 			else if (parent->_bf == -2 || parent->_bf == 2)
    107. 			{
    108. 				//此时需要进行旋转了。
    109. 				if (parent->_bf == -2 && cur->_bf == -1)//向右单旋的条件
    110. 				{
    111. 					RoateR(parent);
    112. 				}
    113. 				else if (parent->_bf==2 && cur->_bf ==1)//向左单旋的条件
    114. 				{
    115. 					RoateL(parent);
    116. 				}
    117. 				else if (parent->_bf==-2 && cur->_bf==1)//左右旋的条件
    118. 				{
    119. 					RoateLR(parent);
    120. 				}
    121. 				else if (parent->_bf == 2 && cur->_bf == -1)//右左旋的条件
    122. 				{
    123. 					RoateRL(parent);
    124. 				}
    125.  
    126. 				break;//旋转完，就结束了，树已经平衡了
    127. 			}
    128. 			else
    129. 			{
    130. 				//这里说明上一次平衡因子出现了问题，不出问题不会到这里
    131. 				assert(false); //出现问题了。
    132. 			}
    133.  
    134. 		}
    135. 		return true;
    136.  
    137. 	}
    138.  
    139.  
    140. 	void RoateR(Node*parent)//右单旋
    141. 	{
    142. 		Node*subL = parent->_left;
    143. 		Node*subLR = subL->_right;
    144. 		
    145. 		parent->_left = subLR;
    146. 		if (subLR) //subL右边可能为空
    147. 			subLR->_parent = parent;
    148.  
    149. 		subL->_right = parent;
    150. 		Node*parentPrev = parent->_parent; //记录parent的上一个结点
    151. 		parent->_parent = subL;
    152. 		if (parent == _root) //若parent是根节点
    153. 		{
    154. 			_root = subL;
    155. 			subL->_parent = nullptr;
    156. 		}
    157. 		else //若不是根,而是子树
    158. 		{
    159. 			if (parentPrev->_left == parent)//是左边子树
    160. 			{
    161. 				parentPrev->_left = subL;
    162. 			}//是右边子树
    163. 			else
    164. 			{
    165. 				parentPrev->_right = subL;
    166. 			}
    167. 			subL->_parent = parentPrev;
    168. 		}
    169. 		parent->_bf = subL->_bf = 0;//更新一下平衡因子
    170. 	}
    171.  
    172.  
    173. 	void RoateL(Node*parent)//左单旋
    174. 	{
    175. 		Node* subR = parent->_right;
    176. 		Node*subRL = subR->_left;
    177.  
    178. 		parent->_right = subRL;
    179. 		if (subRL) //subRL有可能为空
    180. 			subRL->_parent = parent;
    181. 		subR->_left = parent;
    182.  
    183. 		Node*parentPrev = parent->_parent;
    184. 		parent->_parent = subR;
    185.  
    186. 		if (_root==parent)//如果是根节点
    187. 		{
    188. 			_root = subR;
    189. 			subR->_parent = nullptr;
    190. 		}
    191. 		else
    192. 		{
    193. 			if (parentPrev->_left==parent)
    194. 			{
    195. 				parentPrev->_left = subR;
    196. 			}
    197. 			else
    198. 			{
    199. 				parentPrev->_right = subR;
    200. 			}
    201. 			subR->_parent = parentPrev;
    202. 		}
    203. 		subR->_bf = parent->_bf = 0;//更新平衡因子
    204. 	}
    205.  
    206.  
    207. 	void RoateLR(Node*parent)//左右旋
    208. 	{
    209. 		//保存好2个结点的指针
    210. 		Node* subL = parent->_left;
    211. 		Node*subLR = subL->_right;
    212. 		int bf = subLR->_bf;
    213.  
    214. 		RoateL(parent->_left);//先进行左单旋
    215. 		RoateR(parent);//在进行右单旋
    216. 		if (bf==1)
    217. 		{
    218. 			subL->_bf = -1;
    219. 			parent->_bf = 0;
    220. 			subLR->_bf = 0;
    221. 		}
    222. 		else if (bf==-1)
    223. 		{
    224. 			subL->_bf = 0;
    225. 			parent->_bf = 1;
    226. 			subLR->_bf = 0;
    227. 		}
    228. 		else if (bf==0)
    229. 		{
    230. 			subL->_bf = 0;
    231. 			parent->_bf =0;
    232. 			subLR->_bf = 0;
    233. 		}
    234. 		else
    235. 		{
    236. 			//这里就是出错了
    237. 			assert(false);
    238. 		}
    239. 	}
    240.  
    241. 	void RoateRL(Node*parent)//右左旋
    242. 	{
    243. 		Node* subR = parent->_right;
    244. 		Node* subRL = subR->_left;
    245. 		int bf = subRL->_bf;
    246. 	
    247. 		RoateR(parent->_right);//先进行右单旋
    248. 		RoateL(parent);//在进行左单旋
    249. 		if (bf == 1)
    250. 		{
    251. 			subRL->_bf = subR->_bf = 0;
    252. 			parent->_bf = -1;
    253. 		}
    254. 		else if (bf==-1)
    255. 		{
    256. 			subRL->_bf = parent->_bf = 0;
    257. 			subR->_bf = 1;
    258. 		}
    259. 		else if (bf == 0)
    260. 		{
    261. 			subRL->_bf = subR->_bf = parent->_bf = 0;
    262. 		}
    263. 		else
    264. 		{
    265. 			//这里是不可能到达的。
    266. 			assert(false);
    267. 		}
    268. 	}
    269.  
    270. 	void Inorder()
    271. 	{
    272. 		_Inorder(_root);
    273. 	}
    274.  
    275. 	void _Inorder(Node* root)//中序遍历
    276. 	{
    277. 		if (root == nullptr)
    278. 			return;
    279. 		_Inorder(root->_left);
    280. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
    281. 		_Inorder(root->_right);
    282. 	}
    283.  
    284. 	int TreeHigh(Node*root)
    285. 	{
    286. 		if (root == nullptr)
    287. 			return 0;
    288. 		int left_high = TreeHigh(root->_left);
    289. 		int right_high = TreeHigh(root->_right);
    290. 	
    291. 		return left_high > right_high ? left_high + 1 : right_high + 1;
    292. 	}
    293.  
    294. 	bool IsBanlance()
    295. 	{
    296. 		return  _IsBanlance(_root);
    297. 	}
    298.  
    299. 	bool _IsBanlance(Node*root)
    300. 	{
    301. 		if (root==nullptr)
    302. 		{
    303. 			return true;
    304. 		}
    305. 		int left_high = TreeHigh(root->_left);
    306. 		int right_high = TreeHigh(root->_right);
    307. 		//平衡因子有异常
    308. 		if (right_high - left_high != root->_bf)
    309. 		{
    310. 			cout << root->_kv.first << "现在是:" << root->_bf << endl;
    311. 			cout << root->_kv.first << "应该是:" << right_high - left_high << endl;
    312. 			return false;
    313. 		}
    314. 		return abs(left_high - right_high)< 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);
    315. 	}
    316.  
    317. private:
    318. 	Node* _root;
    319. };

    main.cpp

    1. #include"AVLTreeNode.h"
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.  
    7. 	//int a[] = { 5, 4, 3, 2, 1 ,0};
    8. 	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    9. 	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    10. 	AVLTree<int, int> AVL;
    11. 	for (auto&e :a)
    12. 	{
    13. 		AVL.insert(make_pair(e,e));
    14. 		cout << "insert"<":"<IsBanlance() << endl;
    15. 	}
    16. 	AVL.Inorder();
    17. 	
    18.  
    19. 	return 0;
    20. }

    测试结果：3个用例，没问题。

    AVL树的性能：AVL树是一颗绝对平衡的二叉树，其要求每个节点的左右子树高度差的绝对值不超过1，这样可以保证查询时高效的时间复杂度，即{\log _2}N\

    5.红黑树

    5.1红黑树的概念

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

    5.2红黑树的性质

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

    2.根结点是黑色

    3.如果一个结点是红色，则它的两个孩子结点是黑色的。(没有连续的红色结点)

    4.每条路径上所包含的黑色结点数目是一样多的。

    5.每个叶子结点都是黑色的(此处的叶子结点指的是空节点，即NIL 都是黑色的) 。但是这个黑色结点可以不算，不用管就是了。

    以上的前4个红黑树性质，确定了最长路径不超过最短路径的2倍，从NIL开始到根节点代表一条路径。下图一共10条路径。

    通过下图理解为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍。

    最短路径：全黑

    最长路径：一黑一红

    假设每条路径黑节点的数量是N，  N<=任意路径长度<=2N

    红黑树复杂度分析：

    红黑树是近似平衡与AVL树完全平衡相比，AVL树的复杂度是{\log _2}N\，比红黑树效率高，但是它需要大量的旋转才能达到平衡付出代价很大，所以红黑树更吃香。

    5.3红黑树的实现

    1.红黑树的基本框架

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. enum color
    6. {
    7. 	RED,
    8. 	BLACK
    9. };
    10.  
    11.  
    12. template<class K,class V>
    13. struct RBtreeNode
    14. {
    15. 	RBtreeNode* _left;
    16. 	RBtreeNode* _right;
    17. 	RBtreeNode* _parent;
    18. 	pair _kv;
    19. 	color _col;
    20.  
    21. 	RBtreeNode(const pair& kv)
    22. 		:_left(nullptr)
    23. 		, _right(nullptr)
    24. 		, _parent(nullptr)
    25. 		, _kv(kv)
    26. 		, _col(RED)
    27. 	{}
    28. };
    29.  
    30. template<class K,class V>
    31. class RBTtree 
    32. {
    33. 	typedef RBtreeNode Node;
    34. public:
    35. 	RBTtree()
    36. 		:_root(nullptr)
    37. 	{}
    38. //这里增加成员函数
    39.  
    40. private:
    41. 	Node* _root;
    42. };

    2.insert函数

    思考一个问题：在插入节点时，是插入红色的节点还是黑色的。答案：红色的，若是插入黑色的，根据红黑树的定义，每条路径上所包含相同数目的黑色节点，若是插入黑色节点，那么将会对整棵树产生影响，反而插入红色节点，最差只会影响这一条路径上的，最好不影响。

    这里的插入节点和前面的平衡二叉树是一样的，旋转也一样，只是不更新平衡因子。不同的是控制上的不同，所以只介绍控制。

    以下分析都是分析的左边插入节点，右边插入就是相反了。

    情况1：只是变色

    情况2：单旋

    情况3：

    红黑树insert代码：

    1. bool insert(const pair& kv)
    2. 	{
    3. 		//
    4. 		if (_root == nullptr)
    5. 		{
    6. 			_root = new Node(kv);
    7. 			_root->_col = BLACK;
    8. 			return true;
    9. 		}
    10. 		Node* cur = _root;
    11. 		Node* parent = nullptr;
    12.  
    13. 		while (cur)
    14. 		{
    15. 			if (cur->_kv.first > kv.first)
    16. 			{
    17. 				parent = cur;
    18. 				cur = cur->_left;
    19. 			}
    20. 			else if (cur->_kv.first < kv.first)
    21. 			{
    22. 				parent = cur;
    23. 				cur = cur->_right;
    24. 			}
    25. 			else
    26. 			{
    27. 				return false;
    28. 			}
    29. 		}
    30. 		cur = new Node(kv);
    31. 		cur->_col = RED;//把结点以红色插入
    32. 		if (parent->_kv.first < kv.first)
    33. 		{
    34. 			parent->_right = cur;
    35. 			cur->_parent = parent;
    36. 		}
    37. 		else 
    38. 		{
    39. 			parent->_left = cur;
    40. 			cur->_parent = parent;
    41. 		}
    42.  
    43. 		//进行红黑树的控制
    44. 		while (parent && parent->_col==RED)//父节点位黑或者不存在就结束了
    45. 		{
    46. 			Node*gradparent = parent->_parent; //这里的祖父一定是存在的，因为parent->_col==RED，所以parent不可能是根节点
    47. 			if (gradparent->_left==parent)//在左边进行插入的
    48. 			{
    49. 				Node* uncle = gradparent->_right;
    50. 				if (uncle && uncle->_col == RED)//u存在且为红色,情况1
    51. 				{
    52. 					uncle->_col = BLACK;
    53. 					parent->_col = BLACK;
    54. 					gradparent->_col = RED;
    55. 					cur = gradparent;//把祖父当成新增结点
    56. 					parent = cur->_parent;
    57. 				}
    58. 				else //u不存在或为黑   
    59. 				{
    60. 					if (parent->_left==cur) //在parent插入左边插入节点，情况2
    61. 					{
    62. 						//单旋
    63. 						//   g
    64. 						// p   u(存在为黑，或不存在)
    65. 					//    c
    66. 						RoateR(gradparent);
    67. 						gradparent->_col = RED;
    68. 						parent->_col = BLACK;
    69. 					}
    70. 					else //在parent的右边插入节点 ，情况3
    71. 					{
    72. 						//双旋
    73. 						//   g
    74. 						// p   u
    75. 						//  c
    76. 						RoateL(parent);
    77. 						RoateR(gradparent);
    78. 						cur->_col = BLACK;
    79. 						gradparent->_col = RED;
    80. 					}
    81. 					break;
    82.  
    83. 				}
    84. 			}
    85. 			else //gradparent->_left==parent，在树的右边插入了节点
    86. 			{
    87. 				
    88. 				Node*uncle = gradparent->_left;
    89. 				if (uncle && uncle->_col==RED)//情况1  u存在且为红
    90. 				{
    91. 					parent->_col = BLACK;
    92. 					uncle->_col = BLACK;
    93. 					gradparent->_col = RED;
    94. 					cur = gradparent;
    95. 					parent = cur->_parent;
    96. 				}
    97. 				else //u不存在或着u为黑
    98. 				{
    99. 					// g
    100. 					//u  p
    101. 					//     cur
    102. 					if (parent->_right == cur)//情况2
    103. 					{
    104. 						//进行左单旋
    105. 						RoateL(gradparent);
    106. 						parent->_col = BLACK;
    107. 						gradparent->_col = RED;
    108. 					}
    109. 					//  g
    110. 					//u   p
    111. 					//   c
    112. 					else //情况3
    113. 					{
    114. 						//双旋
    115. 						RoateR(parent);
    116. 						RoateL(gradparent);
    117. 						cur->_col = BLACK;
    118. 						gradparent->_col = RED;
    119. 					}
    120. 					break;
    121. 				}
    122. 			}
    123. 		}
    124. 		_root->_col = BLACK;//不管是子树还是根节点都需要是黑色
    125. 		return true;
    126. 	}

    测试代码：使用中序只能证明是搜索二叉树。

    1. #include"RBTree.h"
    2. int main()
    3. {
    4. 	//int a[] = { 5, 4, 3, 2, 1 ,0};
    5. 	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    6. 	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    7.  
    8. 	RBTtree<int, int> t;
    9. 	for (auto e : a)
    10. 	{
    11. 		t.insert(make_pair(e,e));
    12. 	}
    13. 	t.Inoder();
    14.  
    15. 	return 0;
    16. }

    那如何证明是红黑树呢？

    主要是检验性质3和4。

    注意这里检查是否存在连续红色节点的时候，去检查红色节点的父亲节点。

    这里检查每条路径上的黑色节点是否一样，需要选取一个基准值，这里选的树的最左边那条路径。

    1. bool IsBanlance()
    2. 	{
    3. 		if (_root && _root->_col == RED) //检查根节点是不是黑色的
    4. 		{
    5. 			cout << "根节点不是黑色" << endl;
    6. 			return false;
    7. 		}
    8.  
    9. 		int benchmark = 0;  //取一个路径上黑色节点的数量作为基准值
    10. 		Node* cur = _root;
    11. 		while (cur)//这里取的最左路径为基准，以方便检验黑色节点的数量
    12. 		{
    13. 			if (cur->_col == BLACK)
    14. 			{
    15. 				benchmark++;
    16. 			}
    17. 			cur = cur->_left;
    18. 		}
    19. 		int BlackCount = 0;
    20. 			
    21. 		return _IsBanlance(_root, benchmark, BlackCount);
    22. 	}
    23. 	bool _IsBanlance(Node* root, int benchmark, int BlackCount)
    24. 	{
    25. 		if (root == nullptr)
    26. 		{
    27. 			//检查每一条黑色节点数量
    28. 			if (BlackCount != benchmark)
    29. 			{
    30. 				cout << "路径黑色节点不一样" << endl;
    31. 				return false;
    32. 			}
    33. 			return true;
    34. 		}
    35. 		//这里不去检查孩子节点，而是检查父亲节点，检查孩子太麻烦了，情况比较多
    36. 		if (root->_col==RED && root->_parent->_col==RED) //root->_col==RED 一定存在父节点，因为根黑色的
    37. 		{
    38. 			cout << "连续的红节点" << endl;
    39. 			return false;
    40. 		}
    41. 		if (root->_col == BLACK)
    42. 		{
    43. 			BlackCount++;
    44. 		}
    45.  
    46. 		
    47. 		return _IsBanlance(root->_left, benchmark, BlackCount) && _IsBanlance(root->_right, benchmark, BlackCount);
    48. 	}

    测试代码：

    RBTree.h

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5.  
    6. enum color
    7. {
    8. 	RED,
    9. 	BLACK
    10. };
    11.  
    12.  
    13. template<class K,class V>
    14. struct RBtreeNode
    15. {
    16. 	RBtreeNode* _left;
    17. 	RBtreeNode* _right;
    18. 	RBtreeNode* _parent;
    19. 	pair _kv;
    20. 	color _col;
    21.  
    22. 	RBtreeNode(const pair& kv)
    23. 		:_left(nullptr)
    24. 		, _right(nullptr)
    25. 		, _parent(nullptr)
    26. 		, _kv(kv)
    27. 		, _col(RED)
    28. 	{}
    29. };
    30.  
    31. template<class K,class V>
    32. class RBTtree 
    33. {
    34. 	typedef RBtreeNode Node;
    35. public:
    36. 	RBTtree()
    37. 		:_root(nullptr)
    38. 	{}
    39.  
    40. 	void RoateR(Node*parent)
    41. 	{
    42. 		Node*subL = parent->_left;
    43. 		Node* subLR = subL->_right;
    44.  
    45. 		parent->_left = subL->_right;
    46. 		if (subLR)
    47. 			subLR->_parent = parent;
    48. 		subL->_right = parent;
    49. 		Node*prevparent = parent->_parent;
    50. 		parent->_parent = subL;
    51. 		if (parent == _root)
    52. 		{
    53. 			_root = subL;
    54. 			subL->_parent = nullptr;
    55. 		}
    56. 		else if (prevparent->_left==parent)
    57. 		{
    58. 			prevparent->_left = subL;
    59. 			subL->_parent = prevparent;
    60. 		}
    61. 		else if (prevparent->_right==parent)
    62. 		{
    63. 			prevparent->_right = subL;
    64. 			subL->_parent = prevparent;
    65. 		}
    66. 		else
    67. 		{
    68. 			assert(false);
    69. 		}
    70. 	}
    71.  
    72.  
    73. 	void RoateL(Node* parent)
    74. 	{
    75. 		Node*subR = parent->_right;
    76. 		Node*subRL = subR->_left;
    77. 		parent->_right = subRL;
    78. 		if (subRL)
    79. 		{
    80. 			subRL->_parent = parent;
    81. 		}
    82. 		subR->_left = parent;
    83. 		Node*prevparent = parent->_parent;
    84. 		parent->_parent = subR;
    85. 		if (parent==_root)
    86. 		{
    87. 			_root = subR;
    88. 			subR->_parent = nullptr;
    89. 		}
    90. 		else if (prevparent->_left == parent)
    91. 		{
    92. 			prevparent->_left = subR;
    93. 			subR->_parent = prevparent;
    94. 		}
    95. 		else if (prevparent->_right == parent)
    96. 		{
    97. 			prevparent->_right = subR;
    98. 			subR->_parent = prevparent;
    99. 		}
    100. 		else
    101. 		{
    102. 			assert(false);
    103. 		}
    104. 	}
    105.  
    106.  
    107. 	bool insert(const pair& kv)
    108. 	{
    109. 		//
    110. 		if (_root == nullptr)
    111. 		{
    112. 			_root = new Node(kv);
    113. 			_root->_col = BLACK;
    114. 			return true;
    115. 		}
    116. 		Node* cur = _root;
    117. 		Node* parent = nullptr;
    118.  
    119. 		while (cur)
    120. 		{
    121. 			if (cur->_kv.first > kv.first)
    122. 			{
    123. 				parent = cur;
    124. 				cur = cur->_left;
    125. 			}
    126. 			else if (cur->_kv.first < kv.first)
    127. 			{
    128. 				parent = cur;
    129. 				cur = cur->_right;
    130. 			}
    131. 			else
    132. 			{
    133. 				return false;
    134. 			}
    135. 		}
    136. 		cur = new Node(kv);
    137. 		cur->_col = RED;//把结点以红色插入
    138. 		if (parent->_kv.first < kv.first)
    139. 		{
    140. 			parent->_right = cur;
    141. 			cur->_parent = parent;
    142. 		}
    143. 		else 
    144. 		{
    145. 			parent->_left = cur;
    146. 			cur->_parent = parent;
    147. 		}
    148.  
    149. 		//进行红黑树的控制
    150. 		while (parent && parent->_col==RED)//父节点位黑或者不存在就结束了
    151. 		{
    152. 			Node*gradparent = parent->_parent; //这里的祖父一定是存在的，因为parent->_col==RED，所以parent不可能是根节点
    153. 			if (gradparent->_left==parent)//在左边进行插入的
    154. 			{
    155. 				Node* uncle = gradparent->_right;
    156. 				if (uncle && uncle->_col == RED)//u存在且为红色,情况1
    157. 				{
    158. 					uncle->_col = BLACK;
    159. 					parent->_col = BLACK;
    160. 					gradparent->_col = RED;
    161. 					cur = gradparent;//把祖父当成新增结点
    162. 					parent = cur->_parent;
    163. 				}
    164. 				else //u不存在或为黑   
    165. 				{
    166. 					if (parent->_left==cur) //在parent插入左边插入节点，情况2
    167. 					{
    168. 						//单旋
    169. 						//   g
    170. 						// p   u(存在为黑，或不存在)
    171. 					//    c
    172. 						RoateR(gradparent);
    173. 						gradparent->_col = RED;
    174. 						parent->_col = BLACK;
    175. 					}
    176. 					else //在parent的右边插入节点 ，情况3
    177. 					{
    178. 						//双旋
    179. 						//   g
    180. 						// p   u
    181. 						//  c
    182. 						RoateL(parent);
    183. 						RoateR(gradparent);
    184. 						cur->_col = BLACK;
    185. 						gradparent->_col = RED;
    186. 					}
    187. 					break;
    188.  
    189. 				}
    190. 			}
    191. 			else //gradparent->_left==parent，在树的右边插入了节点
    192. 			{
    193. 				
    194. 				Node*uncle = gradparent->_left;
    195. 				if (uncle && uncle->_col==RED)//情况1  u存在且为红
    196. 				{
    197. 					parent->_col = BLACK;
    198. 					uncle->_col = BLACK;
    199. 					gradparent->_col = RED;
    200. 					cur = gradparent;
    201. 					parent = cur->_parent;
    202. 				}
    203. 				else //u不存在或着u为黑
    204. 				{
    205. 					// g
    206. 					//u  p
    207. 					//     cur
    208. 					if (parent->_right == cur)//情况2
    209. 					{
    210. 						//进行左单旋
    211. 						RoateL(gradparent);
    212. 						parent->_col = BLACK;
    213. 						gradparent->_col = RED;
    214. 					}
    215. 					//  g
    216. 					//u   p
    217. 					//   c
    218. 					else //情况3
    219. 					{
    220. 						//双旋
    221. 						RoateR(parent);
    222. 						RoateL(gradparent);
    223. 						cur->_col = BLACK;
    224. 						gradparent->_col = RED;
    225. 					}
    226. 					break;
    227. 				}
    228. 			}
    229. 		}
    230. 		_root->_col = BLACK;//不管是子树还是根节点都需要是黑色
    231. 		return true;
    232. 	}
    233.  
    234. 	//中序遍历
    235. 	void Inoder()
    236. 	{
    237. 		_Inoder(_root);
    238. 	}
    239. 	void _Inoder(Node* root)
    240. 	{
    241. 		if (root == nullptr)
    242. 			return;
    243. 		_Inoder(root->_left);
    244. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
    245. 		_Inoder(root->_right);
    246. 	}
    247.  
    248. 	bool IsBanlance()
    249. 	{
    250. 		if (_root && _root->_col == RED) //检查根节点是不是黑色的
    251. 		{
    252. 			cout << "根节点不是黑色" << endl;
    253. 			return false;
    254. 		}
    255.  
    256. 		int benchmark = 0;  //取一个路径上黑色节点的数量作为基准值
    257. 		Node* cur = _root;
    258. 		while (cur)//这里取的最左路径为基准
    259. 		{
    260. 			if (cur->_col == BLACK)
    261. 			{
    262. 				benchmark++;
    263. 			}
    264. 			cur = cur->_left;
    265. 		}
    266. 		int BlackCount = 0;
    267. 			
    268. 		return _IsBanlance(_root, benchmark, BlackCount);
    269. 	}
    270. 	bool _IsBanlance(Node* root, int benchmark, int BlackCount)
    271. 	{
    272. 		if (root == nullptr)
    273. 		{
    274. 			//检查每一条黑色节点数量
    275. 			if (BlackCount != benchmark)
    276. 			{
    277. 				cout << "路径黑色节点不一样" << endl;
    278. 				return false;
    279. 			}
    280. 			return true;
    281. 		}
    282. 		//这里不去检查孩子节点，而是检查父亲节点，检查孩子太麻烦了，情况比较多
    283. 		if (root->_col==RED && root->_parent->_col==RED) //root->_col==RED 一定存在父节点，因为根黑色的
    284. 		{
    285. 			cout << "连续的红节点" << endl;
    286. 			return false;
    287. 		}
    288. 		if (root->_col == BLACK)
    289. 		{
    290. 			BlackCount++;
    291. 		}
    292.  
    293. 		
    294. 		return _IsBanlance(root->_left, benchmark, BlackCount) && _IsBanlance(root->_right, benchmark, BlackCount);
    295. 	}
    296.  
    297. private:
    298. 	Node* _root;
    299. };

    main.cpp

    1. #include"RBTree.h"
    2. int main()
    3. {
    4. 	//int a[] = { 5, 4, 3, 2, 1 ,0};
    5. 	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    6. 	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    7.  
    8. 	RBTtree<int, int> t;
    9. 	for (auto e : a)
    10. 	{
    11. 		t.insert(make_pair(e,e));
    12. 		cout << "insert" << e << ":"<IsBanlance() << endl;
    13. 	}
    14. 	t.Inoder();
    15.  
    16. 	return 0;
    17. }

    也可以给随机值： 

    1. #include
    2. #include
    3. #include"RBTree.h"
    4. int main()
    5. {
    6. 	//int a[] = { 5, 4, 3, 2, 1 ,0};
    7. 	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    8. 	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    9. 	vector<int> v;
    10. 	srand(time(0));
    11. 	int N = 100000;
    12. 	for (int i = 0; i < N; i++)
    13. 	{
    14. 		v.push_back(rand()); //给随机值
    15. 	}
    16. 	RBTtree<int, int> t;
    17. 	for (auto e : v)
    18. 	{
    19. 		t.insert(make_pair(e,e));
    20. 		cout << "insert" << e << ":"<IsBanlance() << endl;
    21. 	}
    22.    // cout <
    23. 	t.Inoder();
    24.  
    25. 	return 0;
    26. }

    6.set和map的模拟实现

    1.set和map的模拟实现

    观察STL源码：stl_map.h , stl_set.h , stl_tree.h。

    set是key ,map是 pair

    为了实现红黑树既可以是pair，也可以是key，那就需要改进红黑树。

    这里最主要的是实现set和map共用一个红黑树：

    RBTree.h

    1. #pragma once
    2. #include
    3. namespace zcf{
    4.  
    5.  
    6. enum color
    7. {
    8. 	RED,
    9. 	BLACK
    10. };
    11.  
    12.  
    13. template<class T>//这里只需要一个模板参数，用于接受类型
    14. struct RBtreeNode
    15. {
    16. 	RBtreeNode* _left;
    17. 	RBtreeNode* _right;
    18. 	RBtreeNode* _parent;
    19. 	T _data;  //根据传入的模板参数来确定这里是pair还是key
    20. 	color _col;
    21.  
    22. 	RBtreeNode(const T& data)
    23. 		:_left(nullptr)
    24. 		, _right(nullptr)
    25. 		, _parent(nullptr)
    26. 		, _data(data)
    27. 		, _col(RED)
    28. 	{}
    29. };
    30.  
    31.  
    32. //迭代器
    33. template<class T, class Ref, class Ptr>
    34. struct RBTreeIterator
    35. {
    36. 	typedef RBTreeIterator Self;
    37. 	typedef RBtreeNode Node;
    38. 	Node* _node;
    39.  
    40. 	RBTreeIterator(Node* node)
    41. 		:_node(node)
    42. 	{}
    43.  
    44. 	Ref operator*()
    45. 	{
    46. 		return _node->_data;
    47. 	}
    48.  
    49. 	Ptr operator->()
    50. 	{
    51. 		return &(_node->_data);
    52. 	}
    53.  
    54. 	//前置++
    55. 	//当前结点的右子树不为空，那么就去找右子树的最左结点
    56. 	//当前结点的右子树为空：因为是中序遍历，++也要遵循中序
    57. 	//						1.如果当前结点是parent的左边，++就是parent
    58. 	//						2.如果当前结点是parent的右边，++就是当前结点的_parent,直到parent为空，或parent->_left==cur  
    59. 	Self&  operator++()
    60. 	{
    61. 		
    62. 		if(_node->_right) // 右子树不为空，那就是右子树的最左节点
    63. 		{
    64. 			Node* cur = _node->_right;
    65. 			while (cur->_left)
    66. 			{
    67. 				cur = cur->_left;
    68. 			}
    69. 			_node = cur;
    70. 		}
    71. 		else//右子树为空
    72. 		{
    73. 				Node*cur = _node;
    74. 				Node*parent = cur->_parent;
    75. 				while (parent &&  parent->_right==cur)
    76. 				{
    77. 					cur = cur->_parent;
    78. 					parent = parent->_parent;
    79. 				}
    80. 				//父亲的左节点为cur。
    81. 				//parent->_left==cur或parent==nullptr
    82. 				_node = parent;
    83. 		}
    84. 		return *this;
    85. 	}
    86.  
    87. 	//前置--   ,与++是相反的思想
    88. 	Self& operator--()
    89. 	{
    90. 		if (_node->_left)//左子树不为空，找最右节点
    91. 		{
    92. 			Node*cur = _node->_left;
    93. 			while (cur->_right)
    94. 			{
    95. 				cur = cur->_right;
    96. 			}
    97. 			_node = cur;
    98. 		}
    99. 		else//左子树为空
    100. 		{
    101. 			Node*cur = _node;
    102. 			Node*parent = cur->_parent;
    103. 			while (parent && parent->_left==cur)
    104. 			{
    105. 				cur = cur->_parent;
    106. 				parent = parent->_parent;
    107. 			}
    108. 			_node = parent;
    109.  
    110.  
    111. 		}
    112. 		return *this;
    113. 	}
    114. 	bool operator!=(const Self& s)
    115. 	{
    116. 		return _node != s._node;
    117. 	}
    118.  
    119. 	bool operator==(const Self& s)
    120. 	{
    121. 		return _node == s._node;
    122. 	}
    123.  
    124. };
    125.  
    126.  
    127.  
    128. template<class K,class T,class KeyOfT>//使用T来解决红黑树是key还是pair,
    129. //KeyOfT 来解决比较的问题，因为红黑树在比较的时候不知道是pair还是key,而map和set类中知道
    130. class RBTtree 
    131. {
    132. 	
    133. public:
    134. 	typedef RBTreeIterator< T, T&, T*> iterator;
    135. 	typedef RBTreeIterator< T, const T&,const T*> const_iterator;
    136. 	typedef RBtreeNode Node; //typedef一下RBtreeNode，根据传入的T进行节点的实例化，确定是pair还是key
    137.  
    138. 	RBTtree()
    139. 		:_root(nullptr)
    140. 	{}
    141.  
    142. 	Node* copy(Node* root)
    143. 	{
    144. 		if (root == nullptr)
    145. 			return nullptr;
    146. 		//拷贝结点
    147. 		Node* newnode = new Node(root->_data);
    148. 		newnode->_col = root->_col;//更新颜色
    149. 		//Node*newnode=new Node(*root);//这里会去调用拷贝构造，但是拷贝构造是系统默认的，只更新了颜色和data
    150. 		
    151. 		//更新左和右
    152. 		newnode->_left = copy(root->_left);
    153. 		newnode->_right = copy(root->_right);
    154. 		//更新parent
    155. 		if (newnode->_left)//不为空
    156. 		{
    157. 			newnode->_left->_parent = newnode;
    158. 		}
    159. 		if (newnode->_right)
    160. 		{
    161. 			newnode->_right->_parent = newnode;
    162. 		}
    163. 		return newnode;
    164. 	}
    165. 	//拷贝构造，需要深拷贝
    166. 	RBTtree(const RBTtree& rb)
    167. 	{
    168. 		_root=copy(rb._root);
    169. 	}
    170.  
    171. 	//赋值
    172. 	RBTtree& operator=(RBTtree tmp)
    173. 	{
    174. 		swap(_root, tmp._root);
    175. 		return *this;
    176. 	}
    177.  
    178. 	//迭代器
    179. 	iterator begin() //找最小的节点
    180. 	{
    181. 		Node* min = _root;
    182. 		while (min && min->_left)
    183. 		{
    184. 			min = min->_left;
    185. 		}
    186. 		return iterator(min);
    187. 	}
    188.  
    189. 	iterator end()
    190. 	{
    191. 		return iterator(nullptr);
    192. 	}
    193.  
    194. 	//查找函数，查找的是key
    195. 	iterator find(const K& key)
    196. 	{
    197. 		KeyOfT kot;
    198. 		Node* cur = _root;
    199. 		while (cur)
    200. 		{
    201. 			if (kot(cur->_data) > kot(key))
    202. 			{
    203. 				cur = cur->_left;
    204. 			}
    205. 			else if (kot(cur->_data) < kot(key))
    206. 			{
    207. 				cur = cur->_right;
    208. 			}
    209. 			else //找到了
    210. 			{
    211. 				return iterator(cur);
    212. 			}
    213. 		}
    214. 		return end(); //没有找到，返回nullptr;
    215. 	}
    216.  
    217.  
    218. 	void RoateR(Node*parent)
    219. 	{
    220. 		Node*subL = parent->_left;
    221. 		Node* subLR = subL->_right;
    222.  
    223. 		parent->_left = subL->_right;
    224. 		if (subLR)
    225. 			subLR->_parent = parent;
    226. 		subL->_right = parent;
    227. 		Node*prevparent = parent->_parent;
    228. 		parent->_parent = subL;
    229. 		if (parent == _root)
    230. 		{
    231. 			_root = subL;
    232. 			subL->_parent = nullptr;
    233. 		}
    234. 		else if (prevparent->_left==parent)
    235. 		{
    236. 			prevparent->_left = subL;
    237. 			subL->_parent = prevparent;
    238. 		}
    239. 		else if (prevparent->_right==parent)
    240. 		{
    241. 			prevparent->_right = subL;
    242. 			subL->_parent = prevparent;
    243. 		}
    244. 		else
    245. 		{
    246. 			assert(false);
    247. 		}
    248. 	}
    249.  
    250.  
    251. 	void RoateL(Node* parent)
    252. 	{
    253. 		Node*subR = parent->_right;
    254. 		Node*subRL = subR->_left;
    255. 		parent->_right = subRL;
    256. 		if (subRL)
    257. 		{
    258. 			subRL->_parent = parent;
    259. 		}
    260. 		subR->_left = parent;
    261. 		Node*prevparent = parent->_parent;
    262. 		parent->_parent = subR;
    263. 		if (parent==_root)
    264. 		{
    265. 			_root = subR;
    266. 			subR->_parent = nullptr;
    267. 		}
    268. 		else if (prevparent->_left == parent)
    269. 		{
    270. 			prevparent->_left = subR;
    271. 			subR->_parent = prevparent;
    272. 		}
    273. 		else if (prevparent->_right == parent)
    274. 		{
    275. 			prevparent->_right = subR;
    276. 			subR->_parent = prevparent;
    277. 		}
    278. 		else
    279. 		{
    280. 			assert(false);
    281. 		}
    282. 	}
    283.  
    284. 	//insert返回pair对象，对象里面一个是迭代器，一个是bool
    285. 	pairbool> insert(const T& data)
    286. 	{
    287. 		if (_root == nullptr)
    288. 		{
    289. 			_root = new Node(data);
    290. 			_root->_col = BLACK;
    291. 			return make_pair(iterator(_root),true);
    292. 		}
    293. 		Node* cur = _root;
    294. 		Node* parent = nullptr;
    295. 		KeyOfT kot; //创建KeyOfT的对象，相当于仿函数
    296. 		while (cur)
    297. 		{
    298. 			if (kot(cur->_data) > kot(data))//比较去调用KeyOfT对象的重载的()
    299. 			{
    300. 				parent = cur;
    301. 				cur = cur->_left;
    302. 			}
    303. 			else if (kot(cur->_data) < kot(data))//比较去调用KeyOfT对象的重载的()
    304. 			{
    305. 				parent = cur;
    306. 				cur = cur->_right;
    307. 			}
    308. 			else
    309. 			{
    310. 				//返回相同结点的迭代器
    311. 				return make_pair(iterator(cur),false);
    312. 			}
    313. 		}
    314. 		cur = new Node(data);
    315. 		//记录一下结点，好返回,因为下面会改变cur
    316. 		Node* newnode = cur;
    317.  
    318. 		cur->_col = RED;//把结点以红色插入
    319. 		if (kot(parent->_data) < kot(data))//比较去调用KeyOfT对象的重载的()
    320. 		{
    321. 			parent->_right = cur;
    322. 			cur->_parent = parent;
    323. 		}
    324. 		else 
    325. 		{
    326. 			parent->_left = cur;
    327. 			cur->_parent = parent;
    328. 		}
    329.  
    330. 		//进行红黑树的控制
    331. 		while (parent && parent->_col==RED)//父节点位黑或者不存在就结束了
    332. 		{
    333. 			Node*gradparent = parent->_parent; //这里的祖父一定是存在的，因为parent->_col==RED，所以parent不可能是根节点
    334. 			if (gradparent->_left==parent)//在左边进行插入的
    335. 			{
    336. 				Node* uncle = gradparent->_right;
    337. 				if (uncle && uncle->_col == RED)//u存在且为红色,情况1
    338. 				{
    339. 					uncle->_col = BLACK;
    340. 					parent->_col = BLACK;
    341. 					gradparent->_col = RED;
    342. 					cur = gradparent;//把祖父当成新增结点
    343. 					parent = cur->_parent;
    344. 				}
    345. 				else //u不存在或为黑   
    346. 				{
    347. 					if (parent->_left==cur) //在parent插入左边插入节点，情况2
    348. 					{
    349. 						//单旋
    350. 						//   g
    351. 						// p   u(存在为黑，或不存在)
    352. 					//    c
    353. 						RoateR(gradparent);
    354. 						gradparent->_col = RED;
    355. 						parent->_col = BLACK;
    356. 					}
    357. 					else //在parent的右边插入节点 ，情况3
    358. 					{
    359. 						//双旋
    360. 						//   g
    361. 						// p   u
    362. 						//  c
    363. 						RoateL(parent);
    364. 						RoateR(gradparent);
    365. 						cur->_col = BLACK;
    366. 						gradparent->_col = RED;
    367. 					}
    368. 					break;
    369.  
    370. 				}
    371. 			}
    372. 			else //gradparent->_left==parent，在树的右边插入了节点
    373. 			{
    374. 				
    375. 				Node*uncle = gradparent->_left;
    376. 				if (uncle && uncle->_col==RED)//情况1  u存在且为红
    377. 				{
    378. 					parent->_col = BLACK;
    379. 					uncle->_col = BLACK;
    380. 					gradparent->_col = RED;
    381. 					cur = gradparent;
    382. 					parent = cur->_parent;
    383. 				}
    384. 				else //u不存在或着u为黑
    385. 				{
    386. 					// g
    387. 					//u  p
    388. 					//     cur
    389. 					if (parent->_right == cur)//情况2
    390. 					{
    391. 						//进行左单旋
    392. 						RoateL(gradparent);
    393. 						parent->_col = BLACK;
    394. 						gradparent->_col = RED;
    395. 					}
    396. 					//  g
    397. 					//u   p
    398. 					//   c
    399. 					else //情况3
    400. 					{
    401. 						//双旋
    402. 						RoateR(parent);
    403. 						RoateL(gradparent);
    404. 						cur->_col = BLACK;
    405. 						gradparent->_col = RED;
    406. 					}
    407. 					break;
    408. 				}
    409. 			}
    410. 		}
    411. 		_root->_col = BLACK;//不管是子树还是根节点都需要是黑色
    412. 		return make_pair(iterator(newnode),true);
    413. 	}
    414.  
    415.  
    416. 	//析构函数
    417. 	~RBTtree()
    418. 	{
    419. 		Destory(_root);
    420. 		_root = nullptr;
    421. 	}
    422. 	void Destory(Node*root)
    423. 	{
    424. 		if (root == nullptr)
    425. 			return;
    426. 		Destory(root->_left);
    427. 		Destory(root->_right);
    428. 		delete root;
    429. 	}
    430. private:
    431. 	Node* _root;
    432. };
    433.  
    434. }

    my_set.h

    1. #pragma once
    2. #include"RBTree.h"
    3.  
    4. namespace zcf
    5. {
    6. 	template<class K>
    7. 	class set
    8. 	{
    9. 	public:
    10. 		struct SetKeyOfT
    11. 		{
    12. 			const K& operator()(const K& k)
    13. 			{
    14. 				return k; //直接返回key
    15. 			}
    16. 		};
    17.  
    18. 		typedef typename RBTtree::iterator iterator; //迭代器
    19.  
    20. 		pairbool> insert(const K& key)
    21. 		{
    22. 			return _t.insert(key);
    23. 		}
    24. 		iterator begin()
    25. 		{
    26. 			return _t.begin();
    27. 		}
    28. 		iterator end()
    29. 		{
    30. 			return _t.end();
    31. 		}
    32. 		iterator find(const K& key)
    33. 		{
    34. 			return _t.find(key);
    35. 		}
    36.  
    37. 	protected:
    38. 		RBTtree _t; //关键,set知道自己是key,传的是key
    39. 										//set知道怎么比较SetKeyOfT
    40. 	};
    41.  
    42. 	void test_set()
    43. 	{
    44. 		set<int> s;
    45. 		s.insert(1);
    46. 		s.insert(2);
    47. 		s.insert(3);
    48. 		set<int>::iterator it = s.begin();
    49. 		while (it!=s.end())
    50. 		{
    51. 			cout << *it<<" ";
    52. 			++it;
    53. 		}
    54. 		cout << endl;
    55.  
    56. 		set<int> s1(s);//拷贝构造
    57. 		set<int>::iterator it1 = s1.begin();
    58. 		while (it1 != s1.end())
    59. 		{
    60. 			cout << *it1 << " ";
    61. 			++it1;
    62. 		}
    63. 		cout << endl;
    64.  
    65. 		set<int> s2;
    66. 		s2 = s1; //赋值运算
    67. 		set<int>::iterator it2 = s2.begin();
    68. 		while (it2 != s2.end())
    69. 		{
    70. 			cout << *it2 << " ";
    71. 			++it2;
    72. 		}
    73. 		cout << endl;
    74. 	}
    75. }
    76.

    my_map.h

    1. #pragma once
    2. #include"RBTree.h"
    3.  
    4. namespace zcf
    5. {
    6. 	template<class K,class V>
    7. 	class map
    8. 	{
    9. 	public:
    10. 		
    11. 		struct MapKeyOfT //提供一个内置类
    12. 		{
    13. 			const K& operator()(const pair& kv)
    14. 			{
    15. 				return kv.first; //使用key进行比较，返回pair的第一个值
    16. 			}
    17. 		};
    18.         //注意这里
    19. 		typedef typename RBTtree, MapKeyOfT>::iterator iterator;//迭代器
    20.  
    21.  
    22.  
    23. 		pairbool> insert(const pair& kv)
    24. 		{
    25. 			return _t.insert(kv);
    26. 		}
    27.  
    28. 		iterator begin()
    29. 		{
    30. 			return _t.begin();
    31. 		}
    32.  
    33. 		iterator end()
    34. 		{
    35. 			return _t.end();
    36. 		}
    37.  
    38. 		iterator find(const K& key)
    39. 		{
    40. 			return _t.find(key);
    41. 		}
    42.  
    43. 		V& operator[](const K&key)
    44. 		{
    45.  
    46. 			auto ret=_t.insert(make_pair(key,V()));//给缺省值
    47. 			//ret是pair对象
    48. 			return ret.first->second;//调用迭代器的operator->()
    49. 		}
    50.  
    51.  
    52. 	protected:
    53. 		RBTtree, MapKeyOfT> _t;  //这里是关键,map知道自己是pair，所以传的pair
    54. 												//比较也是这样的，map知道怎么比较MapKeyOfT
    55. 	};
    56.  
    57. 	void test_map()
    58. 	{
    59. 		map dict;
    60. 		dict.insert(make_pair("left","左"));
    61. 		dict.insert(make_pair("right", "右"));
    62. 		dict.insert(make_pair("map", "地图"));
    63. 		dict["map"] = "地图或映射"; //修改second
    64. 		dict["state"] = "状态"; //新增
    65. 		auto it = dict.begin();
    66. 		while (it!=dict.end())
    67. 		{
    68. 			cout << it->first << ":" << it->second << endl;
    69. 			++it;
    70. 		}
    71. 		cout << endl;
    72.  
    73.  
    74. 		map dict1(dict);//拷贝构造
    75. 		auto it1 = dict.begin();
    76. 		while (it1 != dict1.end())
    77. 		{
    78. 			cout << it1->first << ":" << it1->second << endl;
    79. 			++it1;
    80. 		}
    81. 		cout << endl;
    82. 	}
    83. }

    main.cpp

    1. #include
    2. #include
    3. using namespace std;
    4. #include"my_set.h"
    5. #include"my_map.h"
    6.  
    7. int main()
    8. {
    9. 	zcf::test_set();
    10. 	zcf::test_map();
    11. 	return 0;
    12. }

     对于迭代器相对比较难的是++：

  • 相关阅读:
    【微服务】服务容错---Sentinel
    运维监控Zabbix部署
    PY32F003F18按键输入
    老卫带你学---leetcode刷题(124. 二叉树中的最大路径和)
    应用层 - 常见协议、域名、DNS、DHCP、HTTP、form提交、正向代理反向代理、CDN
    【GEE】基于GEE进行非监督学习
    【C++】C&C++内存管理
    【Verilog基础】一些时序约束相关的面试真题
    Source Map知多少？Golang手写SourceMap转换过程
    VUE3中 reacitive源码理解
  • 原文地址：https://blog.csdn.net/qq_37303158/article/details/126041837