Uma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras
Revista Sítio Novo
Uma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras
Autor Correspondente: Edwardes Amaro Galhardo | [email protected]
Palavras-chave: Análise assintótica. Árvores binárias. Estrutura de dados. Mediana.
Resumos Cadastrados
Resumo Português:
Este trabalho apresenta uma abordagem para calcular a mediana das chaves, após a sua inserção em estruturas de dados do tipo árvores AVL e árvores Rubro-Negras. Por meio da linguagem C, realizam-se inserções de chaves nas duas árvores, com o número de nós variando entre 10 e 2.000.000. Além de realizar o cálculo da mediana das chaves contidas nas duas árvores, realizaram-se comparações da eficiência para obtenção das medianas através de análises das alturas e do número de rotações das árvores. A partir dos resultados encontrados, nota-se que as duas estruturas possuem uma complexidade assintótica O(n) para encontrar a mediana, porém, a árvore Rubro-Negra apresenta um desempenho melhor para a obtenção da mediana dos números inteiros contidos nela.
Resumo Inglês:
This paper presents an approach to calculate the median of the keys, after their insertion in data structures like AVL-Trees and Red-Black-Trees. Through by the C Language, key insertions are performed in the two trees, with the number of nodes ranging from 10 to 2,000,000. In addition to calculating the median of the keys contained in the two trees, efficiency comparisons were made to obtain the medians through analysis of the heights and number of rotations of the trees. From the results found, it was noted that the two structures have an asymptotic complexity O(n) to find the median, but the Red-Black-Tree presents a better performance to obtain the median of the integers in it.
