Arvore avl

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (840 palavras )
  • Download(s) : 0
  • Publicado : 30 de novembro de 2012
Ler documento completo
Amostra do texto
#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 emarvores 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 outrosdados 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 a esquerda e ve se a sub-arvore cresceu */
cresceu = insereAVL(x, &(*p)->esq);
if(cresceu) {
/* Verifica o estado atual de balanceamento */
switch((*p)->bal) {
/* Se a arvore dir. era maior nao ha crescimento */
case 1:
(*p)->bal = 0;
cresceu = 0;
break;
/* Se a arvoredir. tinha tamanho igual, houve crescimento */
case 0:
(*p)->bal = -1;
cresceu = 1;
break;
/* Se a sub-arvore da esq. ja era maior, deve-se re-balancear. */
case -1:
/* Verifica qual o...
tracking img