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-131pPalavras-chave:
Análise assintótica. Árvores binárias. Estrutura de dados. Mediana.Resumo
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
Métricas
Referências
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
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2020 Edwardes Amaro Galhardo, Cassio Martins Carlos, João Augusto Arce Santana, Vinicius Carvalho Lopes, Antonio Carlos de Oliveira Júnior
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Permite o compartilhamento, adaptação e uso para quaisquer fins, inclusive comerciais, desde que feita a devida atribuição aos autores e à Revista Sítio Novo.
Os autores declaram que o trabalho é original, não foi previamente publicado em parte ou no todo, exceto em servidores de preprints reconhecidos, desde que declarado, e que nenhum outro manuscrito similar de sua autoria está publicado ou em processo de avaliação por outro periódico, seja impresso ou eletrônico.
Declaram que não violaram nem infringiram nenhum tipo de direito de propriedade de outras pessoas, e que todas as citações no texto são fatos verdadeiros ou baseados em pesquisas de exatidão cientificamente considerável.
Os autores mantêm os direitos autorais dos manuscritos publicados nesta revista, permitindo o uso irrestrito de seu conteúdo, desde que citada a autoria original e a fonte da publicação.
