• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

eMineiro

Balancear Árvore Binária

6 mensagens neste tópico

Olá estou estudando sobre arvores e estou um pouco perdido quanto a balancear uma árvore binária.

Eis que ja sei alguns conceitos

Altura de Uma Árvore , Número de Nós De Uma Árovre são conceitos que ja sei os algoritimos e que não necessitam ser explicados.

Li no wikipedia:http://pt.wikipedia.org/wiki/Árvore_AVL , algoritimo de rotacionar uma árvore avl, creio eu que avl é igual a árvore binária.

Então tenho quase certeza que terei de usar o sistema de rotações para balancear, mas alguem poderia me dar uma luz, algoritimo, site, tutorial, pdf, livro???

Realmente ficarei grato se puderem me ajudar com este algoritimo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Então mas foi o que eu disse, la ensinava um algoritimo de roatacionar um nó, que achei que fosse parte do algoritimo de balancear uma arvore binária de busca.

Você pode me passar links que contém algoritimo ou pelo menos alguma ajuda sobre como balancear uma arvore binária??

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Desculpa rui, é pq vc falou que são árvore diferente, achei que não iria ser útil pra mim, vo da uma estudada por isso.

Apesar de que na árvore avl a inserção ja é balanceada e no meu caso não ;/.....vo tirar o maior proveito possível disso ae que você me passou, obrigado

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dentre todo o meu estudo feito essa semana por arvores binárias, procurei por muitas coisas e acho que ja tenho um caminho para balancear uma arvore.

Percorrendo toda a arvore eu faço as seguintes verificações.

Arvore balanceada = Altura Arv Esquerda - Altura da Arv Direita <= 1

Arvore está balanceada? Se sim, prosiga, senao faça:

Com a raiz dada como PIVO (Nao sei se em portugal vocês dao esse nome) faço as devidas rotações para balancear a árvore.

Se Altura Arv Esquerda maior que Altura Arv Direita, eu faço um rotação para a direita.

Se Altura Arv Direita maior que a Altura da Arv Esquerda, eu faço uma rotação para a esquerda.

Continuo a verificar. Penso eu que devo percorrer a arvore no sentido arv_esquerda , arv_direita , raiz.

O pensamento está certo?? por favor ajudem xD

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora