题目描述

关系

有序表-BST

内容

你需要写一种数据结构，来维护一些数，其中需要提供以下操作：

1. 插入数值 $x$。
2. 删除数值 $x$。
3. 输出数值 $x$ 的前驱 (前驱定义为现有所有数中小于 $x$ 的最大的数)。
4. 输出数值 $x$ 的后继 (后继定义为现有所有数中大于 $x$ 的最小的数)。

题目保证：

• 操作 $1$ 插入的数值各不相同。
• 操作 $2$ 删除的数值一定存在。
• 操作 $3$ 和 $4$ 的结果一定存在。

输入格式

第一行包含整数 $n$，表示共有 $n$ 个操作命令。

接下来 $n$ 行，每行包含两个整数 $opt$ 和 $x$，表示操作序号和操作数值。

输出格式

对于操作 $3,4$，每行输出一个操作结果。

数据范围

$1\le n\le 2000$，
$-10000\le x\le 10000$

输入样例：

6
1 1
1 3
1 5
3 4
2 3
4 2

输出样例：

3
5

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1e8;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;

void insert(TreeNode* &root, int x) {
    if (!root) root = new TreeNode(x);
    else if (x < root->val) insert(root->left, x); // find in the left tree
    else insert(root->right, x); // find in the right tree
}

void remove(TreeNode* &root, int x) {
    if (!root) return;
    if (x < root->val) remove(root->left, x);
    else if (x > root->val) remove(root->right, x);
    else {
        // x == root->val
        // root is leaf
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else {
            // root has left and right
            auto p = root->left; // p is root's left subtree
            // find the rightmost node of root's left subtree.
            while (p->right) p = p->right;
            root->val = p->val;
            // delete it
            remove(root->left, p->val);
        }
    }
}

// get the biggest node that is smaller than x
int get_pre(TreeNode* root, int x) {
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}

// get the smallest node that is bigger than x
int get_suf(TreeNode* root, int x) {
    if (!root) return INF;
    if (root->val <= x) return get_suf(root->right, x);
    return min(root->val, get_suf(root->left, x));
}

int main()
{
    int n;
    cin >> n;
    while (n--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suf(root, x) << endl;
    }
    return 0;
}