Morris' Blog

2011-07-09 17:21:26Morris

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

留言 0 收藏 0 推薦 0

作法 : 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;
}

上一篇：a175. 撒旦玩不玩骰子？ (SplayTree 版本)

下一篇：a181. 逆逆向思考

Morris' Blog

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

你可能感興趣的文章

為了過年剃的

大摩2025年十大意外美元貶值居首

耶誕節

苗栗竹南：獅山親子公園

急速關頭 Borning

Morris' Blog

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

你可能感興趣的文章

為了過年剃的

大摩2025年十大意外 美元貶值居首

耶誕節

苗栗竹南：獅山親子公園

急速關頭 Borning

大摩2025年十大意外美元貶值居首