ABBxAVL.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
int c = 1, w = 1;
typedef struct binary_tree{
    int item;
    int h;
    struct binary_tree *left;
    struct binary_tree *right;
}binary_tree;
binary_tree * create_empty_tree(){
    return NULL;
}
binary_tree *create_tree(int item, binary_tree *left, binary_tree *right){
binary_tree *new_tree = (binary_tree*) malloc(sizeof(binary_tree));
new_tree->item = item;
new_tree->left = left;
new_tree->right = right;
return new_tree;
}
void print_in_order(binary_tree *bt){
    if(bt != NULL){
        print_in_order(bt->left);
        printf("%d\n" , bt->item);
        print_in_order(bt->right);
    }
}
void print_pre_order(binary_tree *bt){
    if(bt != NULL){
        printf("%d\n", bt->item);
        print_pre_order(bt->left);
        print_pre_order(bt->right);
    }
}
void print_post_order(binary_tree *bt){
    if(bt != NULL){
        print_post_order(bt->left);
        print_post_order(bt->right);
        printf("%d\n", bt->item);
    }
}
int search_abb(binary_tree *bt, int item){
    if((bt == NULL) || (bt->item == item)){
        return c;
    } else if(bt->item > item){
        c = c + 1;
        return search_abb(bt->left, item);
    } else{
        c = c + 1;
        return search_abb(bt->right, item);
    }
}
binary_tree *add_abb(binary_tree *bt, int item){
    if(bt == NULL){
        bt = create_tree(item, NULL, NULL);
    } else if(bt->item > item){
        bt->left = add_abb(bt->left, item);
    } else{
        bt->right = add_abb(bt->right, item);
    }
    return bt;
}
int balance_factor(binary_tree *bt){
    if(bt == NULL){
        return 0;
    }else if((bt->left != NULL) && (bt->right != NULL)){
        return (bt->left->h - bt->right->h);
    }else if((bt->left != NULL) && (bt->right == NULL)){
        return (1 + bt->left->h);
    }else{
        return (-bt->right->h - 1);
    }
}
int max(int a, int b){
    return (a > b) ? a : b;
}
int h(binary_tree *bt){
    if(bt == NULL){
        return -1;
    } else{
        return 1 + max(h(bt->left), h(bt->right));
    }
}
int is_balanced(binary_tree *bt){
    int bf = h(bt->left) - h(bt->right);
    return ((-1 <= bf) && (bf <= 1));
}
binary_tree *rotate_left(binary_tree *bt){
    binary_tree *subtree_root = NULL;
    if(bt != NULL && bt->right != NULL){
        subtree_root = bt->right;
        bt->right = subtree_root->left;
        subtree_root->left = bt;
    }
    subtree_root->h = h(subtree_root);
    bt->h = h(bt);
    return subtree_root;
}
binary_tree *rotate_right(binary_tree *bt){
    binary_tree *subtree_root = NULL;
    if(bt != NULL && bt->left != NULL){
        subtree_root = bt->left;
        bt->left = subtree_root->right;
        subtree_root->right = bt;
    }
    subtree_root->h = h(subtree_root);
    bt->h = h(bt);
    return subtree_root;
}
int search_avl(binary_tree *bt, int item){
    if((bt == NULL) || (bt->item == item)){
        return w;
    } else if(bt->item > item){
        w = w + 1;
        return search_avl(bt->left, item);
    } else{
        w = w + 1;
        return search_avl(bt->right, item);
    }
}
binary_tree *add_avl(binary_tree *bt, int item){
    if(bt == NULL){
        return create_tree(item, NULL, NULL);
    }else if(bt->item > item){
        bt->left = add_avl(bt->left, item);
    }else{
        bt->right = add_avl(bt->right, item);
    }
    bt->h = h(bt);
    binary_tree *child = NULL;
    if(balance_factor(bt) == 2 || balance_factor(bt) == -2){
        if(balance_factor(bt) == 2){
            child = bt->left;
            if(balance_factor(child) == -1){
                bt->left = rotate_left(child);
            }
            bt = rotate_right(bt);
        }else if(balance_factor(bt) == -2){
            child = bt->right;
            if(balance_factor(child) == 1){
                bt->right = rotate_right(child);
            }
            bt = rotate_left(bt);
        }
    }
    return bt;
}
void comparator(){
    long long int n, element, i, position, element_search, ate;
    char choise;
    printf("Quantos números serão gerado?\n");
    scanf("%lld", &n);
    printf("Até qual elemento?\n");
    scanf("%lld", &ate);
    printf("Escolher o a posição do número a ser procurado? s/n\n");
    getchar();
    scanf("%c", &choise);
    srand(time(NULL));
    if(choise == 's'){
        printf("Qual posição, entre 0/%lld\n", n - 1);
        scanf("%lld", &position);
        position = position - 1;
    }else position = rand() % n;
    binary_tree *ABB = create_empty_tree();
    binary_tree *AVL   = create_empty_tree();
    for(i=0;i<n;i++){
        element = rand() % ate;
        ABB = add_abb(ABB, element);
        AVL = add_avl(AVL, element);
        if(i == position) element_search = element;
    }
    // printf("ABB:\n");
    // print_pre_order(ABB);
    // printf("AVL:\n");
    // print_pre_order(AVL);
    printf("Elemento procurado: %lld, foi %lld a ser inserido\n", element_search, position + 1);
    printf("Comparações ABB: %d\n", search_abb(ABB, element_search));
    printf("Comparações AVL: %d\n", search_avl(AVL, element_search));
}
void main(){
    comparator();
}