Relatório de Desempenho Sobre AVLs e Binary Trees

Instituto de Matemática e Computação - IMC

Universidade Federal de Itajubá - UNIFEI

Disciplina COM112 - Algoritmos e Estruturas de Dados II

1o Semestre de 2022

Nome: Gabriel Marra D’Martins Matrícula: 2016013157

Atividade 6 - Relatório de Desempenho sobre AVLs e árvores Binárias

1. Introdução

A computação é notoriamente conhecida pela rica gama de estruturas de dados utilizadas no desenvolvimento de aplicações e sistemas, entre uma dessas arquiteturas existem as árvores. No contexto abordado, elas são estruturas não lineares onde seus dados estão dispostos de forma hierárquica, ou seja, estão posicionados em níveis diferentes da árvore. O primeiro nível (topo) desta árvore é conhecido como raiz, que possui ligações para os outros elementos(nós) filhos que estão alocados em níveis inferiores da estrutura.

As árvores possuem diversas implementações, as duas presentes neste trabalho são a AVL, criada em 1962 pelos soviéticos Adelson Velsky e Landis que a criaram para que fosse possível inserir e buscar um elemento em tempo c.log (n) operações, onde n é o número de elementos contido na árvore, tornando-a a primeira árvore binária balanceada criada; e a outra estrutura é a binária desbalanceada, ou seja, ela não realiza o balanceamento dos seus e portanto possui uma complexidade maior para busca, inserção ou remoção de um elemento presente.

O objetivo deste trabalho é comparar a performance entre ambas as implementações descritas anteriormente, a fim de expor as diferenças e semelhanças no seus processos de busca, remoção e inserção de elementos através de métricas de tempo de execução e número de rotações.

________________

2. Metodologia

A metodologia foi dividida da seguinte forma, foi escolhida apenas uma máquina para a realização do experimento. Ela possui as seguintes especificações:

* Processador: AMD Fx 8350 2.8 GHz

* Memória ram: 8 gigabytes

* Sistema operacional: Windows 10

* IDE e Compilador: Dev c + +, compilador GNU.

Sobre as métricas utilizadas serão analisadas duas implementações, uma árvore Binária desbalanceada e uma AVL. Para cada árvore serão inseridas em sua estrutura 4 entradas de tamanhos diferentes iguais a 1.000, 10.000, 100.000 e 1.000.000, sendo estes conjuntos de elementos divididos em três tipos de ordenação (crescente, decrescente e aleatório). Além disso, foram implementados contadores que irão contabilizar o número de rotações para carregar as árvores e esvaziá-las, cronômetros para medir o tempo de inserção e remoção de todos elementos da estrutura e a duração média para realização de 30 consultas para cada árvore também foram adicionados.

________________

3. Resultados

Após o desenvolvimento dos códigos foram realizados os testes e computados seus resultados. Os gráficos estão divididos da seguinte forma, primeiramente serão dispostos os gráficos com os tempos de inserção e remoção para cada estrutura seguido do número de rotações realizadas na AVL, vale ressaltar que os valores discrepantes das amostras pode dificultar a visualização dos valores dos gráficos, portanto tabelas também serão disponibilizadas a fim de complementar seus resultados.

Figura 1 - Comparação AVL x Binária desbalanceada com elementos ordenados aleatoriamente

A primeira comparação realizada foi com um conjunto de elementos ordenados de forma aleatória, a Figura 1 indica o tempo cronometrado correspondente às operações de inserção e remoção em cada árvore a fim de comparar a performance de execução. É evidente que a AVL levou mais tempo para realizar suas operações na amostra de 100.000 elementos devido a sua característica de realizar o balanceamento dos nós, quando os elementos foram na casa de 1.000.000 a binária desbalanceada apresentou um tempo muito reduzido para remoção total da árvore, isso pode ser devido à sua natureza desbalanceada e portanto, semelhante a uma lista. Vale ressaltar que devido ao número de consultas ser apenas 30, não foi possível contabilizar o tempo para cada amostra visto que ele é extremamente reduzido apresentando valor igual a 0,000001 segundos.

Tamanho

AVL Inserção

Binária. Inserção

AVL Remoção

Binária Remoção

1.000

0,002

0

0,001

0

10000

0,007

0,003

0,007

0,002

100000

0,1

0,045

0,098

0,035

1000000

1,903

2,035

2,028

0,46

Tabela 1 - Tabela com o tempo em segundos da figura 1 relacionados à performance com elementos aleatórios.

Figura 2 - Rotações realizadas na AVL durante a remoção e inserção de elementos aleatórios

Acerca do número de rotações, é possível afirmar que foram realizadas um número maior de rotações nas operações de inserção de todos os casos, os dados coletados estão dispostos na tabela