quarta-feira, 17 de setembro de 2008

Comparação do Desempenho da Árvore Binária de Busca (ABB) e Árvore n-area de busca (ANE)

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

magno.fernando@gmail.com

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:

clip_image002

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

3.1.Gráficos de desempenho: ­ clip_image004clip_image006 clip_image008

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: