数据结构红黑树和set/map

一、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 1. find ：查找⼀个元素，返回的是迭代器。时间复杂度：O(log N) 。 2. count ：查询元素出现的次数，⼀般⽤来判断元素是否在红⿊树中。时间复杂度： 。O(log N) 如果想查找元素是否在set中，我们⼀般不使⽤find，⽽是⽤count。因为find的返回值是⼀个迭代器，判断起来不⽅便。

lower_bound/upper_bound 1. lower_bound ：⼤于等于x的最⼩元素，返回的是迭代器； 时间复杂度：O(log N) 。 2. 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<int>> 来表⽰⼀个数后⾯跟了若⼲个数......，⽤来存储树。

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

1. find ：查找⼀个元素，返回的是迭代器。时间复杂度：O(log N) 。 2. count ：查询元素出现的次数，⼀般⽤来判断当前元素是否在红⿊树中。时间复杂度： O(log N) 。 5.8 lower_bound/upper_bound 1. lower_bound ：⼤于等于x的最⼩元素，返回的是迭代器。时间复杂度：O(log N) 。 2. 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; }