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

蓝桥备赛(18)- 红黑树和 set 与 map(下)

一、红黑树

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 中快捷生成模板快捷键