Abordagem de arvores rubro-negra

Abordagem de Árvores Rubro-Negra e AVL

Universidade Federal do Pará – UFPA
Marabá – PA – Brasil

Edinei Lustosa, Eliton Miranda, Janailda Bezerra, Mª Eliane Sobrinho, Priscila Alves, Raul Freire e Thiago Brito.

loirinhalustosa,elitoneletrik,janny_katypa,MEFASOBRI,priscilasi09,raul_aguiarrm,thiagobritocarneiro {@hotmail.com}

Resumo: O presente trabalho fará uma abordagem sobre a definição e a utilização de arvores rubro-negra e arvores AVL, bem como exemplos das mesmas. Vale ressaltar que esse trabalho é de caráter exploratório e para o seu desenvolvimento baseou-se em pesquisa bibliográfica. 1. Introdução
Segundo Veloso et al., (1983), árvores são estruturas de dados utilizadas em casos onde os dados, ou objetos, a serem representados possuem uma hierarquia. Uma aplicação para árvore é a representação de expressões aritméticas, que podem ser representadas sob a forma de árvores binárias, de tal forma que a hierarquia dos operadores fique bem definida. Outra aplicação de árvores binárias é utiliza-la no registro de dados de tal maneira que, ao final da operação de armazenamento, os dados estejam ordenados, segundo um dado critério, independentemente da ordem de armazenamento.
Este trabalho está estruturado da seguinte forma: na seção 2 será tratada a definição de árvores; na seção 3 arvores rubro-negra; na seção 4 arvores AVL; e na seção 5 as considerações finais.

2. Árvores
Árvores são estruturas de dados que caracterizam uma relação entre os dados que a compõem. A relação existente entre estes dados (denominados nós) é uma relação de hierarquia ou de composição, onde um conjunto de dados é hierarquicamente subordinado a outro.
Uma árvore é definida como um conjunto finito T de um ou mais nós, tais que: a) Existe um nó denominado raiz; b) Os demais nós formam m>0 conjuntos disjuntos S1, S2, ...., Sm, onde cada um destes conjuntos é uma árvore Si (1<i<n) recebem a denominação de subárvores.

Figura 1: