1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Arvores em C

Discussão em 'Programação' iniciada por Morrighan, 24 de Maio de 2007. (Respostas: 15; Visualizações: 2841)

  1. Morrighan

    Morrighan Power Member

    Boaaaas! Precisava de uma ajudinha.

    Preciso de saber funcionar com árvores. Desde RBT AVL etc.. Alguem sabe de tutoriais, links, wtv.. sobre isto? Algo que me ajudasse a compreender o seu funcionamente, utilidades, e vantagens de utilização em relação umas às outras.

    Tks *

    PS: (Morrighan = F )
     
  2. HecKel

    HecKel The WORM

    Boas!

    A tua dificuldade é na implementação ou na funcionalidade das mesmas?

    abraços, HecKel
     
  3. Morrighan

    Morrighan Power Member

    A minha dificuldade é saber que flexibilidade é que elas têm, que tipo de funções podem ter, e mais tarde como implementar.

    Obrigado
     
  4. HecKel

    HecKel The WORM

    Boas mais uma vez :P

    As árvores, tal como todas as outras estruturas, têm vantagens e desvantagens. A grande vantagem é mesmo a ordenação, com uma árvore bem implementada consegues percorrer a mesma de forma infixa, sufixa e prefixa sem grandes complicações e sem sequer teres de a ordenar.

    Em contrapartida, as operações de remoção, inserção e consulta são mais lentas que numa hashtable, pois tens de percorrer a árvore pelos ramos, mas visto que esta está ordenada (e se for AVL está equilibrada) só notas grandes diferenças de performance quando a árvore começa a ficar muito grande.

    As RBT são um pouco mais complicadas de explicar, e sinceramente nunca implementei nenhuma, só as conheço na teoria, mas funcionam um pouco por camadas..., sinceramente nem te sei dizer qual a vantagem das mesmas :S

    O que te recomendo, para já, é consultares a wikipedia e fazeres alguns debugs manuais (foi assim que aprendi bem as AVLs), perdes uma horita de volta de um teste parvo..., mas ficas a perceber a sua implementação ;)

    abraços, HecKel
     
  5. El_UnO

    El_UnO 1st Folding then Sex

    As RBT têm a vantagem de estarem sempre equilibradas :P

    Mais info aqui
     
  6. Morrighan

    Morrighan Power Member

    Eu tenho isso =P

    Mas nao estou a conseguir associar ao nosso projecto...

    No projecto passado utilizei Hash Table... Mas agora para a remoção de ficheiros e nao sei que =\.. Ando ah procura de soluções novas..
     
  7. snis

    snis Power Member

    arvores

    para isso teras q banlancear a arvore ao inserir..

    mas opah arvores nun e dificil, se quiseres arranjo-te uns pdf engraçados , em q tens la as ideias todas ..

    tens q começar por ver algoritmos de iteraçao preorder inorder inorder.. tens la tb exercicios do genero de contar qtos nodos a arvores ou folhas.. por ai
    qq duvida se te poder ajudar..
     
  8. Morrighan

    Morrighan Power Member

    Hum.. Agradecia imenso que me arranjasses entao esses pdf's.. É que estou assim a modos que indecisa.. Tenho que arranjar uma estrutura que me seja bastante flexivel e nivel de inserção e remoção. Nao estou a ver a Hash como uma boa solução para remover ficheiros =S.. Enfim..
    Thank you

    Cumps =)
     
  9. snis

    snis Power Member

  10. Morrighan

    Morrighan Power Member

    Obrigado =)

    Eu sobre a hash ja sabia o essencial. Utilizei-a no projecto passado, e tratei as colisoes com listas ligadas. O problema é : para alem de eu ter que por as palavras dos ficheiros na hash, a minha estrutura da palavra, tem q conter um apontador p uma estrutura com o nome dos ficheiros. Ora, quando me pedem para remover um ficheiro, ter q andar à procura dele na hash toda =| e ainda mais a procura sequencial na lista, fica demasiado inificiente. =\

    De arvores, é que eu pesco mesmo muito pouco =|..

    Mas tks plos pdf, dá para esclerecer umas coisas quanto à eficiencia.

    Cumps *
     
  11. Morrighan

    Morrighan Power Member

  12. Morrighan

    Morrighan Power Member

    COmo fazer um algoritmo de inserção numa AVL para ficar bem balanceada? Ha uma bibloioteca em C #include <rbtree.h> o que ja contem esta biblioteca?

    Obrigado =)
     
    Última edição: 26 de Maio de 2007
  13. Baderous

    Baderous Banido

    Bom, aproveito o facto de se estar a falar de AVLs para perguntar o seguinte:

    Qual a complexidade da operação de balanceamento de uma AVL: O(1) ou O(log(n))?
    Eu vi aqui que as rotações tinham O(1), e como o balanceamento é feito através de rotações pensei que era O(1). Mas depois vi isto, mais propriamente:

    e fiquei ainda mais confuso! Afinal é O(1) ou O(log(n))? Será que O(1) é a complexidade de uma rotação, mas o facto de se ter de percorrer todos os nodos até à raiz para corrigir o balanceamento (fazendo rotações sempre que preciso), faz com que a operação total de balanceamento seja O(log(n)), uma vez que a altura é 1.44log(n)?

    E a diferença entre os dois estará relacionada com o facto de as operações de balanceamento serem feitas à custa de apontadores?
     
    Última edição: 11 de Janeiro de 2008
  14. Baderous

    Baderous Banido

    Ninguém respondeu mas eu cheguei à conclusão: O(log(n)).
     

Partilhar esta Página