考研数据结构——每日一题[二叉排序树]

3786. 二叉排序树

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

插入数值 x。 删除数值 x。 输出数值 x 的前驱(前驱定义为现有所有数中小于 x 的最大的数)。 输出数值 x 的后继(后继定义为现有所有数中大于 x 的最小的数)。 题目保证：

操作 1 插入的数值各不相同。 操作 2 删除的数值一定存在。 操作 3 和 4 的结果一定存在。 输入格式 第一行包含整数 n，表示共有 n 个操作命令。

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

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

数据范围 1≤n≤2000， −10000≤x≤10000 输入样例： 6 1 1 1 3 1 5 3 4 2 3 4 2 输出样例： 3 5

左旋、右旋不改变中序遍历，且互逆 背过：①最小不平衡树，从下往上找，找到第一个不平衡的子树 ②按照类型规则旋转 四种类型 ：LL、RR、LR、RL 看图的感悟：LR：左C后变LL，再右旋A ；RL：右C后变RR，再左旋A ； 手写二叉排序树【前驱和后继为遍历序列左右相邻元素】 先序【根左右】、中序【左根右】、后序【左右根】 [小三角判断]

insert(TreeNode* &root, int x) 递归查找左<根<右
remove(TreeNode* &root, int x) 先找再分类删
get_pre(TreeNode* root, int x) 寻找前驱【找小于的最大值，不存在用-INF负无穷】
get_suc(TreeNode* root, int x) 寻找后继   【找大于的最小值，不存在用INF正无穷】

#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);//【找到位置后，指针指向new的新结点】
    else if (x < root->val) insert(root->left, x);//小于父结点值，放左子树，递归判断下一次插入
    else insert(root->right, x);//大于父结点值，放右子树，递归判断下一次插入
}

void remove(TreeNode* &root, int x)//先找再分类删【左右子树是否为空分四类】 
{
    if (!root) return;//树为空，删除的数不存在 【注意判空分支是提前判断 没有if-else关系】 
    if (x < root->val) remove(root->left, x);//x小于根结点，x在左子树，去左子树删
    else if (x > root->val) remove(root->right, x);//x大于根结点值，x在右子树，
    else//找到x后：分类删除
    {
        if (!root->left && !root->right) root = NULL; //如果没有左右孩子，则为叶子结点，直接删除【root指针指向NULL】
        else if (!root->left) root = root->right;//如果左子树为空，把右子树填上来   ，往右找最右侧【取最大值】，
        else if (!root->right) root = root->left;//如果右子树为空，把左子树填上来 
        else//如果左右子树都有 【则把左子树最右侧的结点值替换删除结点，然后删除最右侧结点】
        {
            auto p = root->left; //替换法删除【保持左<父<右 && 中序遍历不变】
            while (p->right) p = p->right;//找左子树最右侧最大值，替换父结点，再删除最右侧结点
            root->val = p->val;
            remove(root->left, p->val);//删除左子树的最右侧结点，值为p->val
        }
    }
}

int get_pre(TreeNode* root, int x)//寻找前驱【找小于的最大值，不存在用-INF负无穷】 【查找不需要修改，不用加引用】 
{
    if (!root) return -INF;//找最大值，没有答案用-INF（负无穷） 
    if (root->val >= x) return get_pre(root->left, x);//值大于x，返回左子树的查找结果 
    return max(root->val, get_pre(root->right, x));//否则返回根的结果和右子树的值的max（看根有没有右子树，有则前驱为右子树的最右侧）
}

int get_suc(TreeNode* root, int x)//寻找后继   【找大于的最小值，不存在用INF正无穷】
{
    if (!root) return INF;//找最小值，没有答案用正无穷 
    if (root->val <= x) return get_suc(root->right, x); //值大于，往右子树找
    return min(root->val, get_suc(root->left, x));//返回根与其左子树min（若根有左子树则左子树作为后继，min=左子树）
}

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_suc(root, x) << endl;
    }

    return 0;
}