Open AccessUma comparação do cálculo da mediana de inteiros contidos em árvores AVL e Rubro-Negras
Author(s) -
Edwardes Amaro Galhardo,
Cassio Martins Carlos,
João Augusto Arce Santana,
Vinícius Carvalho Lopes,
Antônio Carlos de Oliveira Júnior
Publication year - 2020
Publication title -
revista sítio novo
Language(s) - Portuguese
Resource type - Journals
ISSN - 2594-7036
DOI - 10.47236/2594-7036.2020.v4.i3.124-131p
Subject(s) - humanities , political science , philosophy
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.