蓝桥备赛(18)- 红黑树和 set 与 map(下)
一、红黑树
1.1 基本概念
红黑树(简称 RBT) ,也是一棵二叉搜索树(左 < 根 < 右) 。1)它是在搜索树的基础上,使每个结点上 增加一个存储位表示结点的颜色 ,可以是 Red 或者 Black。2)通过对任意⼀条从根到叶子的路径上各个结点着色方式的限制, 确保没有⼀条路径会比其他路径长出 2 倍 ,因而是⼀棵 接近!!!! 平衡的二叉搜索树。红黑树相对于 AVL 树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于 AVL树。
1.2 红黑树的规则
在一棵红黑树中,需要满足下面几条规则,在每次插入和删除之后,都应该让红黑树满足下面的规则:![]()
可以结合某道的总结 , 来记忆相关的规则:
在红黑树中 , 我们会称 空结点为叶子结点 ( 也只有在这里这么叫 )
练习 : 判断下面的树 , 是否为红黑树 ?
(为了简洁 , 叶子(NULL)结点就不画了)
1.3 红黑树的性质
最长路径不超过 最短路径的 两倍
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 红黑树的构造
红黑树的构造,就是不断向红黑树中插入新的结点:
记住 : 先判断叔叔的颜色
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;
}