DS平衡二叉树练习AVL

题目描述
对二叉平衡树进行四种操作：
1 D K 表示插入一个新数据，数据为D用于输出，关键值为K用于排序；
2 输出当前树中最大关键值所带的数据，并删除该数据，如果没有这个关键值，则输出0；
3 输出当前树中最小关键值所带的数据，并删除该数据，如果没有这个关键值，则输出0；
4 K 输出关键值为 K 的数据，并删除该数据，如果没有这个关键值，则输出0。
要求必须实现平衡树，不可以使用各类库函数
AVL代码模板参考:

#include<stdio.h>
const int maxn = 1e5 + 10;
struct Node
{
    int key;        // 关键值
    int data;       // 携带的数据
    int left;       // 左子树地址（数组下标）
    int right;      // 右子树地址（数组下标）
    int height;     // 当前结点为根的子树高度
    void Init(){data = key = left = right = height = -1;}
    void Init(int k_, int d_=0){Init(); key = k_; data = d_;}
    Node(){Init();}
    Node(int k_, int d_=0){Init(k_, d_);}
};
 
Node tr[maxn];
int root, tp;  // root标记根节点位置，tp全局结点分配下标
 
inline int UpdateHeight(int now)
{
    // 更新 tr[now] 结点的子树高度，即tr[now].height的值
}
inline int HeightDiff(int now)
{
    // 计算 tr[now] 结点的平衡因子
}
int LL(int an)
{
}
int RR(int an)
{
}
int LR(int an)
{
}
int RL(int an)
{
}
void Insert(int &now, int key, int data=0)
{
    if(now == -1)
    {
        // 传入指针为空，新建结点保存数据
        now = ++ tp;
        tr[now].Init(key, data);
    }
    // 判断插入哪个子树，插入数据，判断平衡因子，做正确旋转，更新高度
}
void Delete(int &now, int key)
{
    if(now == -1) return;
    else if(key < tr[now].key) Delete(tr[now].left, key);
    else if(key > tr[now].key) Delete(tr[now].right, key);
    else
    {
        // 删除当前结点
    }
    // 处理树平衡
}
 
int main()
{
    int n, op, key, data;
    while(scanf("%d", &n) != EOF)
    {
        for(root = tp = -1; n --; )  // 初始化根结点和“内存指针”
        {
            scanf("%d", &op);
            if(op == 1)
            {
            }
            else if(op == 2)
            {
            }
            else if(op == 3)
            {
            }
            else
            {
            }
    }
    return 0;
}

输入
每组数据第一行n表示有n个操作
接下来n行操作内容
输出
按操作规则输出对应内容

测试样例：

8
2
1 20 14
1 30 3
2
1 10 99
3
2
2

输出：

0
20
30
10
0

• 建议你看下这篇博客👉 ：平衡二叉树AVL树