/******************************************************************
题目： Double Queue(poj 3481)
链接： http://poj.org/problem?id=3481
算法： avl树(入门)
*******************************************************************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std; typedef struct Node ///树的节点
{
int val,data;
int h; ///以当前结点为根结点的数的高度
int bf; ///平衡因子（左子树高度与右子树高度之差）
Node *left,*right;
}Node; class AvlTree ///alv树,树中太多函数,用类来实现容易一些
{
private:
Node *root; ///树的根节点
public:
void Init() ///初始化树
{
root=NULL;
}
int Height(Node *T) ///取一个节点的高度
{
if (T==NULL) return ;
return T->h;
}
int Bf(Node *T) ///计算一个节点的平衡因子
{
if (T->left==T->right) return ;
if (T->left==NULL) return -(T->right->h); ///这里一定取负数(左子树高度与右子树高度之差)
if (T->right==NULL) return T->left->h;
return (T->left->h)-(T->right->h);
}
///四种旋转,不知为什么,自己多画一下就知道了。
Node *LL_rotate(Node *T) ///单向右旋平衡处理LL：由于在*T的左子树根结点的左子树上插入结点
{
Node *B=T->left;
T->left=B->right;
B->right=T;
T->h=max(Height(T->left),Height(T->right))+;
B->h=max(Height(B->left),Height(T->right))+;
T->bf=Bf(T);
B->bf=Bf(B);
return B;
}
Node *RR_rotate(Node *T) ///单向左旋平衡处理RR：由于在*T的右子树根结点的右子树上插入结点
{
Node *B=T->right;
T->right=B->left;
B->left=T;
T->h=max(Height(T->left),Height(T->right))+;
B->h=max(Height(B->left),Height(T->right))+;
T->bf=Bf(T);
B->bf=Bf(B);
return B;
}
Node *LR_rotate(Node *T) ///双向旋转平衡处理LR：由于在*T的左子树根结点的右子树上插入结点
{
T->left=RR_rotate(T->left);
T=LL_rotate(T);
return T;
}
Node *RL_rotate(Node *T) ///双向旋转平衡处理RL：由于在*T的右子树根结点的左子树上插入结点
{
T->right=LL_rotate(T->right);
T=RR_rotate(T);
return T;
}
void Insert(int v,int e) ///root是private,所以不能从主函数传入
{
Insert(root,v,e);
}
void Insert(Node *&T,int v,int e) ///插入新节点
{
if (T==NULL)
{
T=(Node *)malloc(sizeof(Node));
T->h=;
T->bf=;
T->val=v;
T->data=e;
T->left=T->right=NULL;
return ;
}
if (e<T->data) Insert(T->left,v,e);
else Insert(T->right,v,e);
T->h=max(Height(T->left),Height(T->right))+; ///计算节点高度
T->bf=Bf(T); ///计算平衡因子
if (T->bf>||T->bf<-) ///调整平衡,四种调整反法
{
if (T->bf>&&T->left->bf>) T=LL_rotate(T); ///如果T->bf > 1 则肯定有左儿子
if (T->bf<-&&T->right->bf<) T=RR_rotate(T); ///如果T->bf < -1 则肯定有右儿子
if (T->bf>1&&T->left->bf<0) T=LR_rotate(T);
if (T->bf<-1&&T->right>0) T=RL_rotate(T);
}
}
void Find(int flag) ///flag=1为找最大值，否则找最小值
{
if (root==NULL)
{
printf("0\n");
return ;
}
Node *temp=root;
if (flag) ///最大值一定最右边
{
while (temp->right)
temp=temp->right;
}
else
{
while (temp->left)
temp=temp->left;
}
printf("%d\n",temp->val);
Delete(root,temp->data); ///删除相应节点
}
void Delete(Node *&T,int e)
{
if (T==NULL) return ;
if (e<T->data) Delete(T->left,e);
else if (e>T->data) Delete(T->right,e);
else ///找到删除的节点
{
if (T->left&&T->right) ///删除的节点左右都还有节点
{
Node *temp=T->left; ///把左子树的最大值当做当前节点
while (temp->right) temp=temp->right; ///找最大值
T->val=temp->val;
T->data=temp->data;
Delete(T->left,temp->data); ///左子树最大值已近改为当前根节点，应该删除原来位置
}
else
{
Node *temp=T;
if (T->left) T=T->left; ///删除节点只存在左子树
else if (T->right) T=T->right; ///删除节点只有右子树
else ///删除节点没有孩子
{
free(T);
T=NULL;
}
if (T) free(temp);
return ;
}
}
T->h=max(Height(T->left),Height(T->right))+;
T->bf=Bf(T);
if (T->bf>||T->bf<-) ///删除后一定要调整
{
if (T->bf>&&T->left->bf>) T=LL_rotate(T);
if (T->bf<-&&T->right->bf<) T=RR_rotate(T);
if (T->bf>&&T->left->bf<) T=LR_rotate(T);
if (T->bf<-&&T->right>) T=RL_rotate(T);
}
}
void Free() ///由于内存是malloc出来的，最后一定要释放
{
FreeNode(root);
}
void FreeNode(Node *T)
{
if (T==NULL) return ;
if (T->right) FreeNode(T->right);
if (T->left) FreeNode(T->left);
free(T);
}
};
AvlTree T; int main()
{
T.Init();
int op;
while (~scanf("%d",&op)&&op)
{
if (op==)
{
int v,e;
scanf("%d%d",&v,&e);
T.Insert(v,e);
}
if (op==)
{
T.Find();
}
if (op==)
{
T.Find();
}
}
T.Free();
return ;
}