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.