Uma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras
DOI:
https://doi.org/10.47236/2594-7036.2020.v4.i3.124-131pKeywords:
Análise assintótica. Árvores binárias. Estrutura de dados. Mediana.Abstract
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.Downloads
Metrics
References
CAPELLE, Márcia R. Estrutura de Dados e Projeto de Algoritmos: EDPA.2019.1270 slides
CORMEN, Thomas H. How to Describe and Evaluate Computer Algorithms. 2013.
CORMEN, Thomas H. et al. Introduction to algorithms. MIT press, 2009.
JAGADISH, Hosagrahar V.; OOI, Beng Chin; VU, Quang Hieu. Baton: A balanced tree structure for peer-to-peer networks. In: Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 2005. p. 661-672.
ROSEN, Kenneth H.; KRITHIVASAN, Kamala. Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.
SCHEINERMAN, Edward R. Matemática Discreta: Uma introdução. Thomson Pioneira, 2017. (Tradução da 3ª ed. norte-americana)
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de Dados e seus Algoritmos. Livros Técnicos e Científicos, 1994.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Edwardes Amaro Galhardo, Cassio Martins Carlos, João Augusto Arce Santana, Vinicius Carvalho Lopes, Antonio Carlos de Oliveira Júnior
This work is licensed under a Creative Commons Attribution 4.0 International License.
It allows sharing, adaptation, and use for any purpose, including commercial use, provided proper attribution is given to the authors and to Revista Sítio Novo.
The authors declare that the work is original and has not been previously published, in whole or in part, except on recognized preprint servers, if declared, and that no other similar manuscript authored by them is published or under review by another journal, whether printed or electronic.
They declare that they have not violated or infringed upon any proprietary rights of others, and that all citations in the text are factual or based on research with scientifically significant accuracy.
The authors retain the copyright of the manuscripts published in this journal, allowing unrestricted use of their content, provided that the original authorship and the publication source are properly cited.
