Arvores balanceadas

652 palavras 3 páginas
#include
#include

typedef struct arv{ int info,altura; struct arv *esq, *dir;
}*Arv;

Arv aloca_Arv(){ Arv aux=(struct arv*)malloc(sizeof(struct arv)); if (aux==NULL) printf("\n\n\t\tSem espaco de memoria."); return aux;
}

int altura(Arv raiz ){ if( raiz == NULL ) return 0; else return raiz->altura;
}

int calcular_altura(Arv esq, Arv dir ){ int ae, ad; ae=altura(esq); ad=altura(dir); if(ae>ad) return ae+1; else return ad+1;
}

int altura_maior(int a, int b){ if (a>=b) return a; else return b;
}

Arv rot_dir(Arv no){ Arv aux; aux = no->esq; no->esq = aux->dir; aux->dir = no; no->altura = altura_maior(altura(no->esq),altura(no->dir))+1; aux->altura = altura_maior(altura(aux->esq),altura(no))+1; return aux;
}

Arv rot_se(Arv no){ Arv aux; aux = no->dir; no->dir = aux->esq; aux->esq = no; no->altura = altura_maior(altura(no->esq),altura(no->dir))+1; aux->altura = altura_maior(altura(aux->dir),altura(no))+1; return aux;
}

Arv rd_esq_dir(Arv no){ no->esq = rot_se( no->esq ); return rot_dir(no);
}

Arv rd_dir_esq(Arv no){ no->dir=rot_dir(no->dir); return rot_se(no);
}

void verificaavl(Arv *no){ if ((*no)!=NULL){ if ( (altura((*no)->dir) - altura((*no)->esq))==-2){ if ( (altura((*no)->esq->dir) - altura((*no)->esq->esq) )==-1) *no=rot_dir(*no); else *no=rd_esq_dir(*no); }else if ( (altura((*no)->dir) - altura((*no)->esq))==2){ if((altura((*no)->dir->dir)-altura((*no)->dir->esq))==1) *no=rot_se(*no); else *no=rd_dir_esq(*no);

Relacionados

  • arvores balanceadas
    1194 palavras | 5 páginas
  • Árvore rubro negra
    4598 palavras | 19 páginas
  • Arvore avl
    5073 palavras | 21 páginas
  • arvores
    2061 palavras | 9 páginas
  • Arvores AVL
    889 palavras | 4 páginas
  • Arvores
    2734 palavras | 11 páginas
  • Arvores binarias
    1706 palavras | 7 páginas
  • teste
    3016 palavras | 13 páginas
  • arvores binarios em java
    4192 palavras | 17 páginas
  • Abordagem de arvores rubro-negra
    2304 palavras | 10 páginas