Árvore Binária

#include <stdio.h>

#include <stdlib.h>

#include "avl_tree.h"

void avl_init ( AVL_Tree **tree,

int (*compara_info)( const void *, const void *),

void (*imprime_info)( const void * ))

/* Inicializa a árvore */

{

AVL_Tree *nova;

nova = ( AVL_Tree * ) malloc ( sizeof ( AVL_Tree ));

if ( nova == NULL ) return;

nova->root = NULL;

nova->num_nodes = 0;

nova->compara_info = compara_info;

nova->imprime_info = imprime_info;

*tree = nova;

}

int avl_height ( AVL_Node *node ) {

int esq, dir;

if ( node == NULL ) return -1;

esq = avl_height ( node->esq );

dir = avl_height ( node->dir );

if ( esq > dir )

return esq + 1;

else

return dir + 1;

}

/* -- Rotações de sub-árvore --

*

* A árvore AVL necessita, além das rotinas

* básicas, algumas rotinas auxiliares para

* mantê-la balanceada. São elas: rotação

* simples para a esquerda, rotação simples

* para a direita.

*/

AVL_Node *rotacao_direita ( AVL_Node *p )

/* Rotação simples para a direita */

{

AVL_Node *q;

q = p->esq;

//----------------> Realiza a rotação

p->esq = q->dir;

if ( q->dir != NULL )

q->dir->pai = p;

q->dir = p;

q->pai = p->pai;

if ( p->pai != NULL )

if ( p->pai->esq == p )

p->pai->esq = q;

else

p->pai->dir = q;

p->pai = q;

//----------------> Rebalanceia

q->bal = avl_height ( q->dir ) - avl_height ( q->esq );

p->bal = avl_height ( p->dir ) - avl_height ( p->esq );

return q;

}

AVL_Node *rotacao_esquerda ( AVL_Node *p )

/* Rotação simples para a esquerda */

{

AVL_Node *q;

q = p->dir;

//----------------> Realiza a rotação

p->dir = q->esq;

if ( q->esq != NULL )

q->esq->pai = p;

q->esq = p;

q->pai = p->pai;

if ( p->pai != NULL )

if ( p->pai->esq == p )

p->pai->esq = q;

else

p->pai->dir = q;

p->pai = q;

//----------------> Rebalanceia

q->bal = avl_height ( q->dir ) - avl_height ( q->esq );

p->bal = avl_height ( p->dir ) - avl_height ( p->esq );

return q;

}

/* Inserção na árvore AVL */

int avl_insert ( AVL_Tree **tree, AVL_Node *pai, AVL_Node **node, void *info )

{

AVL_Node *novo;

int aux;

if ( *tree == NULL ) return -1;

if ( *node == NULL )

// Se for o local correto para a inserção

{

novo = ( AVL_Node * ) malloc ( sizeof ( AVL_Node ));

if ( novo == NULL ) return -1;

novo->info = info;

novo->bal = 0;

novo->pai = pai;

novo->esq = NULL;

novo->dir = NULL;

*node = novo;

(*tree)->num_nodes++;

return 1;

}

/*

* Procura o local apropriado. Na volta da pilha do processador, o