数据结构 红黑树和set/map

数据结构 红黑树和set/map

引用

CSDN

1.

https://m.blog.csdn.net/hjx1235/article/details/145669120

一、set/multiset

set 与multiset 的区别： set 不能存相同元素， multiset 可以存相同的元素，其余的使用方式完全一致。因此，我们有时候可以用set 帮助我们给数据去重。
在这里只练习使用set 。 set 会用， multiset 也会用。

创建set

#include <iostream>
#include <set>
using namespace std;
int main()
{
 set<int> mp1;
 set<string> mp2;
 return 0;
}  

size/empty

1. size ：返回set 中实际元素的个数。时间复杂度：O(1) 。
2. empty ：判断set 是否为空。时间复杂度：O(1) 。
   begin/end
   迭代器，可以使用范围for遍历整个红黑树。
   遍历是按照中序遍历的顺序，因此是一个有序的序列。
   insert
   向红黑树中插入一个元素
   时间复杂度：O(log N) 。
   erase
   删除一个元素
   时间复杂度：O(log N) 。
   find/count
3. find ：查找一个元素，返回的是迭代器。时间复杂度：O(log N) 。
4. count ：查询元素出现的次数，一般用来判断元素是否在红黑树中。时间复杂度：
   。O(log N)
   如果想查找元素是否在set中，我们一般不用find，而是用count。因为find的返回值是一个迭代器，判断起来不方便。
   lower_bound/upper_bound
5. lower_bound ：大于等于x的最小元素，返回的是迭代器；
   时间复杂度：O(log N) 。
6. upper_bound ：大于x的最小元素，返回的是迭代器。
   时间复杂度：O(log N) 。

#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 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

map 与multimap 的区别： map 不能存相同元素， multimap 可以存相同的元素，其余的使用方式完全一致。因此，这里只练习使用map 。
map 与set 的区别： set 里面存的是一个单独的关键字，也就是存一个int 、 char 、
double 或者string 。而map 里面存的是一个pair<key, value> ，（k-v模型）不仅
有一个关键字，还会有与关键字绑定的值，比较方式是按照key 的值来比较。
可以这样理解：红黑树里面一个个的结点都是一个结构体，里面有两个元素分别是key 和value 。插入、删除和查找的过程中，比较的是key 的值。
比如，我们可以在map 中：
• 存<int, int> ，来统计数字出现的次数；
• 存<string, int> ，来统计字符串出现的次数；
• 存<string, string> ，表示一个字符串变成另一个字符串；
• 甚至存<int, vector> 来表示一个数后跟了若干个数......，用来存储树。

创建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  

size/empty

1. size ：求红黑树的大小。时间复杂度：O(1) 。
2. empty ：判断红黑树是否为空。时间复杂度：O(1) 。
   begin/end
   迭代器，可以使用范围for遍历整个红黑树。
   遍历是按照中序遍历的顺序，因此是一个有序的序列。
   insert
   向红黑树中插入一个元素。这里需要插入一个pair，可以使用{} 形式。比如： mp.insert({1,
   2}) 。
   时间复杂度：O(log N) 。
   operator[]
   重载[] ，使的map可以像数组一样使用。
   这是map最好用的接口，有了这个重载，map的使用就变得特别轻松，不用写很多冗余的代码。
   它的底层其实就是调用了insert函数，并且会返回val的引。
   erase
   删除一个元素。
   时间复杂度：O(log N) 。
   find/count
3. find ：查找一个元素，返回的是迭代器。时间复杂度：O(log N) 。
4. count ：查询元素出现的次数，一般用来判断当前元素是否在红黑树中。时间复杂度：
   O(log N) 。
   5.8 lower_bound/upper_bound
5. lower_bound ：大于等于x的最小元素，返回的是迭代器。时间复杂度：O(log N) 。
6. upper_bound ：大于x的最小元素，返回的是迭代器。时间复杂度：O(log N) 。

#include <iostream>
#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]++; // 体现了 operator 的强大 
 }
 print(mp);
}
int main()
{
 fun();
 // 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; 
 // // 注意事项：operator[] 有可能会向 map 中插入本不想插入的元素 
 // // [] 里面的内容如果不存在 map 中，会先插入，然后再拿值 
 // // 插入的时候：第一个关键字就是 [] 里面的内容，第二个关键字是一个默认值 
 // if(mp.count("赵六") && mp["赵六"] == 4) cout << "yes" << endl; 
 // else cout << "no" << endl;
 // // 删除 
 // mp.erase("张三"); 
 // print(mp);
 return 0;
}