2011-07-09 17:21:26Morris

a175. 撒旦玩不玩骰子? (AVLTree 版本)

作法 : AVL Tree
/**********************************************************************************/
/*  Problem: a175 "撒旦玩不玩骰子?" from Hash Table                      */
/*  Language: C                                                                   */
/*  Result: AC (272ms, 815KB) on ZeroJudge                                        */
/*  Author: morris1028 at 2011-07-13 20:31:51                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
#define IsLc(X) ((X) == (X)->p->lc)
#define IsRc(X) ((X) == (X)->p->rc)
typedef struct AVLNode {
    int v;
    short h;
    struct AVLNode *p, *lc, *rc;
}AVLNode;
typedef struct AVLTree{
    struct AVLNode *NIL, *root;
}AVLTree;
short Max(short, short);
short Height(AVLTree*, AVLNode*);

AVLNode *AVLMax(AVLTree*, AVLNode*);
AVLNode *AVLMin(AVLTree*, AVLNode*);
AVLNode *AVLFind(AVLTree*, int);
AVLNode *AVLLL(AVLTree*, AVLNode*);
AVLNode *AVLRR(AVLTree*, AVLNode*);
AVLNode *AVLLR(AVLTree*, AVLNode*);
AVLNode *AVLRL(AVLTree*, AVLNode*);

void AVLinit(AVLTree*);
void AVLFree(AVLTree*, AVLNode*);
void AVLPrint(AVLTree*, AVLNode*);
void AVLBalance(AVLTree*, AVLNode*, AVLNode*);
void InsAVL(AVLTree*, int);
void DelAVL(AVLTree*, int);

short Max(short x, short y) {
    return x > y ? x : y;
}
short Height(AVLTree *tree, AVLNode *node) {
    if(node == tree->NIL)    return -1;
    return node->h;
}
void AVLinit(AVLTree *tree) {
    tree->NIL = (AVLNode*)malloc(sizeof(AVLNode));
    tree->root = tree->NIL->p = tree->NIL->lc = tree->NIL->rc = tree->NIL;
}
void AVLFree(AVLTree *tree, AVLNode *now) {
    if(now == tree->NIL)    return;
    if(now->lc != tree->NIL)    AVLFree(tree, now->lc);
    if(now->rc != tree->NIL)    AVLFree(tree, now->rc);
    free(now);
}
void AVLPrint(AVLTree *tree, AVLNode *now) {
    if(now == tree->NIL)    return;
    if(now->lc != tree->NIL)    AVLPrint(tree, now->lc);
    printf("%d -> ", now->v);
    if(now->rc != tree->NIL)    AVLPrint(tree, now->rc);
}
AVLNode *AVLMax(AVLTree *tree, AVLNode *node) {/*Max node*/
    if(node == tree->NIL || node->rc == tree->NIL)    return node;
    return AVLMax(tree, node->rc);
}
AVLNode *AVLMin(AVLTree *tree, AVLNode *node) {/*Min node*/
    if(node == tree->NIL || node->lc == tree->NIL)    return node;
    return AVLMin(tree, node->lc);
}
AVLNode *AVLLL(AVLTree *tree, AVLNode *node) {
    if(node == tree->NIL)    return tree->NIL;
    AVLNode *lc = node->lc;
    if(node->p != tree->NIL) {
        if(IsLc(node))    node->p->lc = lc;
        else    node->p->rc = lc;
    }
    node->lc = lc->rc;
    lc->rc = node;
    lc->p = node->p;
    node->p = lc;
    node->lc->p = node;
    node->h = Max(Height(tree, node->lc), Height(tree, node->rc))+1;
    lc->h = Max(Height(tree, lc->lc), Height(tree, lc->rc))+1;
  
    if(lc->p == tree->NIL)    tree->root = lc;
  
    return lc;
}
AVLNode *AVLRR(AVLTree *tree, AVLNode *node) {
    if(node == tree->NIL) return tree->NIL;
    AVLNode *rc = node->rc;
    if(node->p != tree->NIL) {
        if(IsRc(node))    node->p->rc = rc;
        else    node->p->lc = rc;
    }
    node->rc = rc->lc;
    rc->lc = node;
    rc->p = node->p;
    node->p = rc;
    node->rc->p = node;
    node->h = Max(Height(tree, node->lc), Height(tree, node->rc))+1;
    rc->h = Max(Height(tree, rc->lc), Height(tree, rc->rc))+1;
  
    if(rc->p == tree->NIL)    tree->root = rc;
  
    return rc;
}
AVLNode *AVLLR(AVLTree *tree, AVLNode *node) {
    node->lc = AVLRR(tree, node->lc);
    return AVLLL(tree, node);
}
AVLNode *AVLRL(AVLTree *tree, AVLNode *node) {
    node->rc = AVLLL(tree, node->rc);
    return AVLRR(tree, node);
}
void AVLBalance(AVLTree *tree, AVLNode *node, AVLNode *dest) {
    if(node == dest)    return;
    while(node != dest) {/*node == root*/
        if(Height(tree, node->lc) - Height(tree, node->rc) == 2) {
            if(Height(tree, node->lc->lc) >= Height(tree, node->lc->rc))
                node = AVLLL(tree, node);
            else    node = AVLLR(tree, node);
            node->h = Max(Height(tree, node->lc), Height(tree, node->rc))+1;
        }
        else if(Height(tree, node->rc) - Height(tree, node->lc) == 2) {
            if(Height(tree, node->rc->rc) >= Height(tree, node->rc->lc))
                node = AVLRR(tree, node);
            else node = AVLRL(tree, node);
            node->h = Max(Height(tree, node->lc), Height(tree, node->rc))+1;
        }
        else {
            node->h = Max(Height(tree, node->lc), Height(tree, node->rc))+1;
            node = node->p;
        }
    }
}
void InsAVL(AVLTree *tree, int key) {
    AVLNode *curr = tree->root, *prev = tree->NIL;
    while(curr != tree->NIL) {
        prev = curr;
        if(curr->v > key)    curr = curr->lc;
        else if(curr->v < key)    curr = curr->rc;
        else return;
    }
    curr = (struct AVLNode*)malloc(sizeof(struct AVLNode));
    curr->v = key, curr->p = prev, curr->h = 0;
    curr->lc = curr->rc = tree->NIL;
  
    if(prev == tree->NIL)    tree->root = curr;
    else if(prev->v > key)    prev->lc = curr;
    else    prev->rc = curr;
    AVLBalance(tree, curr, tree->NIL);
}

void DelAVL(AVLTree *tree, int key) {
    AVLNode *node = AVLFind(tree, key);
    if(node == tree->NIL)    return;
    AVLNode *temp = AVLMin(tree, node->rc);
    if(temp == tree->NIL) {
        AVLNode *tmpp = node->p;
        if(node->p == tree->NIL) tree->root = node->lc;
        if(IsLc(node))    node->p->lc = node->lc;
        else    node->p->rc = node->lc;
        node->p->h = Max(Height(tree, node->p->lc), Height(tree, node->p->rc))+1;
        node->lc->p = node->p;
        AVLBalance(tree, tmpp, tree->NIL);
    }
    else {
        AVLNode *tmpp = temp->p;       
        if(node->p == tree->NIL) tree->root = temp;
        if(IsLc(node))    node->p->lc = temp;
        else    node->p->rc = temp;
        if(temp != node->rc) {
            temp->rc->p = temp->p;
            temp->p->lc = temp->rc;
            temp->rc = node->rc;
            node->rc->p = temp;
        }
        node->lc->p = temp;
        temp->lc = node->lc, temp->p = node->p;
        if(tmpp != node)    AVLBalance(tree, tmpp, tree->NIL);
    }
    free(node);
}
AVLNode *AVLFind(AVLTree *tree, int key) {
    AVLNode *curr = tree->root;
    while(curr != tree->NIL) {
        if(curr->v > key)    curr = curr->lc;
        else if(curr->v < key)    curr = curr->rc;
        else return curr;
    }
    return tree->NIL;
}
main() {
    int a, k, n, op, Mod;
    while(scanf("%d %d", &k, &Mod) == 2) {
        AVLTree Tree[Mod];
        for(a = 0; a < Mod; a++)    AVLinit(&Tree[a]);
        while(k--) {
            scanf("%d", &op);
            switch(op) {
                case 1:scanf("%d", &n);
                        InsAVL(&Tree[n%Mod], n);break;
                case 2:scanf("%d", &n);
                        DelAVL(&Tree[n%Mod], n);break;
                case 3:{
                    puts("===== s =====");
                    for(a = 0; a < Mod; a++) {
                        printf("[%03d]:", a); AVLPrint(&Tree[a], Tree[a].root);
                        puts("NULL");
                    }
                    puts("===== e =====");
                    break;
                }
            }
        }
        for(a = 0; a < Mod; a++)    AVLFree(&Tree[a], Tree[a].root);
    }
    return 0;
}