AVL_TREE.c

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *left;
    struct node *right;
    int height;
}node_avl;

int max(int a, int b){
    return a > b ? a : b;
}

int avl_height(node_avl *node){
    return node == NULL ? -1 : node->height;
}

void rotateWithLeftChild(node_avl **node){
    node_avl *node_tmp = (*node)->left;
    (*node)->left = node_tmp->right;
    node_tmp->right = (*node);
    (*node)->height = max(avl_height((*node)->left), avl_height((*node)->right)) + 1;
    node_tmp->height = max(avl_height(node_tmp->left), (*node)->height) + 1;
    (*node) = node_tmp;
}

void rotateWithRightChild(node_avl **node){
    node_avl *node_tmp = (*node)->right;
    (*node)->right = node_tmp->left;
    node_tmp->left = (*node);
    (*node)->height = max(avl_height((*node)->left), avl_height((*node)->right)) + 1;
    node_tmp->height = max(avl_height(node_tmp->right), (*node)->height) + 1;
    (*node) = node_tmp;
}

void doubleWithLeftChild(node_avl **node){
    rotateWithRightChild(&((*node)->left));
    rotateWithLeftChild(&(*node));
}

void doubleWithRightChild(node_avl **node){
    rotateWithLeftChild(&((*node)->right));
    rotateWithRightChild(&(*node));
}

void insert_avl(node_avl **node, int data){
    if((*node) == NULL){
        (*node) = (node_avl*)malloc(sizeof(node_avl));
        (*node)->left = (*node)->right = NULL;
        (*node)->data = data;
    }
    else if(data < (*node)->data){
        insert_avl(&((*node)->left), data);
        if(avl_height((*node)->left) - avl_height((*node)->right) == 2)
            if(data < (*node)->left->data)
                rotateWithLeftChild(&(*node));
            else
                doubleWithLeftChild(&(*node));
    }
    else if(data > (*node)->data){
        insert_avl(&((*node)->right), data);
        if(avl_height((*node)->right) - avl_height((*node)->left) == 2){
            if(data > (*node)->right->data)
                rotateWithRightChild(&(*node));
            else
                doubleWithRightChild(&(*node));
        }
    }
    else; // Duplicate; do nothing
    (*node)->height = max(avl_height((*node)->left), avl_height((*node)->right)) + 1;
}

void printTreeInOrder(node_avl *node){
    if(node == NULL) return;
    printTreeInOrder(node->left);
    printf("%d ", node->data);
    printTreeInOrder(node->right);
}

int main(){
    int n, i;
    scanf("%d", &n);
    int data[n];
    
    for(i=0; i<n; i++)
        scanf("%d", &data[i]);
    
    node_avl *root = NULL;
    for(i=0; i<n; i++)
        insert_avl(&root, data[i]);
    
    printTreeInOrder(root);
    
    return 0;
}