Uma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras
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.
Palavras-chave
Texto completo:
PDFReferê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.
DOI: http://dx.doi.org/10.47236/2594-7036.2020.v4.i3.124-131p
Apontamentos
- Não há apontamentos.

CC BY
Este obra está licenciado com uma Licença Creative Commons Atribuição 4.0 Internacional.
Esta licença permite que outros distribuam, remixem, adaptem e criem a partir do seu trabalho, mesmo para fins comerciais, desde que lhe atribuam o devido crédito pela criação original.
Revista Sítio Novo
Kallyana Moraes Carvalho Dominices
Editora-Chefe
Instituto Federal do Tocantins - Reitoria
Avenida Joaquim Teotônio Segurado, Quadra 202 sul, ACSU-SE 20, Conjunto 01, Lote 08 - Plano Diretor Sul
Palmas, Tocantins - Brasil
Cep: 77.020-450
Telefone: 63 3229-2214
Bases de Dados, Diretórios, Repositórios e/ou Indexadores
Utilizamos o seguinte software de detectação de similaridade:
