Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

Rexy

Árvores

Mensagens Recomendadas

Rexy    0
Rexy

Há algum interesse em utilizar árvores binárias balanceadas? Qual diferença entre a definição de uma árvore binária não-balanceada e uma árvore binaria balanceada?

Estou com alguma dúvida a entender qual a diferença mesmo. Agradeço desde ja a ajuda.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
KiNgPiTo    6
KiNgPiTo

Tem a ver com a complexidade das árvores. Uma árvore não balanceada, por exemplo, para efectuares uma pesquisa de um elemento tens um pior caso com O(N) ou seja tens de percorrer todos os nodos. Numa árvore balanceada tens O(logN) (um nodo por nível)...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Baderous    31
Baderous

Ao balancear uma árvore, diminui-se a sua altura e evita-se que a árvore degenere numa lista ligada que, tal como o KiNgPiTo disse, tem complexidade O(N) de processamento, contra O(log(N)) duma árvore balanceada.

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


×

Aviso Sobre Cookies

Ao usar este site você aceita a nossa Política de Privacidade