rendered paste body#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct pkt pkt;
struct pkt {
int klucz, waga, pod, height;
char dane[30];
pkt * parent;
pkt * left, * right;
};
pkt * root;
void ins (int , char *);
void del(int);
inline int max (int, int);
pkt * search(pkt *, int);
void balance(pkt *);
void LL(pkt *,pkt *,pkt *);
void LD(pkt *,pkt *,pkt *);
void RR(pkt *,pkt *,pkt *);
void RD(pkt *,pkt *,pkt *);
int zief;
pkt * H (pkt *, int);
int G(pkt *, int);
void validiate(pkt *);
int main()
{
#ifndef ONLINE_JUDGE
freopen("all-small.in","r",stdin);
//freopen("out.txt", "w", stdout);
#endif
char cmd, danee[30], terminate, linia[100];
int klucz, order, adsf, n;
pkt * tmp, * tmp2;
while(1) {
gets(linia);
if (linia[0] == 'I')
sscanf(linia, "%*c %d %s", &klucz, danee);
else
sscanf(linia, "%*c %d", &klucz);
if (feof(stdin)!=0) break;
zief++;
if (linia[0] == 'I') {
ins(klucz , danee);
//validiate(root);
} else
if (linia[0] == 'D') {
del(klucz);
} else
if (linia[0] == 'S') {
tmp = search(root, klucz);
if (tmp) {
printf("%d %s\n", tmp->klucz, tmp->dane);
} else
printf("-\n");
} else
if (linia[0] == 'N') {
adsf = G(root, klucz);
if (adsf) {
tmp = H(root, adsf+1);
if (tmp)
printf("%d %s\n", tmp->klucz, tmp->dane);
else
printf("-\n");
} else {
printf("-\n");
}
} else
if (linia[0] == 'P') {
adsf = G(root, klucz);
if (adsf) {
tmp = H(root, adsf-1);
if (tmp)
printf("%d %s\n", tmp->klucz, tmp->dane);
else
printf("-\n");
} else {
printf("-\n");
}
} else
if (linia[0] == 'G') {
adsf = G(root, klucz);
if (adsf)
printf("%d\n", adsf);
else
printf("-\n");
} else
if (linia[0] == 'H') {
tmp = H(root, klucz);
if (tmp)
printf("%d %s\n", tmp->klucz, tmp->dane);
else
printf("-\n");
}
}
return 0;
}
void ins (int id, char * danea) {
int n;
pkt * tmp, **tmp2;
if (!root) {
root = (pkt*)malloc(sizeof(pkt));
n = 0;
while(danea[n]!=0) {root->dane[n] = danea[n]; n++;} root->dane[n]=0;
root->klucz = id;
root->parent = 0;
root->left = 0;
root->right = 0;
root->pod = 0;
root->height = 1;
} else {
tmp = root;
while (1) {
if (tmp->klucz == id) {
return;
}
if (tmp->klucz > id) {
if (tmp->left == NULL) {
tmp2 = &tmp->left;
break;
}
tmp = tmp->left;
} else {
if (tmp->right == NULL) {
tmp2 = &tmp->right;
break;
}
tmp = tmp->right;
}
}
(*tmp2) = (pkt*)malloc(sizeof(pkt));
n = 0; while(danea[n]!=0) {(*tmp2)->dane[n] = danea[n]; n++;} (*tmp2)->dane[n]=0;
(*tmp2)->klucz = id;
(*tmp2)->parent = tmp;
(*tmp2)->left = 0;
(*tmp2)->right = 0;
(*tmp2)->pod = 0;
(*tmp2)->height = 1;
tmp = (*tmp2)->parent;
while(tmp) {
tmp->pod = 0;
if (tmp->right) tmp->pod +=(tmp->right)->pod+1;
if (tmp->left) tmp->pod +=(tmp->left)->pod+1;
tmp = tmp->parent;
}
tmp = (*tmp2)->parent;
while (tmp) {
tmp->height = max(((tmp->left) ? (tmp->left)->height : 0 ) , ((tmp->right) ? (tmp->right)->height : 0 ))+1;
n = abs( ((tmp->left) ? (tmp->left)->height : 0 ) - ((tmp->right) ? (tmp->right)->height : 0 ));
if ( (n&1)==0) {
balance(tmp);
break;
}
tmp = tmp->parent;
}
}
}
void del (int id) {
pkt * tmp, * tmp2=0, * tmp3, * tmp4;
pkt ** strona;
pkt * parent;
int n;
if (!root) return;
tmp = search(root, id);
if (tmp) {
parent = tmp->parent;
if (tmp!=root) {
if ((tmp->parent)->left == tmp)
strona = &(tmp->parent)->left;
else
strona = &(tmp->parent)->right;
} else strona = 0;
if (tmp->left == 0 && tmp->right == 0) {
if (strona) {
*strona = 0;
} else {
root = 0;
}
tmp3 = tmp->parent;
}
else if (tmp->left == 0) {
if (strona) {
*strona = tmp->right;
} else {
root = tmp->right;
}
(tmp->right)->parent = tmp->parent;
tmp3 = tmp->parent;
} else if (tmp->right == 0) {
if (strona) {
*strona = tmp->left;
} else
root = tmp->left;
(tmp->left)->parent = tmp->parent;
tmp3 = tmp->parent;
} else {
if ((tmp->right)->left) {
tmp2 = tmp->right;
while(tmp2->left) {
tmp2 = tmp2->left;
}
if (tmp2->right) {
(tmp2->right)->parent = tmp2->parent;
(tmp2->parent)->left = tmp2->right;
} else {
(tmp2->parent)->left = 0;
}
tmp3 = tmp2->parent;
if (!strona) root = tmp2;
tmp2->parent = tmp->parent;
if (strona) *strona = tmp2;
tmp2->left = tmp->left;
(tmp2->left)->parent = tmp2;
tmp2->right = tmp->right;
(tmp2->right)->parent = tmp2;
} else {
tmp2 = tmp->right;
tmp3 = tmp2;
tmp2->parent = tmp->parent;
*strona = tmp2;
tmp2->left = tmp->left;
(tmp2->left)->parent = tmp2;
tmp2->height = max(((tmp2->left) ? (tmp2->left)->height : 0 ) , ((tmp2->right) ? (tmp2->right)->height : 0 ))+1;
tmp2->pod = ((tmp2->left) ? tmp2->left->pod+1 : 0) + ((tmp2->right) ? tmp2->right->pod+1 : 0);
}
}
tmp = tmp3;
while(tmp) {
tmp->pod = ((tmp->left) ? tmp->left->pod+1 : 0) + ((tmp->right) ? tmp->right->pod+1 : 0);
tmp = tmp->parent;
}
while(tmp3) {
tmp3->height = max(((tmp3->left) ? (tmp3->left)->height : 0 ) , ((tmp3->right) ? (tmp3->right)->height : 0 ))+1;
n = abs( ((tmp3->left) ? (tmp3->left)->height : 0 ) - ((tmp3->right) ? (tmp3->right)->height : 0 ) );
if ( (abs( ((tmp3->left) ? (tmp3->left)->height : 0 ) - ((tmp3->right) ? (tmp3->right)->height : 0 ) )&1)==1) {
break;
} else {
tmp4 = tmp3->parent;
if (n!=0) {
balance(tmp3);
}
tmp3 = tmp4;
}
}
if (tmp2) {
tmp2->height = max(((tmp2->left) ? (tmp2->left)->height : 0 ) , ((tmp2->right) ? (tmp2->right)->height : 0 ))+1;
tmp2->pod = ((tmp2->left) ? tmp2->left->pod+1 : 0) + ((tmp2->right) ? tmp2->right->pod+1 : 0);
}
free(tmp);
}
}
pkt * search(pkt * tmp, int id) {
if (tmp==0 || tmp->klucz == id) return tmp;
if (tmp->klucz > id)
return search(tmp->left, id);
else return search(tmp->right, id);
}
void balance (pkt * a) {
pkt * b, * c;
int tmp;
tmp = ((a->right) ? (a->right)->height : 0 ) - ((a->left) ? (a->left)->height : 0 );
if (tmp == 2) {
b = a->right;
tmp = ((b->right) ? (b->right)->height : 0 ) - ((b->left) ? (b->left)->height : 0 );
if (tmp == -1) {
c = b->left;
LD(a,b,c);
} else {
c = b->right;
LL(a,b,c);
}
} else if (tmp == -2) {
b = a->left;
tmp = ((b->right) ? (b->right)->height : 0 ) - ((b->left) ? (b->left)->height : 0 );
if (tmp == -1 || tmp == 0) {
c = b->left;
RR(a,b,c);
} else {
c = b->right;
RD(a,b,c);
}
}
}
void LL(pkt * a, pkt * b, pkt * c) {
a->right = b->left;
if (b->left) {
(b->left)->parent = a;
}
if (!a->parent) root = b;
b->parent = a->parent;
if (a->parent) {
if ((a->parent)->left == a) (a->parent)->left = b;
else (a->parent)->right = b;
}
b->left = a;
a->parent = b;
a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;
b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;
a->pod = 0;
if (a->right) a->pod += (a->right)->pod+1;
if (a->left) a->pod += (a->left)->pod+1;
b->pod = 0;
if (b->right) b->pod += (b->right)->pod+1;
if (b->left) b->pod += (b->left)->pod+1;
c->pod = 0;
if (c->right) c->pod += (c->right)->pod+1;
if (c->left) c->pod += (c->left)->pod+1;
}
void RR(pkt * a, pkt * b, pkt * c) {
a->left = b->right;
if (b->right) (b->right)->parent = a;
if (!a->parent) root = b;
b->parent = a->parent;
if (a->parent) {
if ((a->parent)->left == a) (a->parent)->left = b;
else (a->parent)->right = b;
}
b->right = a;
a->parent = b;
a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;
b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;
a->pod = 0;
if (a->right) a->pod += (a->right)->pod+1;
if (a->left) a->pod += (a->left)->pod+1;
b->pod = 0;
if (b->right) b->pod += (b->right)->pod+1;
if (b->left) b->pod += (b->left)->pod+1;
c->pod = 0;
if (c->right) c->pod += (c->right)->pod+1;
if (c->left) c->pod += (c->left)->pod+1;
}
void LD(pkt * a, pkt * b, pkt * c) {
a->right = c;
c->parent = a;
b->left = c->right;
if (c->right) (c->right)->parent = b;
c->right = b;
b->parent = c;
a->right = c->left;
if (c->left)(c->left)->parent = a;
if (!a->parent) root = c;
c->parent = a->parent;
if (a->parent) {
if ((a->parent)->left == a) (c->parent)->left = c;
else (c->parent)->right = c;
}
c->left = a;
a->parent = c;
a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;
c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;
a->pod = 0;
if (a->right) a->pod += (a->right)->pod+1;
if (a->left) a->pod += (a->left)->pod+1;
b->pod = 0;
if (b->right) b->pod += (b->right)->pod+1;
if (b->left) b->pod += (b->left)->pod+1;
c->pod = 0;
if (c->right) c->pod += (c->right)->pod+1;
if (c->left) c->pod += (c->left)->pod+1;
}
void RD(pkt * a, pkt * b, pkt * c) {
a->left = c;
c->parent = a;
b->right = c->left;
if (c->left) (c->left)->parent = b;
c->left = b;
b->parent = c;
a->left = c->right;
if (c->right) (c->right)->parent = a;
if (!a->parent) root = c;
c->parent = a->parent;
if (a->parent) {
if ((a->parent)->left == a) (c->parent)->left = c;
else (c->parent)->right = c;
}
c->right = a;
a->parent = c;
a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;
c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;
a->pod = 0;
if (a->right) a->pod += (a->right)->pod+1;
if (a->left) a->pod += (a->left)->pod+1;
b->pod = 0;
if (b->right) b->pod += (b->right)->pod+1;
if (b->left) b->pod += (b->left)->pod+1;
c->pod = 0;
if (c->right) c->pod += (c->right)->pod+1;
if (c->left) c->pod += (c->left)->pod+1;
}
inline int max (int a, int b) {
return ((a>b) ? a : b);
}
void validiate(pkt * x) {
if (x!=0) {
validiate(x->left);
if (x->left && x->klucz != ((x->left)->parent)->klucz) {
printf("Err: Lewe dziecko %d %d\n", x->left->klucz, (x->left)->parent->klucz);
return;
}
if (x->right && x->klucz != ((x->right)->parent)->klucz){
printf("Err: Prawe dziecko\n");
return;
}
if (x->parent) {
if ((x->parent)->left == x) {
if (((x->parent)->left)->klucz != x->klucz) {
printf("Err: Parent nie pokazuje na dziecko\n");
return;
}
} else if ((x->parent)->right == x) {
if (((x->parent)->right)->klucz != x->klucz) {
printf("Err: Parent nie pokazuje na dziecko\n");
return;
}
} else {
printf("Err: Parent nie pokazuje na dziecko\n");
return;
}
}
if ( abs( ((x->left) ? (x->left)->height : 0) - ((x->right) ? (x->right)->height : 0) ) > 1 || x->height != max(((x->left) ? (x->left)->height : 0 ) , ((x->right) ? (x->right)->height : 0 ))+1) {
printf("Err: waga\n");
return;
}
if (x->pod != ((x->left) ? (x->left)->pod+1 : 0)+((x->right) ? (x->right)->pod+1 : 0)) {
printf("Err: wzbogacanie\n");
return;
}
validiate(x->right);
}
}
pkt * H (pkt * tmp, int klucz) {
int order = 0;
while(tmp) {
if (order+((tmp->left) ? (tmp->left)->pod+1 : 0)+1 > klucz) {
tmp = tmp->left;
} else {
order+= ((tmp->left) ? (tmp->left)->pod+1 : 0)+1;
if (order == klucz) break;
tmp = tmp->right;
}
}
if (tmp)
return tmp;
else
return 0;
}
int G(pkt * tmp, int klucz) {
int order = 0;
while(tmp) {
if (tmp->klucz == klucz) {
if (tmp->left) {
order+= (tmp->left)->pod+2;
} else {
order+=1;
}
break;
}
if (tmp->klucz < klucz) {
if (tmp->left) {
order+= (tmp->left)->pod+2;
} else {
order+=1;
}
tmp = tmp->right;
} else {
tmp = tmp->left;
}
}
if (tmp)
return order;
else
return 0;
}