Arvores binarias

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1706 palavras )
  • Download(s) : 0
  • Publicado : 19 de junho de 2011
Ler documento completo
Amostra do texto
UNIVERSIDADE FEDERAL DO PARÁ – UFPA CAMPUS SUL E SUDESTE DO PARÁ – MARABÁ FACULDADE DE COMPUTAÇÃO – FACOM CURSO BACHAREADO EM SISTEMAS DE INFORMAÇÃO - SI

ÁRVORES BINÁRIAS DE BUSCA BALANCEADA

MARABÁ – PARÁ 2011

UNIVERSIDADE FEDERAL DO PARÁ – UFPA CAMPUS SUL E SUDESTE DO PARÁ – MARABÁ FACULDADE DE COMPUTAÇÃO – FACOM CURSO BACHAREADO EM SISTEMAS DE INFORMAÇÃO - SI

DENIS PERERIRA DEOLIVEIRA EVERTON PAIXÃO FRANCISCO OLTEN GOUVEIA PORTO NETO MARCELA GOMES HERINGER ROBSON PINHEIRO LOUZADA RONALD BRUNO PANTOJA LOBATO

ÁRVORES BINÁRIAS DE BUSCA BALANCEADA

Trabalho apresentado à disciplina Estrutura de Dados do curso de Bacharelado em Sistemas de Informação, como requisito de avaliação para obtenção de nota, orientado pelo professor Francisco Neto – UFPA.

MARABÁ – PARÁ 2011 Sumario
1. Introdução....................................................................................................................04 2. Árvores rubro-negras...................................................................................................04 3. Árvores AVL...............................................................................................................07 4.Considerações finais....................................................................................................11 5. Referencial Bibliográfico............................................................................................12

1. Introdução
Árvores são estruturas de dados extremamente úteis em muitas aplicações. Uma árvore é formada por um conjunto finito T de elementosdenominados vértices ou nós de tal modo que se T = 0 a árvore é vazia, caso contrário temos um nó especial chamado raiz da árvore (r), e cujos elementos restantes são particionados em m>=1 conjuntos distintos não vazios, as subárvores de r, sendo cada um destes conjuntos por sua vez uma árvore. Neste segmento estudaremos a seguir os principais conceitos de árvores rubronegras e árvores AVL que sãoambas árvores binárias de busca balanceadas que garantem inserção, remoção e busca em tempo logarítmico.

2. Árvores rubro-negras
São arvores binárias de busca balanceadas que garantem a inserção, remoção e busca em tempo logaritmo, são recomendadas para atividades de maiores remoções e são arvores projetadas para busca de dados na memória principal (RAM). Cada nó de uma arvore binária éconstituído dos seguintes campos: cor (1 bit): pode ser vermelho ou preto. key (e.g. inteiro): indica o valor de uma chave. left, right: ponteiros que apontam para a sub-árvore esquerda e direita, respectivamente. pai: ponteiro que aponta para o nó pai. O campo pai do nó-raiz aponta para nil. Exemplo de uma arvore rubro-negra: O ponteiro pai serve para facilitar a operação da árvore rubro-negra. Quando umnó pai não possui um filho (esquerda/direita), supões-se que ao invés de apontar para o nil, ele aponta para um nó fictício, que será uma folha da arvore. Abaixo se apresentam as características de uma arvore rubro-negra. Todo nó da árvore ou é vermelho ou é preto. A raiz é preta. Toda folha (nil) é preta.
4

Se um nó é vermelho, então ambos os filhos são pretos. Para todo nó, todos os caminhosdo nó até as folhas descendentes contêm o mesmo número de nós pretos. Exemplo de uma arvore rubro-negra:

A busca, inserção e remoção têm complexidade de tempo de O(h) = O(log n). Vale lembrar que Inserções e remoções feitas numa árvore rubro-negra podem modificar a sua estrutura. Precisamos garantir que nenhuma das propriedades de árvore rubro-negra seja violada. Para isso podemos ter que mudara estrutura da árvore e as cores de alguns dos nós da árvore. A mudança da estrutura da árvore é feita por dois tipos de rotações em ramos da árvore: left-rotate e right-rotate. Exemplo usando left-rotate:

5

Algoritmo left-rotate:
left-rotate(T, x): 1: y rigft[x] 2: right[x] left[y] 3: if left[y] 6= nil[T] then 4: pai[left[y]] x 5: end if 6: pai[y] pai[x] 7: if pai[x] = nil[T] then 8:...
tracking img