Arvores em C

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 )
 
A minha dificuldade é saber que flexibilidade é que elas têm, que tipo de funções podem ter, e mais tarde como implementar.

Obrigado
 
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
 
HecKel disse:
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
Clicar para expandir...

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

Mais info aqui
 
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..
 
snis disse:
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..
Clicar para expandir...

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 =)
 
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 *
 
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:
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:

Red Black & AVL trees both have O(log N) search, insert and delete, min, max, previous, next in terms of nodes.

Somebody said insert was O(1). It is not, as it still take O(log N) steps to find the correct place to insert. What is O(1) for Red Black insert, is any rebalancing necessary to restore the trees properties. At most a double left or right rotation is needed. For a AVL tree, rebalancing is O(log N). This is where a RB tree gains over AVL. There is less rebalancing of nodes after an insert.
Clicar para expandir...
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:
Inicie sessão ou registe-se para poder participar.
Back
Topo