84分RE求调

#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

typedef struct Node
{
    int hei, siz, fre, dat;
    Node *ls, *rs;
    char las;//回溯过程是从左儿子还是右儿子
    Node()
    {
        hei = siz = fre = 1;
        ls = rs = NULL;
        dat = 0;
        las = 0;
    }

    void update()
    {
        int tp1 = 0, tp2 = 0;
        if(ls) tp1 = ls -> hei;
        if(rs) tp2 = rs -> hei;
        hei = max(tp1, tp2) + 1;//高度更新
        siz = fre;
        if(ls) siz += ls -> siz;
        if(rs) siz += rs -> siz;
        //树的大小更新
    }

    int bal()
    {//求当前节点的平衡因子 
        // if(!p) return 0;
        // return p -> hei;
        int ans = 0;
        if(ls) ans += ls -> hei;
        if(rs) ans -= rs -> hei;
        return ans;
    }
}Node;

int ges(Node*);//得到树的大小
int geh(Node*);//得到树的高度

Node *root;

int ges(Node *p)
{
    if(!p) return 0;
    return p -> siz;
}

int geh(Node *p)
{
    if(!p) return 0;
    return p -> hei;
}

enum rot_type { L = 1, R = 0 };

void rotatee(Node *&rot, rot_type tp)
{//单次旋转
    if(tp == L)
    {//左旋转
        auto tp = rot -> rs;
        rot -> rs = tp -> ls;
        tp -> ls = rot;
        rot = tp;
        rot -> ls -> update();
        rot -> update();
    }
    else
    {//右旋转
        auto tp = rot -> ls;
        rot -> ls = tp -> rs;
        tp -> rs = rot;
        rot = tp;
        rot -> rs -> update(); 
        rot -> update();
    }
    rot -> update();
}

void rotate(Node *&rot)
{
    if(rot -> las == 'l')
    {
        if(rot -> ls -> las == 'l')
        {//右单旋转
            rotatee(rot, R);
        }
        else
        {//左右双旋转
            rotatee(rot -> ls, L);
            rotatee(rot, R);
        }
    }
    else if(rot -> las == 'r')
    {
        if(rot -> rs -> las == 'r')
        {//左单旋转
            rotatee(rot, L);
        }
        else
        {//右左双旋转
            rotatee(rot -> rs, R);
            rotatee(rot, L);
        }
    }
    else exit(-1);
}

void insert(Node *&rt, int x)
{//插入一个数
    if(!rt)
    {
        rt = (Node *) malloc(sizeof(Node));
        rt -> dat = x;
        rt -> hei = rt -> siz = rt -> fre = 1;
        rt -> ls = rt -> rs = NULL;
        rt -> las = 0;
        return;
    }
    if(rt -> dat > x)
    {//往左边找
        insert(rt -> ls, x);
        rt -> las = 'l';
        rt -> update();
        if(rt -> bal() == 2) rotate(rt);
    }
    else if(rt -> dat < x)
    {//往右边找
        insert(rt -> rs, x);
        rt -> las = 'r';
        rt -> update();
        if(rt -> bal() == -2) rotate(rt);
    }
    else
    {
        rt -> fre ++;
        rt -> update();
    }
}

void del(Node *&rt, int x)
{
    if(!rt) return;//表示没有这一个数字
    if(rt -> dat < x)
    {
        del(rt -> rs, x);
        rt -> las = 'r';
        rt -> update();
        if(rt -> bal() == 2)
        {//左侧数目大
            if(geh(rt -> ls -> ls) >= geh(rt -> ls -> rs)) rotatee(rt, R);
            else
            {
                rotatee(rt -> ls, L);
                rotatee(rt, R);
            }
        }
    }
    else if(rt -> dat > x)
    {
        del(rt -> ls, x);
        rt -> las = 'l';
        rt -> update();
        if(rt -> bal() == -2)
        {
            if(geh(rt -> rs -> ls) <= geh(rt -> rs -> rs)) rotatee(rt, L);
            else
            {
                rotatee(rt -> rs, R);
                rotatee(rt, L);
            }
        }
    }
    else
    {
        if(rt -> fre != 1)
        {//表示重复多少个
            rt -> fre --;
            rt -> update();
            return;
        }
        //表示是单独的一个点
        if(rt -> ls && rt -> rs)
        {//既有左孩子又有右孩子，找到左孩子里面最大的替代这一个然后进行删除
            auto tmp = rt -> ls;
            while(tmp -> rs)
                tmp = tmp -> rs;
            swap(tmp -> fre, rt -> fre);
            swap(tmp -> dat, rt -> dat);//交换数据，整个树不变
            del(rt -> ls, x);
        }
        else if(rt -> ls)
        {//只有左孩子
            auto tmp = rt;
            rt = rt -> ls;
            free(tmp);
        }
        else if(rt -> rs)
        {
            auto tmp = rt;
            rt = rt -> rs;
            free(tmp);
        }
        else
        {//叶子节点
            auto tmp = rt;
            free(tmp);
            rt = NULL;
        }
        
    }
    if (rt != NULL) rt -> update();
    //删除节点这里不可能平衡因子的abs=2的情况
}

int findth(Node *rt, int x)
{//找到x是第几位
    if(!rt) exit(-1);//表示根本没有这个数字
    if(rt -> dat > x) 
        return findth(rt -> ls, x);
    else if(rt -> dat < x)
        return findth(rt -> rs, x) + ges(rt -> ls) + rt -> fre;
    else return ges(rt -> ls) + 1;
}

int findx(Node *rt, int th)
{
    if(!rt) exit(-1);
    if(th > ges(rt -> ls))
    {//如果th大于左侧所有的个数 
        if(th - ges(rt -> ls) <= rt -> fre) return rt -> dat;
        else return findx(rt -> rs, th - ges(rt -> ls) - rt -> fre);
    }
    else
        return findx(rt -> ls, th);
}

int maxx, minn;

void findpre(Node *rt, int x)
{//找到x的前驱 
    if(!rt) return;
    if(rt -> dat < x)
    {
        maxx = max(rt -> dat, maxx);
        findpre(rt -> rs, x);
    }
    else if(rt -> dat > x)
        findpre(rt -> ls, x);
    else
    {//找到了这个点
        auto tmp = rt -> ls;
        while(tmp)
        {
            maxx = max(tmp -> dat, maxx);
            tmp = tmp -> rs;
        }
    }
}

void findnex(Node *rt, int x)
{
    if(!rt) return;
    if(rt -> dat > x)
    {
        minn = min(minn, rt -> dat);
        findnex(rt -> ls, x);
    }
    else if(rt -> dat < x)
        findnex(rt -> rs, x);
    else
    {//找到了这个点
        auto tmp = rt ->rs;
        while(tmp)
        {
            minn = min(tmp -> dat, minn);
            tmp = tmp -> ls;
        }
    }
}

void bfs()
{
	queue <Node *> que;
	if(!root) return;
	que.push(root);
	cout << "BFS:";
	while(!que.empty())
	{
		auto tp = que.front();
		cout << tp -> dat << ' ';
		if(tp -> ls) que.push(tp -> ls);
		if(tp -> rs) que.push(tp -> rs);
		que.pop();
	}
	cout << endl;
	return;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int opt, x;
        cin >> opt >> x;
        switch (opt)
        {
            case 1://插入x
                insert(root, x);
                break;
            
            case 2://删除x
                del(root, x);
                break;

            case 3://查询x的排名
                cout << findth(root, x) << endl;
                break;

            case 4://查询排名为x的数字
                cout << findx(root, x) << endl;
                break;

            case 5://x前驱
                maxx = -10000010;
                findpre(root, x);
                cout << maxx << endl;
                break;
            
            case 6://x后继
                minn = 10000010;
                findnex(root, x);
                cout << minn << endl;
                break;

            default:
                exit(-1);
                break;
        }
        // bfs(); 
    }
    return 0;
}