Relatório de Desempenho Sobre AVLs e Binary Trees

[pic 1]

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.

---

1. 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.

---

1. 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.

[pic 2]

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.

[pic 3]

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 2.

Tamanho	Rot. Inserção	Rot. Remoção
1.000	719	357
10000	6961	3853
100000	73770	38653
1000000	993417	472958

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

As operações com elementos em ordem crescente estão dispostas nos gráficos das figuras 3 e 4, que respectivamente indicam os tempos cronometrados de inserção/remoção e o número de rotações feitas na AVL. As figuras serão complementadas pelas tabelas 3 e 4.

[pic 4]

Figura 3 - Comparação AVL x Binária desbalanceada com elementos ordenados em ordem crescente