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

/* Estruturas para uma arvore de inteiros. */ typedef struct _no { int chave; /* Chave para busca */ int bal; /* Indicacao sobre balanceamento: */ /* -1 se esq. maior, 0 se balanceado, 1 se dir maior */ /* Outros campos de dados aqui */

struct _no *esq, *dir; /*Ponteiros para sub-arvores esq e direita*/
} no;

/* Inicializa a arvore (NULL)*/ void inicializa(no **r)
{
(*r) = NULL;
}

/* Busca x em uma arvore binaria de busca. */ no *busca(int x, no *raiz) { while ((raiz != NULL) && (raiz->chave != x)) { if (raiz->chave < x) raiz = raiz->dir; else raiz = raiz->esq; } return raiz;
}

/* Rotacao a direita */ void rot_dir(no **p) { no *aux; aux = (*p)->esq; (*p)->esq = aux->dir; aux->dir = *p; *p = aux;
}

/* Rotacao a esquerda */ void rot_esq(no **p) { no *aux; aux = (*p)->dir; (*p)->dir = aux->esq; aux->esq = *p; *p = aux;
}

/* Insercao em arvores AVL */ int insereAVL(int x, no **p) {

int cresceu;

/* Se a arvore esta vazia insere. */ if (*p == NULL) { *p = (no *) malloc(sizeof(no)); (*p)->chave = x; /* Caso houvesse outros dados eles deveriam ser copiados aqui. */ (*p)->dir = (*p)->esq = NULL; /* Balanceamento de uma folha e sempre perfeito */ (*p)->bal = 0; /* Esta sub arvore cresceu */ cresceu = 1; } /* Senao verifica se tem que inserir a esquerda */ else if ((*p)->chave > x) { /* Tenta inserir