红黑树（RBT）

基本概念

概念

它是在BST树的基础上，使每个结点增加一个存储位表示结点的颜色，可以是Red或Black

通过对任意一条从根到叶子的路径上，各个结点着色方式的限制，确保没有一条路径会比其他路径长出2倍，因此是一颗接近平衡的BST树（并不是完全平衡的AVL树）

它牺牲了部分平衡，以换取插入/删除时只需要少量的旋转操作，整体来说性能要高于AVL树
RBT树的规则
- 满足BST树的规则
- 根结点以及叶子结点是黑色的（此处叶子结点指空结点）
- 红色结点的左右孩子是黑色的（即任意一条路径中，不会存在连续的红色结点）
- 任意结点到叶子结点的所有路径上，黑色结点的数量相同
总结：左根右、根叶黑、不红红、黑路同
RBT树的性质

有了规则限制后，可以得到最长路径不超过最短路径的两倍（证明略）

通过严谨的数学运算可得，树高 \(h\leq2log(n+1)\)
插入元素时调整RBT树
- 插入结点默认为红色（插入结点是根结点：直接变黑）
- 叔叔是红色，叔叔、父亲、爷爷变色，爷爷变插入结点
  - 叔叔（10）、父亲（7）、爷爷（9）变色
  - 爷爷（9）变插入结点，插入结点的叔叔是黑色（28），LL旋转
  - 然后再旋转点、旋转中心变色
- 叔叔是黑色，（LL、RR、LR、RL）旋转，然后旋转点、旋转中心结点变色
  - 旋转后
  - 旋转点、旋转中心变色

set、map

注：具体使用参阅C++与STL

概念

set 与 unordered_set、map 与 unordered_map 的核心区别，前者是用红黑树实现的，后者是用哈希表实现的

lower_bound()、upper_bound() 使用示例

在后面学习二分时，还会遇到这两个东西

#include <iostream>
#include <set>

using namespace std;

int main() {
    int data[] = {10, 60, 20, 70, 80, 30, 90, 40, 100, 50};
    set<int> s;
    for (auto x: data) {
        s.insert(x);
    }

    auto x = s.lower_bound(30);
    auto y = s.upper_bound(30);

    while (x != s.end()) {
        cout << *(x++) << " ";
    }
    cout << endl;

    while (y != s.end()) {
        cout << *(y++) << " ";
    }
    cout << endl;

    return 0;
}

使用map统计字符串次数

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> mp;
    string s;

    // 统计n个字符串中，目标字符串的个数
    int n = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        mp[s]++;
    }

    cout << "abc出现的次数为：" << mp["abc"] << endl;
    return 0;
}

map中，operator[]的使用

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> mp;

    mp.insert({"01-Hello,World!", 1});
    mp.insert({"03-张三", 2});
    mp.insert({"02-李四", 3});

    cout << mp["03-张三"] << endl; // 调用值
    mp["03-张三"] = 110; // 修改值

    return 0;
}

注：调用operator[]时，可能会插入本不想插入的元素，例如：
if (mp["赵六"] == 4)
       cout << "yes" << endl; // 误插入{"赵六", 0}
调用时，会把[]里面的值先插入（第一个关键字为[]内的，第二个关键字为默认值），再拿取引用。所以，在调用时，先count一下判断元素是否存在