★实验任务
欢迎来到暴走数据结构，我是洪尼玛。今天，我们来玩 AVL 树，怎么玩呢？很简单：给 你 n 个数字，你需要按顺序插入一棵 AVL 树中，然后给你下面 3 个操作
- 操作 1：在 AVL 树中找到最大值，并输出它的值和所在节点的深度，然后删除该节点， 如果树为空树，则输出-1
- 操作 2：在 AVL 树中找到最小值，并输出它的值和所在节点的深度，然后删除该节点， 如果树为空树，则输出-1
- 操作 3：在 AVL 树中插入一个数 X 因为我不会 AVL 树，所以希望聪明的你们来帮我完成这个任务
★数据输入
输入第一个数为 n（n≤100000）表示数字的个数
接下来一行输入 n 个数，范围在 1 到 n 之间，每个数只出现一次
第三行输入一个数 m（m≤100000）表示需要进行操作的次数
接下来 m 行，每行输入第一个数为 op 表示执行操作的编号，若 op 等于 1 或 2，输出最大值 或最小值的大小和所在节点的深度；若 op 等于 3，接着输入一个数 X（X≤n），并将 X 插入 AVL 树中，数据保证当前 AVL 树中不存在 X 这个数
★数据输出
| 输入示例 | 输出示例 |
|---|---|
| 6 1 2 3 4 5 6 5 1 2 3 6 1 1 |
6 3 1 3 6 3 5 2 |
★提示
输出行末不能有空格
对于 50%的数据，1<=n<=100，1<=m<=100
对于 100%的数据，1<=n<=100000，1<=m<=100000
★思路
avl树操作
博客讲解
★Code
#include<stdio.h>
#include<iostream>
using namespace std;
int deep[100005]={0};
int arr[100005] = {0};
int de = 1;
struct Node
{
Node(int _data) :data(_data), hight(1), left(NULL), right(NULL) {}
int hight;
int data;
Node *left;
Node *right;
};
int max(int x, int y)
{
return x > y ? x : y;
}
int get_hight(Node *p)
{
if (p == NULL)
{
return 0;
}
else
return p->hight;
}
Node* right_right_rotation(Node* k1)
{
Node* k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->hight = max(get_hight(k1->left), get_hight(k1->right)) + 1;
k2->hight = max(get_hight(k2->right), k1->hight) + 1;
return k2;
}
Node* left_left_rotation(Node* k2)
{
Node* k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->hight = max(get_hight(k2->left), get_hight(k2->right)) + 1;
k1->hight = max(get_hight(k1->left), k2->hight) + 1;
return k1;
}
Node* right_left_rotation(Node* k3)
{
k3->left = right_right_rotation(k3->left);
return left_left_rotation(k3);
}
Node* left_right_rotation(Node* k1)
{
k1->right = left_left_rotation(k1->right);
return right_right_rotation(k1);
}
Node* Insert(Node *p, int value)
{
if (value < p->data)
{
if (p->left == NULL)
{
p->left = new Node(value);
p->hight = max(get_hight(p->left), get_hight(p->right)) + 1;
return p;
}
else
{
p->left = Insert(p->left, value);
p->hight = max(get_hight(p->left), get_hight(p->right)) + 1;
}
if (get_hight(p->left) - get_hight(p->right) == 2)
{
if (value < p->left->data)
p = left_left_rotation(p);
else
p = right_left_rotation(p);
}
}
if (value > p->data)
{
if (p->right == NULL)
{
p->right = new Node(value);
p->hight = max(get_hight(p->left), get_hight(p->right)) + 1;
return p;
}
else
{
p->right = Insert(p->right, value);
p->hight = max(get_hight(p->left), get_hight(p->right)) + 1;
}
if (get_hight(p->right) - get_hight(p->left) == 2)
{
if (value > p->right->data)
p = right_right_rotation(p);
else
p = left_right_rotation(p);
}
}
return p;
}
void search(Node* p)
{
if(p->left==NULL&&p->right==NULL)
{
deep[p->data] = de;
de--;
return ;
}
if(p->left!=NULL)
{
deep[p->data] = de;
de++;
search(p->left);
}
if(p->right!=NULL)
{
deep[p->data] = de;
de++;
search(p->right);
}
de--;
}
int main()
{
int n;
int temp;
int i;
scanf("%d",&n);
scanf("%d",&i);
arr[1] = i;
Node * tree = new Node(i);
for ( i = 2; i <= n; i++)
{
scanf("%d",&temp);
arr[i] = temp;
tree = Insert(tree, temp);
}
search(tree);
for(i=1;i<=n;i++)
{
printf("%d",deep[arr[i]]);
if(i<n)
printf(" ");
}
return 0;
}