平衡查找树

1. 满足BST (Binary Search Tree)
2. 平衡树的单旋转：右旋拎左右挂左，左旋拎右左挂右

常见的平衡树

1. Treap (tree + heap)
   每个节点随机生成val值, 按堆进行旋转平衡
2. AVL树
   严格平衡每个节点的高度, 两子树高度之差不能超过1
3. 红黑树
   实现较复杂，其中map和set的底层原理是基于红黑树实现的

问题

题目链接

解法一：

vertor模拟查找树，vertor的存储和API使用机制有平衡二叉树的特性

AC Code

#include <bits/stdc++.h>
#define debug(x) cout << #x << ' ' << x << '\n'
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
const int N = 100010, mod = 1e9 + 7, inf = 0x3f3f3f3f;

ll n;
vector<ll> v;

void solve()
{

    cin >> n;
    while (n--)
    {
        ll op, x;
        cin >> op >> x;
        // 插入 x 数
        if(op == 1) v.insert(lower_bound(v.begin(), v.end(), x), x);
        // 删除 x 数(若有多个相同的数，应只删除一个)
        if(op == 2) v.erase(lower_bound(v.begin(), v.end(), x));
        // 查询 x 数的排名(排名定义为比当前数小的数的个数+1 )
        if(op == 3) cout << lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
        // 查询排名为 x 的数
        if(op == 4) cout << v[x - 1];
        // 求x的前驱(前驱定义为小于x，且最大的数)
        if(op == 5) cout << v[lower_bound(v.begin(), v.end(), x) - v.begin() - 1];
        // 求x的后继(后继定义为大于x，且最小的数)
        if(op == 6) cout << v[upper_bound(v.begin(), v.end(), x) - v.begin()];
        if(op != 1 && op != 2) cout << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    solve();

    return 0;
}