Uma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras

Edwardes Amaro Galhardo, Cassio Martins Carlos, João Augusto Arce Santana, Vinicius Carvalho Lopes, Antonio Carlos de Oliveira Júnior

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


Análise assintótica. Árvores binárias. Estrutura de dados. Mediana.

Texto completo:

PDF

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.


Apontamentos

  • Não há apontamentos.


 
Atribuição 

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. 

Contato:
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

e-ISSN: 2594-7036

 

Bases de Dados, Diretórios, Repositórios e/ou Indexadores

 GoogleScholar  BASE - Bielefeld Academich Search EngineResultado de imagem para logo cabi abstracts