当前位置： 首页 > article >正文

蓝桥备赛（18）- 红黑树和 set 与 map（下）

article 2025/3/17 11:01:15

一、红黑树

1.1 基本概念

红黑树(简称 RBT) ，也是一棵二叉搜索树（左 < 根 < 右) 。
1）它是在搜索树的基础上，使每个结点上 增加一个存储位表示结点的颜色 ，可以是 Red 或者 Black。
2）通过对任意⼀条从根到叶子的路径上各个结点着色方式的限制， 确保没有⼀条路径会比其他路径长出 2 倍 ，因而是⼀棵    接近！！！！    平衡的二叉搜索树。
红黑树相对于 AVL 树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于 AVL树。

1.2 红黑树的规则

在一棵红黑树中，需要满足下面几条规则，在每次插入和删除之后，都应该让红黑树满足下面的规则：

可以结合某道的总结 ， 来记忆相关的规则： 

在红黑树中 ， 我们会称  空结点为叶子结点  ( 也只有在这里这么叫 ) 

练习 : 判断下面的树 ， 是否为红黑树 ? 

（为了简洁 ， 叶子(NULL）结点就不画了）

1.3 红黑树的性质

最长路径不超过  最短路径的 两倍 

比较容易证明，这里就不使用严谨的数学方式了，直接看一个具体的例子感受感受。
如下图所示，最短路径最短有 3 个结点，全是黑色。因为不能出现连续的红色，所以想要最长，必
须得是红黑相间的形式，最长就是 5，不会超过最短路径的 2 倍。

1.4 红黑树的查找

与二叉搜索树的查找一样 ， 从根结点开始 ， 沿某个分支逐层 向下比较的过程 ， 若非空 ， 先将给定值与根结点的关键字比较 ， 如果相等 ， 则查找成功 ； 如果不相等 ， 且小于根结点的关键字 ， 则在根结点的左子树查找 ， 否则则在右子树查找 。 

1.5 红黑树的插入

插入过程大致为：

1 ） 按照二叉树搜索树的插入方式插入新的结点

2 ） 默认新插入的结点是红色 。 如果破坏了红黑树的规则 ， 然后就分情况调整成红黑树 。

插入结点后 ， 如果红黑树性质被破坏 ，分三种情况调整 

1） 插入结点 是   根结点

2） 插入结点的叔叔  是  红色

2） 插入结点的叔叔  是  黑色

1.5.1 情况一：插入的是根结点

这是第一个插入结点 ， 直接将结点的颜色变成黑色即可 

1.5.2 情况二：叔叔是红色

调整方式 :

1  )  叔  父  爷 变色 ， 爷爷变插入结点

2 ）继续判断符合三种条件的哪一种 ， 继续调整

1.5.1 情况三：叔叔是黑色

这种情况需要继续分情况讨论   ， 根据祖父 、 父亲 、 新结点三者的位置  ，分情况旋转（同平衡二叉树一致） + 变色 。

1.5.1.1 LL型

如果父亲 和  新结点的位置关系相对于爷爷呈现 ： 新结点是爷爷的左孩子 的左  孩子

1）  右旋爷爷结点

2） 然后将父亲（旋转中心点）和爷爷（旋转点）变色

1.5.1.2 RR型

如果父亲 和  新结点的位置关系相对于爷爷呈现 ： 新结点是爷爷的右孩子 的右  孩子  

1）  左旋爷爷结点

2） 然后将父亲（旋转中心点）和爷爷（旋转点）变色

1.5.1.3 LR型

如果父亲 和  新结点的位置关系相对于爷爷呈现 ： 新结点是爷爷的左孩子 的右  孩子  

1）  左旋爷爷结点的  左孩子

2）  右旋爷爷结点

2）  然后将（旋转中心点）和（旋转点）变色

1.5.1.4 RL型

如果父亲 和  新结点的位置关系相对于爷爷呈现 ： 新结点是爷爷的右孩子 的左  孩子  

1）  右旋爷爷结点的  右孩子

2）  左旋爷爷结点

2）  然后将（旋转中心点）和（旋转点）变色

1.6 红黑树的构造

红黑树的构造，就是不断向红黑树中插入新的结点：
根据序列 a = {18, 19, 25, 40, 30, 11, 9, 1} ，构造⼀棵红黑树

记住 ： 先判断叔叔的颜色

1）叔叔为黑  --->  旋转  + 变色！！！

1）叔叔为红  --->  叔叔、父亲、爷爷变色 ， 再考虑新的点(原爷爷)！！！

二、set / multiset

1）set  与 multiset 的区别： set 不能存相同元素 ， multiset 可以存相同元素 ， 其余的方法一致。

2） 因此我们有时候 ， 可以使用set 帮助我们给数据去重

2.1 创建set

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> mp1;
	set<string> mp2;
	return 0;
}

2.2 size/empty

1 ）size : 返回set 种实际元素的个数 

2 ） empty ： 判断 set 是否为空

时间复杂度： O(1)

2.3 begin/end

迭代器，可是使用范围 for 遍历整个红黑树

遍历是按中序遍历的顺序 ， 因此是一个有序的序列

2.4 insert

向红黑树中插入一个元素

时间复杂度：O(logN)

2.5 erase

删除一个元素

时间复杂度：O(logN)

2.6 find/count

1)查找一个元素 ， 返回的是迭代器 

2)count : 查询元素出现的次数 。 一般用来判断元素是否在红黑树中

时间复杂度：O(logN)

碎碎念 ：如果我们向查找元素是否在 set 中 ， 我们一般不使用find ， 而是用 count 。因为find 的返回值是一个迭代器 ，判断起来不方便 。

2.7 lower_bound/upper_bound

1）lower_bound : 大于等于 x 的最小元素 ， 返回的是迭代器

2）upper_bound ：大于 x 的最小元素 ， 返回的是迭代器

时间复杂度：O(logN)

2.8 所有测试代码

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

int a[] = {10, 60, 20, 70, 80, 30, 90, 40, 100, 50};
int main()
{
	 
	set<int> mp;
	
	//插入
	for(auto x:a)
	{
		mp.insert(x); 
	 } 
	 
	 //遍历set ， 最终结果应该是升序
	 for(auto x:mp)
	 {
	 	cout << x << " ";
	  } 
	  cout << endl;
	  
	  
	//查找 
	if(mp.count(1)) cout << " 1 " << endl;
	if(mp.count(99)) cout << " 99 " << endl; 
	if(mp.count(30)) cout << " 30 " << endl;
	if(mp.count(10)) cout << " 10 " << endl; 
	
	//删除
//	mp.erase(30);
//	mp.erase(10);    
//	if(mp.count(30)) cout << " 30 " << endl;
//	else cout << " no 30 " << endl;
//	if(mp.count(10)) cout << " 10 " << endl; 
//	else cout << " no 10 " << endl;	
	
	auto x = mp.lower_bound(20);
	auto y = mp.upper_bound(20);
	cout << *x << " " << *y << endl;
	  
	return 0;
}

三、map/ multimap

1）map 与 multimap 的区别 ： map 不能存相同元素 ， multimap 可以存相同的元素 ， 其余的使用方式一样 。

2）map 与 set 的区别 ： set 里面存的是一个单独的关键字 ， 也就是存一个 int 、 char 、double 或者 string 。 而 map 里面存的是一个pari<key , value > , <k-v模型> 不仅有一个关键字 ， 还会有一个关键字绑定的值 ， 比较方式是按照 key 的值来比较

3）可以这样理解 : 红黑树里面一个一个的结点都是结构体 ， 里面有两个元素分别是 key 和value 。插入 、删除 和查找的过程中 ， 比较的是 key 值 。

比如：可以在map 中 ：

---> 存<int , int > ， 来统计数字出现的次数；

---> 存<string , int > ， 来统计字符串出现的次数；

---> 存<string , string > ，表示一个字符串变成另一个字符串

---> 甚至 <int , vector<int>> 来表示一个树后面跟了若干个树...， 用来存储树（但是效率不会很高） 

3.1 创建map

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
	map<int,int> mp1;
	map<int,string> mp2;
	map<string,int> mp3;
	map<int,vector<int>>mp4;
	//甚至可以挂一个vector 
	return 0;
}

3.2  size/empty

1 ）size : 求红黑树的大小

2 ） empty ： 判断 红黑树 是否为空

时间复杂度： O(1)

3.3 begin/end

迭代器，可是使用范围 for 遍历整个红黑树

遍历是按中序遍历的顺序 ， 因此是一个有序的序列

3.4 insert

向红黑树中插入一个元素。这里需要插入一个 pair  ， 可以用 { } 形式 。比如：mp.insert({1,2})

时间复杂度：O(logN)

3.5 operator[ ]

重载[ ] ， 使得 map 可以像数组一样使用。

这是 map 最好用的 接口 ， 有了这个重载 ， map 的使用就变得特别轻松 ， 不用写很多冗余的代码 。（底层实际上就是调用了 insert 函数）

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void print(map<string,int> & mp)
{
	for(auto & p:mp)
	{
		cout << p.first << " " << p.second << endl;
	}
}


int main()
{
	map<string,int> mp;
	
	//插入 
	mp.insert({"张三",1});
	mp.insert({"李四",2});
	mp.insert({"王五",3});
	
	//print(mp);   
	
	//operator[ ] 可以让map像数组一样使用
	cout << mp["张三"]  << endl;
	mp["张三"]  = 110;
	cout << mp["张三"] << endl;
	 
	 if(mp["赵六"] == 4) cout << "yes" << endl;
	 else cout << "no" << endl;
	print(mp);
	return 0;
 } 

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void print(map<string,int> & mp)
{
	for(auto & p:mp)
	{
		cout << p.first << " " << p.second << endl;
	}
}


int main()
{
	map<string,int> mp;
	
	//插入 
	mp.insert({"张三",1});
	mp.insert({"李四",2});
	mp.insert({"王五",3});
	
	//print(mp);   
	
	//operator[ ] 可以让map像数组一样使用
	cout << mp["张三"]  << endl;
	mp["张三"]  = 110;
	cout << mp["张三"] << endl;
	 
	 if(mp.count("赵六")&& mp["赵六"] == 4) cout << "yes" << endl;
	 else cout << "no" << endl;
	print(mp);
	return 0;
 }

3.6 erase

删除一个元素

时间复杂度：O(logN)

3.7 find / count

1）lower_bound : 大于等于 x 的最小元素 ， 返回的是迭代器

2）upper_bound ：大于 x 的最小元素 ， 返回的是迭代器

时间复杂度：O(logN)

3.8  lower_bound/upper_bound

1）lower_bound : 大于等于 x 的最小元素 ， 返回的是迭代器

2）upper_bound ：大于 x 的最小元素 ， 返回的是迭代器

时间复杂度：O(logN)

3.9 所有测试代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void print(map<string,int> & mp)
{
	for(auto & p:mp)
	{
		cout << p.first << " " << p.second << endl;
	}
}


int main()
{
	map<string,int> mp;
	
	//插入 
	mp.insert({"张三",1});
	mp.insert({"李四",2});
	mp.insert({"王五",3});
	
	//print(mp);   
	
	//operator[ ] 可以让map像数组一样使用
	cout << mp["张三"]  << endl;
	mp["张三"]  = 110;
	cout << mp["张三"] << endl;
	 
	 if(mp.count("赵六")&& mp["赵六"] == 4) cout << "yes" << endl;
	 else cout << "no" << endl;
	 
	mp.erase("张三");
	print(mp);
	return 0;
 }

当然我们也可以利用map , 找出字符串中 ， 字符串出现的次数：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void print(map<string,int> & mp)
{
	for(auto & p:mp)
	{
		cout << p.first << " " << p.second << endl;
	}
}
void fun()
{
	string s; 
	map<string,int> mp;	
	for(int i = 1;i<=10;i++)
	{
		cin >> s;
		mp[s]++;
	}
	print(mp);
} 

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

四、算法题

4.1 英语作文

P2786 英语1（eng1）- 英语作文 - 洛谷

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;

int n,p;
map<string,int> mp;//<高级词汇，含金量>
 
 bool check(char ch)
 {
 	if(isdigit(ch) || isalpha(ch))
 	 return true;
 	else
 		return false;
 }
int main()
{
	cin >> n >> p;

	//存储<高级词汇,含金量>
	for(int i = 1;i<=n;i++)
	{
		string s;
		int x;
		cin >> s >> x;
		mp[s] = x;	
	} 
	
	//读取字母，判断是否为高级词汇
	LL ret = 0;
	char ch;//一个一个字符读
	string t = "";
	while(scanf("%c",&ch)!=EOF) 
	{
		if(check(ch)) t += ch;
		else
		{
			//读到分割符
			ret = (ret + mp[t]) % p;
			t=""; 
		}
	}
	cout << ret << endl;
	return 0;
}

4.2 营业额统计

P2234 [HNOI2002] 营业额统计 - 洛谷

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

const int INF = 1e7 + 10;
int n;
set<int> mp;
int main()
{
	cin >> n;
	int ret = 0;
	cin >> ret;
	mp.insert(ret);
	
	
	//左右护法 - 防止越界访问
	mp.insert(-INF);
	mp.insert(INF);
	
	for(int i = 2;i<=n;i++)
	{
		int x;
		cin >> x;
		auto it = mp.lower_bound(x);
		auto tmp = it;
		tmp--;
		
		if(*it == x) continue;
		ret += min(abs(*tmp - x),abs(*it - x));
		mp.insert(x);
	 }
	 cout << ret << endl; 
	return 0;
}

4.3 木材仓库

P5250 【深基17.例5】木材仓库 - 洛谷

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

typedef long long LL;
const LL INF = 1e10 + 10;
int n;
set<LL> mp;

int main()
{
	cin >> n;
	int op,x;
	mp.insert(-INF);
	mp.insert(INF);  
	while(n--)
	{
		cin >> op >> x;
		//进货 
		if(op == 1)
		{
			if(mp.count(x) )
				cout << "Already Exist" << endl;
			else
				mp.insert(x);  
		}
		//出货 
		else
		{
			if(mp.size() == 2 ) 
				cout << "Empty" << endl;
			else
			{
				auto it = mp.lower_bound(x);
				auto tmp = it;
				tmp--;
				auto ret = 0;
				
				if(abs(*tmp - x) <= abs(*it - x))
				{
					cout << *tmp << endl;
					mp.erase(tmp); 
				}
				else 
				{
					cout << *it << endl;
					mp.erase(it); 
				}
				 
			}			
		}
	 } 
	return 0;
}

http://www.kler.cn/a/585642.html

相关文章：

  • 专家系统如何运用谓词逻辑进行更复杂的推理
  • 微软为何选择用Go而非Rust重写TypeScript
  • C++程序设计语言笔记——抽象机制：类层次
  • 力扣——146.LRU缓存
  • 2018年全国职业院校技能大赛-高职组计算机网络应用竞赛竞赛样题A卷
  • 2025年跨网文件交换系统推荐：安全的内外网文件传输系统Top10
  • PyQt基础——简单的图形化界面（窗口）
  • PowerShell New-Item命令（多功能命令，用于创建文件、目录、注册表项等多种类型的项目）
  • 彩色图像Opencv转Qimage【避坑】
  • ELK(Elasticsearch、Logstash、Kbana)安装及Spring应用
  • C语言从入门到精通
  • 程序化广告行业（14/89）：DSP供应商评估、服务模式与常见平台
  • MySQL 衍生表（Derived Tables）
  • 动态路径规划——01背包问题讲解和通过滚动数组优化
  • 零基础小白如何系统学习Spring Boot
  • 无需微调的对齐方法URIAL
  • 态势感知产品通用的一些安全场景设计
  • Python实现计算地图多个点的中心位置（详细功能实现及环境搭建）
  • 子像素卷积优化记录
  • vscode 中快捷生成模板快捷键