蓝桥备赛（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;
}