蓝桥杯备考：红黑树与map和set

搜索二叉树

我们三种树只了解原理，不写代码，因为我们竞赛不做要求，只是为了使用set和map做铺垫

原理记不住，没关系，我们只要会各种操作的时间复杂度

二叉搜索树的定义 1°若左子树非空，左子树所有结点的权值小于根结点的权值

2°若右子树非空，右子树所有结点的权值大于根结点的权值

3°左右子树都是一颗二叉搜索树

简单来说 左<根<右

所以二叉搜索树的中序遍历的结果是从小到大

2   5   6  8  11  18  26

第一个操作：查找（二叉搜索树最本质的东西）

根据BST的特性，从根节点开始一路向下找

比如我们要查找一个6 

6比11小，所以我们从左子树向下继续找，6比5大，所以我们从5的右子树向下找，6比8小 我们从8的左子树向下找，

查找失败的案例：查找24

所以我们当我们的结点分布的均匀的话 二叉搜索树的时间复杂度应该就是树高 也就是logN，是一个非常优秀的时间复杂度

插入：和查找操作差不多

比如我们插入一个10，我们通过不断查找到空位置的时候就把10插进去

所以我们的插入操作也是logN的时间复杂度

构建二叉搜索树

插入第一个数，第二个数和10比较应该是小于10的所以放在左子树

插入第三个数8 8比10小，所以去左子树，8比5大 所以放在5的右孩子的位置接下来看18 18比10大 放在右子树

接下来是11 11比10大 去右子树 比18小 放在18的左孩子上   

接下来是2 2比10小 进入10的左孩子 2比5小 把2放在5的左孩子

接下来插入26  26比10大，进入右子树，比18大，放在18的右子树

接下来插入6 6比10小 进入左子树 比5大 进入右子树 比8小 放在8的左子树

这是正常的二叉搜索树，每个结点构建的时间复杂度基本就是logN

但是我们也要考虑一些极端的情况

6在2的右子树，8比2大进入右子树 8比6大放在6的右孩子的位置

10也是放在8的右孩子的位置，这种情况就是极端情况了，它插入每个结点的时间复杂度和单链表差不多 是N级别的复杂度，所以这时候我们就需要有平衡二叉树的东西了

删除操作

删除操作分为3种情况 1°删除的结点是叶子结点

2°删除的结点只有左子树或者右子树

3°删除的结点既有左子树又有右子树

1°删除叶子结点 我们的策略很简单，直接删除，因为删除这个结点不影响二叉搜索树的性质

比如这个搜索树，我们要删除5这个结点，5是有右子树的，由于左子树的所有值都比根结点要小，我们把8替换到5这个位置是不影响搜素破二叉树的性质的，

所以我们的结果就是

第三种情况 就是删除的结点既有左子树和右子树

比如我们删除10这个结点 左右子树都有，这时候我们有两个策略，第一种策略就是把左子树最大的结点和根结点进行替换，然后删除这个大结点，比如如图最大的结点是8 我们把根结点换成8 然后删除左子树的8，左子树的8是一个只有左子树的结点，直接把6结点上移

这一切的前提就是因为左子树最大的那个结点是一定一定没有右子树的

而且左子树最大的结点换到根结点，这个根结点是一定大于左子树小于右子树的

我们的第二种策略就是把右子树最小的结点换到根结点，然后删除这个结点，也是符合搜索树的性质的

我们要学一个特殊的东西，我们原来的二叉搜索树中序遍历之后就是 2 5 6 8 10 11 18 26

我们删除10结点，用的是它的前驱结点8或者后继结点11来替换它，

我们创建二叉树并不是为了排序，而是为了插入查找数据

如果BST不是极端情况，那么它的这些操作时间复杂度都是logN是很低的

但是二叉搜索树毕竟是不能阻止极端情况发生的

所以我们后面要学习平衡二叉树

平衡二叉树

平衡二叉树也叫avl树 本质也是一种二叉搜索树

它的性质1° 左右子树的高度差绝对值不超过1

2°每个子树都是平衡二叉树

左边这棵树平衡因子的绝对值不超过1 是平衡二叉树         右边这棵树平衡因子超过1 不是平衡二叉树

平衡二叉树的查找 插入 删除和搜索二叉树基本上是一致的，只不过对于失衡它会进行调整

处理失衡的操作

左旋操作（以右孩子为轴向左旋转）

这种失衡，我们就要进行左旋操作因为根结点是小于右子树的所有结点的，我们把根结点变成右孩子的左子树，是没问题的没毛病的 经过我们的左旋，我们的树既符合搜索树，又变得平衡了

接下来我们来处理一下复杂的左旋，当我们左旋时右孩子存在左子树时，我们就把根结点左旋过来，把那个左子树变成原来根结点的右子树

右旋操作

如果右旋的时候，左孩子的右子树是有结点的，那我们就把根结点右旋到右子树然后把左孩子原来的右子树变成根节点的左孩子就行了

插入操作

我们因为插入导致失衡的话，失衡的结点一定只可能是2或者-2，我们只需要调整一下最小不平衡子树，那么这颗子树所有的失衡结点都会向0靠近一位，我们的工作就完成了

我们的插入要分为四种情况

LL型

如果插入的结点位于最小失衡树的 根结点的左孩子的左子树上，我们只需要右旋我们的根节点就好了 

RR型

如果插入的结点位于最小失衡树的右孩子的右子树上，这时候我们就左旋一下最小失衡树的根结点

LR型

如果插入的元素位于左孩子的右子树上，我们就先左旋左孩子，再右旋根结点

RL型

如果插入的元素位于右孩子的左子树上，我们就先右旋右孩子，再左旋根结点

构建平衡树

依次插入15，10，6

插入6的时候 15这个结点的平衡因子是2 插入结点是左孩子左子树，我们要右旋一下失衡结点

接下来继续插入 18，12，13

13插入进去之后 10这个结点平衡因子就是-2，插入结点位于右孩子左子树，先右旋右孩子，再左旋根节点

接下来继续插入8导致10这个结点失衡

插入位置再左孩子的右子树，先左旋左孩子，再右旋根结点

接下来插入20，17，插入到28时15这个结点失衡，插入位置在右孩子右子树，左旋根节点15就完成了

构建完毕，接下来我们来简单了解一下删除操作

删除操作

删除结点的操作和平衡二叉树是一致的，删除完之后我们要找到最小不平衡子树，看它的最高儿子结点是左还是右，左就是L 右就是R 再看最高孙子结点是左是右，来判断旋转类型

当我们删除6这个结点，8结点是第一课不平衡子树的根结点，失衡因子是-2，最高儿子结点在右子树，最高孙子结点在左子树  所以是RL型，先右旋右孩子，再左旋根节点

紧接着，12这课树也是不平衡子树，最高儿子结点在右子树，最高孙子结点也在右子树，我们只要左旋根节点就行了

如此，删除完毕，接下来我们学红黑树

红黑树

红黑树是一个效率更高的树，

红黑树是什么样的树 1°在二叉搜索树的基础上，给每个结点赋予红或者黑的颜色

2° 由于最长的路径不高于最短路径的两倍，所以这是一颗接近平衡的搜索树

红黑树牺牲了一部分平衡性来换取 插入/删除时的旋转操作少量，整体来说性能是高于AVL树的

红黑树的规则：左根右（就是搜索树的性质）

根叶黑 （根结点和叶子结点都是黑色的）

不红红  红色结点不能连续存在

黑路同  每条路径黑色结点个数相同

此时，这棵树是符合左根右，根叶黑，不红红三条性质的，

但是 !每条路径黑色结点个数不全是相同的

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

比如我们简单证明一下

假设最短路径是三个黑色结点，那最长路径为了符合不红红，根叶黑，黑路同的性质，最长路径一定是5 如图

所以说最长路径一定不超过最短路径的两倍

通过这个性质，能推出h<= 2 * log(n+1),我们的各种操作都是log级别的时间复杂度

红黑树的插入

首先我们插入的元素默认是红色的，因为如果我们插入黑色结点，那么为了黑路同的性质，我们要调整的路径会特别多

比如如图插入的是黑色结点

插入的那条路径黑色结点变多了，我们就要调整其他所有路径和他一样，我们不要这样，所以我们默认都插入红色结点，这样他只会影响不红红和根叶黑的性质

插入结点后 如果红黑树的性质被破坏，我们会分为三种情况

1°插入结点是根结点

---》直接变黑

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

如果插入结点的叔叔是红色结点的话，我们要把叔父爷的结点变色，然后把爷爷结点当作插入结点处理

如图这是我们变色后的结果，最后我们把8结点当做插入结点，因为他是根结点，直接变成黑色就行了

3°插入结点的叔叔是黑色

如果插入结点的叔叔是黑色结点，那我们就有几种策略来处理了

也就是我们需要（LLor LR or RR or RL）旋转 然后变色处理来解决

1°LL旋转

如图插入结点在根结点的左孩子的左子树，所以我们是LL型的，这时候我们就右旋根结点然后变换旋转中心和旋转结点的颜色即可

2°LR旋转

当我们插入结点是在左孩子的右子树的时候，我们就先左旋左孩子，再右旋根结点，再变换旋转结点和旋转中心结点的颜色

如图这种情况就是插入结点位于左孩子的右子树上，我们先左旋左孩子，再右旋根结点后变色

3° RR旋转

如图这种就是RR型，我们只需要左旋根结点变换颜色就好了

4°RL旋转

RL就是先右旋右孩子，再左旋左孩子，再变色

构建红黑树

先插入根结点18，由于他是根，我们直接把它变成黑色

接下来我们插入19，插入19是不影响红黑树的性质的，我们继续插入24

当我们24插进去的时候，触犯了我们不红红的性质，我们看到24的叔叔结点是黑色的，插入位置再右孩子右子树，我们左旋爷爷结点就行啦

接下来我们插入35，违反了不红红，插入结点的叔叔是红结点，我们只需要变换爷叔父结点的颜色就行了，又因为爷爷结点是根结点，所以爷爷结点再换回黑色

接下来插入28，又违反了不红红，叔叔结点是黑色结点，

插入16，不影响红黑树的性质

然后插入10

插入10的时候，10的叔叔是黑色结点，所以我们只需要右旋爷爷结点就行了

接下来插入7，叔叔结点是红结点

我们只需要改变叔叔爷爷父亲结点的颜色，然后把爷爷结点当成插入结点继续操作就行

接下来我们插入9这个结点

叔叔结点是黑色结点，LR型，先左旋左孩子，再右旋10这个爷爷结点

接下来插入6这个结点

6的叔叔结点是红色，我们只需要变换6的爷爷父亲叔叔结点的颜色然后把爷爷结点当作插入结点

接下来把9这个结点再当成插入结点把9的爷爷进行右旋

接下来我们再插入26这个结点

26这个结点的叔叔也是红结点，我们只需要把叔叔爷爷父亲结点变换颜色把爷爷结点当成插入结点就行了

28叔叔还是红结点，继续进行方才的操作

红黑树构建完毕！！！

set/multiset

set是我们C++里面已经实现好的红黑树的容器，set不能存储重复元素，multiset可以存储重复元素，有时候我们能用set进行去重

接口 size：返回元素个数 ，时间复杂度是O（1） empty 判空 时间复杂度也是O（1）

begin/end 迭代器，我们遍历set的元素的时候是按中序遍历进行的，返回的是一个有序的序列

insert 向红黑树插入一个元素，时间复杂度是logN级别的

查找有 find/count  区别就是find返回的是迭代器，count返回的是一个元素出现的个数，时间复杂度都是logN级别

lower_bound 查找大于等于x的最小元素。upper_bound 查找大于x的最小元素

我们来用代码实现一下

这是我们构建红黑树和遍历红黑树的过程

这是我们测试count和erase接口，由于find接口要返回一个迭代器，我们很少用find 都用count

这是测试lower_bound 和upper_bound 接口

总代码如下

#include <iostream>
#include <set>using namespace std;
int a[] = { 10, 60, 20, 70, 80, 30, 90, 40, 100, 50 };
int main()
{set <int> mp;for (auto e : a){mp.insert(e);}for (auto e : mp){cout << e << " ";}cout << endl;/*if (mp.count(1)) cout << "1" << endl;if (mp.count(30)) cout << "30" << endl;if (mp.count(60)) cout << "60" << endl;mp.erase(30);if (mp.count(30))cout << "30" << endl;elsecout << "不存在30" << endl;*/auto x = mp.lower_bound(20);auto y = mp.upper_bound(20);cout << *x << " " << *y << endl;return 0;
}

map/multimap

我们已经学了set，map就是在set的基础上，多了一个关键字，它的每个元素都绑定着一个值

在学习map之前，我们先给出两个场景

场景1：判断一堆字符串中，某一个字符是否出现过

这种情况，我们可以一个set来解决

场景2：判断一堆字符串中，某一个字符串出现的次数

这时候，我们就必须要用map了，map<string,int>来绑定上每个字符串出现的个数

我们的map红黑树里每个元素存储的pair类型的元素 pair<key,value> 这个也特别像我们在python里学的字典

我们可以这样理解，我们的map里存储的每个元素都是一种结构体，然后我们插入查找的时候比较的是key，每个key绑定着一个value值

可以是map<int,int>判断每个数字出现的次数

可以是map<string,int>判断每个字符串出现的次数

可以是map<string,string>表示字符串替换

也可以是map<int,vector<int>>表示很多树

我们map的接口和set是差不多的

size和empty时间复杂度和set一样的都是O（N）

insert插入元素，注意我们这里插入的是pair类型，比如insert({1,2})，时间复杂度是logN

operator[] 这个运算符重载使得我们能像数组一样查询map的元素，我们的下标就是key，查询的结果就是value的值

其他的erase，find/count和set是一样一样的 时间复杂度都是常数级别

测试插入

我们可以看到，打印的时候是按照字典序打印的

这是我们重载的方括号，和数组用法是一样的

我们需要注意的一点就是，我们的方括号重载有可能会向我们的map里插入我们本不想插入的元素，比如

刘强自动被我们创建了，并且它的初始值是0

然后我们想规避这种插入的话，就需要在判断相等之前先判断这个元素是否存在

好的，最后我们就来实现一下查找一堆字符串中某个字符串出现次数的代码吧

#include <iostream>
#include <map>
using namespace std;void print(map<string, int>& t)
{for (auto e : t){cout << e.first <<" " <<  e.second << endl;}
}
map <string, int> mp;
void fun()
{string s;for (int i = 1; i <= 10; i++){cin >> s;mp[s]++;}print(mp);
}
int main()
{fun();	//map<string, int> mp;//mp.insert({ "张三",1 });//mp.insert({ "李四",2 });//mp.insert({ "王五",3 });//print(mp);///*print(mp);//cout << mp["张三"] << endl;//mp["张三"] = 110;//cout << mp["张三"] << endl;*///if (mp.count("刘强") && mp["刘强"] == 3) cout << "yes" << endl;//else cout << "no" << endl;//print(mp);return 0;
}

set和map算法题

1.英语作文问题

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>
#include <map>
using namespace std;
bool check(char ch)
{if (ch == ' ' || ch == ',' || ch == '!' || ch == '?' || ch == '.')return false;return true;
}int main()
{int n, p;cin >> n >> p;map <string, int> mp;while (n--){string t;int tmp;cin >> t >> tmp;mp.insert({ t,tmp });}char ch;int sum = 0;string ret;scanf("%c", &ch);while (scanf("%c", &ch) != EOF){if (check(ch)) ret += ch;else {sum += mp[ret];ret = "";}}cout << sum%p << endl;return 0;
}

2.营业额统计

我们的思路就是先把第一天的营业额作为最小波动值放到set里，然后不断利用lower_bound找最接近的值求最小差加到和里面就行了，找最近的值就先用lowerbound找到最小的比这个数大的值，再找最大的比这个数小的值，比较出差值最小的，就是最小波动值，当然这个过程也有可能会越界，我们要处理一下边界情况

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
const int INF = 1e7+10;
set<int> mp;
int sum = 0;
int main()
{mp.insert(-INF);mp.insert(INF);int n;cin >> n;int ret;cin >> ret;mp.insert(ret);sum+=ret;for(int i = 2;i<=n;i++){int ret; cin >> ret;auto it = mp.lower_bound(ret);auto tmp = it;tmp--;int r = min(abs(*it-ret),abs(*tmp-ret));sum+=r;mp.insert(ret);}cout << sum << endl;
}

3.木材仓库

#include <iostream>
#include <set>
using namespace std;
typedef long long ll;
const ll INF = 1e10+10;int main()
{set <ll> mp;int n;cin >> n;mp.insert(-INF);mp.insert(INF);while(n--){int op;cin >> op;if(op == 1){int t;cin >> t;if(mp.count(t)) cout << "Already Exist" << endl;else mp.insert(t);}else{int t;cin >> t;if(mp.size()== 2) cout << "Empty" << endl;else{auto it = mp.lower_bound(t);auto tmp = it;tmp--;if(*tmp-t <= *it -t){cout << *tmp << endl;mp.erase(*tmp); }else{cout << *it << endl;mp.erase(*it);}				}}}return 0;
}

这道题和上一道题非常之相似

，