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

Autores

  • Edwardes Amaro Galhardo Instituto \Federal do Tocantins - IFTO Universidade Federal de Goiás - UFG
  • Cassio Martins Carlos Universidade Federal de Goiás - UFG
  • João Augusto Arce Santana Universidade Federal de Goiás - UFG
  • Vinicius Carvalho Lopes Universidade Federal de Goiás - UFG
  • Antonio Carlos de Oliveira Júnior Universidade Federal de Goiás - UFG

DOI:

https://doi.org/10.47236/2594-7036.2020.v4.i3.124-131p

Palavras-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

Não há dados estatísticos.

Métricas

Carregando Métricas ...

Biografia do Autor

Edwardes Amaro Galhardo, Instituto \Federal do Tocantins - IFTO Universidade Federal de Goiás - UFG

Professor EBTT/Computação/Campus PalmasMestrando em Ciência da Computação/UFG/Instituto de Informática

Cassio Martins Carlos, Universidade Federal de Goiás - UFG

Mestrando em Ciência da Computação/UFG/Instituto de Informática

João Augusto Arce Santana, Universidade Federal de Goiás - UFG

Mestrando em Ciência da Computação/UFG/Instituto de Informática

Vinicius Carvalho Lopes, Universidade Federal de Goiás - UFG

Mestrando em Ciência da Computação/UFG/Instituto de Informática

Antonio Carlos de Oliveira Júnior, Universidade Federal de Goiás - UFG

Professor Adjunto 4 do Instituto de Informática daUniversidade Federal de Goiás - UFG

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

2020-07-01

Como Citar

GALHARDO, Edwardes Amaro; CARLOS, Cassio Martins; SANTANA, João Augusto Arce; LOPES, Vinicius Carvalho; JÚNIOR, Antonio Carlos de Oliveira. Uma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras. Revista Sítio Novo, Palmas, v. 4, n. 3, p. 124–131, 2020. DOI: 10.47236/2594-7036.2020.v4.i3.124-131p. Disponível em: https://sitionovo.ifto.edu.br/index.php/sitionovo/article/view/582. Acesso em: 18 jun. 2025.

Edição

Seção

Artigo Científico