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

struct AvlNode;

typedef  int ElementType;
typedef struct AvlNode * Position;
typedef  Position AvlTree;

AvlTree makeEmpty(AvlTree T);
Position find(ElementType x, AvlTree T);
Position findMax(AvlTree T);
Position findMin(AvlTree T);
AvlTree insert(ElementType x, AvlTree T);
AvlTree deleteNode(ElementType x, AvlTree T);
ElementType retrieve(Position p);

struct AvlNode {
    ElementType  element;
    AvlTree  left;
    AvlTree  right;
    int height;
};

static int height(Position p) {
    if (p == NULL) {
        return -1;
    } else {
        return  p->height;
    }
}

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

AvlTree  makeEmpty(AvlTree T) {
    if (T != NULL) {
        makeEmpty(T->left);
        makeEmpty(T->right);
        free(T);
    }
    return NULL;
}


Position  find(ElementType x, AvlTree T) {
    if (T == NULL) {
        return NULL;
    } else {
        if (x < T->left->element) {
            T->left = find(x,T->left);
        } else if (x > T->right->element) {
            T->right = find(x,T->right);
        } else {
            return  T;
        }
    }
}


Position  singleRotateWithLeft(Position k2) {
    Position  k1 = k2->left;
    k2->left = k1->left;
    k1->right = k2;
    k1->height = maxHeight(height(k1->left),k1->height) + 1;
    k2->height = maxHeight(height(k2->left),height(k2->right)) + 1;
    return  k1;
}

Position singleRotateWithRight(Position k1) {
    Position  k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = maxHeight(height(k1->left),height(k1->right)) + 1;
    k2->height = maxHeight(height(k2->left),k2->height) + 1;
    return  k2;
}

Position  doubleRotateWithLeft(Position k3) {
    k3->left = singleRotateWithLeft(k3->left);
    return singleRotateWithRight(k3);
}

Position  doubleRotateWithRight(Position k3) {
    k3->right = singleRotateWithRight(k3->right);
    return singleRotateWithLeft(k3);
}

AvlTree insert(ElementType x, AvlTree T) {
    if (T == NULL) {
        T = (AvlTree)malloc(sizeof(struct AvlNode));
        T->element = x;
        T->left = NULL;T->right = NULL;
        T->height = 0;
    } else if (T->element < x){
        T->left = insert(x,T->left);
        if (height(T->left) - height(T->right) == 2) {
            if (x < T->left->element) {
                T = singleRotateWithLeft(T);
            } else {
                T = doubleRotateWithLeft(T);
            }
        }
    } else if (T->element > x) {
        T->right = insert(x,T->right);
        if (height(T->left) - height(T->right) == 2) {
            if (x>T->right->element) {
                T = singleRotateWithRight(T);
            } else {
                T = doubleRotateWithRight(T);
            }
        }
    }

    T->height = maxHeight(height(T->left),height(T->right)) + 1;
    return T;
}

Position findMax(AvlTree T) {
    if (T != NULL) {
        while (T->right != NULL) {
            T = T->right;
        }
    }
    return  T;
}
Position  findMin(AvlTree T) {
    if (T != NULL) {
        while (T->left != NULL) {
            T = T->left;
        }
    }

    return  T;
}

AvlTree  deleteNode(ElementType x, AvlTree T) {
    Position  Tmp;
    if (T == NULL) {
        printf("AvlTree is empty...\n");
    } else if (x < T->left->element) {
        T->left = deleteNode(x,T->left);
    } else if (x > T->right->element) {
        T->right = deleteNode(x,T->right);
    } else if (T->left && T->right) {
        Tmp = findMin(T);
        T->element = Tmp->element;
        T->right = deleteNode(T->element,T->right);
    } else {
        Tmp = T;
        if (T->left == NULL) {
            T = T->right;
        } else (T->right == NULL) {
            T = T->left;
        }
        free(Tmp);
    }
    return T;
}