Versão em pdf comigo no msn:fernando_magno_@hotmail.com
Fernando Alves Michalak
Departamento de Ciência da Computação – Universidade do Estado de Santa Catarina – Joinville, SC – Brasil
Resumo. Este trabalho tem por objetivo comparar os desempenhos desses de dois tipos de árvores de dados, sendo elas a árvore binária de busca (ABB) e a árvore n-área (ANE) de busca. Nesse trabalho será relatada a descrição de cada arvore e seus desempenhos para que no final se possa definir a mais eficiente para armazenar os dados propostos ao trabalho.
1. Introdução
Uma árvore é uma estrutura de dados em que cada elemento tem zero ou mais elementos associados, podendo definir-se uma árvore recursivamente como:
- uma estrutura vazia (uma árvore vazia);
- um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são comumente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.
As arvores de dados podem ser classificadas dentro desses dois grupos:
- Genéricas (XML,diretórios,expressões,etc.)
- De Busca (as árvores em questão nesse trabalho).
1.1. Árvore Binária
Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.
Uma árvore binária é considerada estritamente binária se cada nó da árvore possui grau zero ou dois.
A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.
Uma árvore é dita completa se todas as folhas da árvore estão no mesmo nível da árvore.
1.1.1 Árvore Binária de Busca
A árvore binária de busca é constituída através três ponteiros, onde um direciona para a informação que estará armazenada na memória e os outros dois para os filhos do nó da árvore, caso o valor da informação a ser inserida for maior que a existente nesse nó, a nova informação é inserida a direita, caso contrario, é inserida a esquerda.
Ela é constituída por um nó principal(a raiz) e pode possuir um ou mais nós folha (que são nós sem filhos). Possui uma profundidade(comprimento do caminho da raiz a algum nó) e uma altura(comprimento do caminho da raiz ao ultimo nó folha). No trabalho implementamos os métodos de criação, inserção, remoção, reinicia e destruição da mesma.
1.1.2 Árvore n-area de Busca
A árvore n-area de Busca também é criada através de ponteiros, mas diferentemente da ABB ela possui quantos ponteiros forem necessários, tendo no mínimo 2: um para a informação e os outros “n” ponteiros para mostrar os demais nos.
Para determinar onde cada nó deve ser inserido utilizamos a seguinte função de espalhamento: t(k, i) = (ch + i)%(N + k − i), onde K demonstra o nível da árvore e, caso o valor a ser inserido na árvore não seja encontrado entre alguma posição do vetor acrescenta-se 1 ao i. Ch representa o valor a ser inserido e N o número de posições no vetor.
A seguir um desenho ilustrando como é o nó utilizado:
Em seu programa implementamos a criação, inserção, remoção, reinicia e destruição.
2. Desenvolvimento
No desenvolvimento do trabalho houve certa dificuldade em compreender a estrutura da árvore n-area. Foi essencial o auxilio dos professores e amigos de turma para esclarecer esta questão.
A ABB já estava pronta de exercícios feitos anteriormente, ou seja, foi necessária somente implementa-la.
Devida a sua estrutura a árvore n-area necessitou de mais horas de trabalho, dando destaque para a função insereAne e removeAne.
3. Resultados
Seguem os dados obtidos:
ABB
ANE 2
ANE 3
ANE 4
ANE 8
ANE 32
100
794,00
783
588
534
421,00
369,00
200
2.534,00
2616
1942
1713
1.351,00
1.138,00
300
5.395,00
5617
4158
3603
2.807,00
2.307,00
400
9.382,00
9875
7285
6255
4.809,00
3.876,00
500
14.615,00
15444
11361
9679
7.400,00
5.845,00
600
20.890,00
22383
16430
13912
10.588,00
8.214,00
700
28.786,00
30699
22561
18995
14.370,00
10.983,00
800
37.629,00
40459
29742
24936
18.765,00
14.152,00
900
48.530,00
51627
38001
31754
23.779,00
17.721,00
1000
60.416,00
64231
47320
39441
29.414,00
21.690,00
2000
85.225,00
92581
68396
56659
41.454,00
30.606,00
3000
127.917,00
137983
102264
84203
60.259,00
44.526,00
4000
187.311,00
201166
149466
122835
86.108,00
63.463,00
5000
264.793,00
282700
210498
172759
119.549,00
87.415,00
6000
356.349,00
383202
285808
234521
160.638,00
116.399,00
7000
470.935,00
502727
375735
308401
209.511,00
150.434,00
8000
598.041,00
642090
480614
394433
266.224,00
189.507,00
9000
740.025,00
801441
600647
493056
331.153,00
233.630,00
10000
911.498,00
980861
736217
604481
404.440,00
282.804,00
20000
1.278.314,00
1372272
1034470
850884
564.255,00
384.542,00
30000
1.841.013,00
1988952
1506211
1242096
814.139,00
545.722,00
40000
2.626.138,00
2838617
2158890
1784872
1.156.760,00
766.763,00
50000
3.640.090,00
3928073
2997102
2484198
1.594.352,00
1.047.930,00
60000
4.838.704,00
5262237
4026525
3344407
2.130.250,00
1.389.272,00
70000
6.266.395,00
6844961
5249210
4368325
2.766.620,00
1.790.820,00
80000
7.858.805,00
8679595
6669256
5558888
3.504.667,00
2.252.655,00
90000
9.838.499,00
10769579
8288856
6919143
4.345.866,00
2.774.778,00
100000
11.983.785,00
13116717
10109392
8450542
5.291.102,00
3.357.303,00
Os gráficos acima apresentados demonstram que o ANE se apresenta como a melhor estrutura em relação a desempenho à partir de ANE com 3 ponteiros.
Para verificar a relação da quantidade de ponteiros e seu desempenho foi feito um teste com 2,3,4, 8 e 32 ponteiros. Estes testes demonstram uma queda logarítmica na quantidade de comparações.
4. Conclusão
Considerando que a menor quantidade de comparações qualifica uma estrutura de dados como mais ou menos eficiente e ao analisar os testes com as duas estruturas de dados, conclui-se que que a árvore n-area com mais de dois ponteiros se apresenta como a melhor opção para armazenamento de dados. Isso se deve ao fato de que uma árvore n-area com mais de dois ponteiros possui uma altura menor, por conseqüência necessita de menos comparações em suas buscas.
Conclui-se também que quanto maior a quantidade de ponteiros da arvore n-area, menor é a sua altura.
5. Referências
Fiorese, Adriano e Gonçalves, Alexandre (2006) Projeto de AED – Implementação de um hashing hierárquico (ANE) e comparação de desempenho com a árvore binária de busca (ABB).
Figueiredo, António Dias. ESCREVER UM ARTIGO CIENTÍFICO:DAS PARTES PARA O TODO(http://eden.dei.uc.pt/~ctp/papers.htm), Departamento de Engenharia Informática, Universidade de Coimbra, Coimbra, Portugal, 1998.
Wikipedia; http://pt.wikipedia.org/wiki/; 11 de dezembro de 06 – 22:10;
Nenhum comentário:
Postar um comentário