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-131pPalabras clave:
Análise assintótica. Árvores binárias. Estrutura de dados. Mediana.Resumen
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.Descargas
Métricas
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2020 Edwardes Amaro Galhardo, Cassio Martins Carlos, João Augusto Arce Santana, Vinicius Carvalho Lopes, Antonio Carlos de Oliveira Júnior
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Permite el intercambio, la adaptación y el uso para cualquier fin, incluso comercial, siempre que se otorgue la debida atribución a los autores y a la Revista Sítio Novo.
Los autores declaran que el trabajo es original y que no ha sido publicado previamente, ni total ni parcialmente, salvo en servidores de preprints reconocidos, siempre que se declare, y que ningún otro manuscrito similar de su autoría se encuentra publicado ni en proceso de evaluación por otra revista, ya sea impresa o electrónica.
Declaran que no han violado ni infringido ningún tipo de derecho de propiedad de terceros, y que todas las citas en el texto son hechos verídicos o están basadas en investigaciones con exactitud científicamente comprobable.
Los autores conservan los derechos de autor de los manuscritos publicados en esta revista, permitiendo el uso irrestricto de su contenido, siempre que se cite adecuadamente la autoría original y la fuente de publicación.
