Metodo de pesquisa e ordenacao

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1447 palavras )
  • Download(s) : 0
  • Publicado : 20 de março de 2011
Ler documento completo
Amostra do texto
Método de Pesquisa e de Ordenação

Resumo.

O propósito deste artigo é apresentar um Método de Pesquisa denominado Árvore rubro-negra e o Método de Ordenação QuickSort, caracterizando-os, apresentando suas funcionalidades, suas complexidades, suas vantagens e desvantagens, e situações em que se aplica. Por fim foi feita uma comparação entre a Árvore rubro-negra e a Árvore AVL, eentre o QuickSort e o MergeSort.

Introdução

Neste estudo, pretende-se estabelecer os principais fundamentos das Árvores rubro-negras e do Algorítmo Quicksort, bem como seus objetivos e características.
As árvores binárias de busca Vermelho-preto, conhecidas também como Rubro-negras ou Red-Black Trees, que segundo seu criador Rudolf Bayer em 1972, é um método de pesquisa geralmentemais utilizado por terem implementações mais eficientes, além das operações básicas (inserção, remoção e pesquisa...) existe outro diferencial em relação às árvores binárias tradicionais, que é um bit extra que armazena a cor (vermelho ou preto) em cada nodo presente na árvore.
O Algoritmo Quicksort foi inventado pelo cientista Charles Antony Richard Hoare em 1960, sendo publicado em 1962após uma série de refinamentos. É um método de ordenação mais rápido e eficiente que se conhece, e provavelmente o algoritmo mais usado dentre todos os tipos existentes.
A Idéia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores. Os problemas menores são ordenados independentemente e os resultados são combinados para produzir a solução final.

*Bacharelno curso de Sistemas de Informação pela Faculdade Metropolitana de Belo Horizonte

Método de Pesquisa

Este método de pesquisa nos possibilitará explicar as semelhanças e diferenças entre as árvores binárias de busca. O estudo dar-se-á as Árvores rubro-negras.

1 Características

As árvores rubro-negras foram criadas por Rudolf Bayer em 1972, 10 anos após a criação dasárvores AVL, sob o nome de “Árvores Binárias Simétricas”.
É um tipo de árvore de busca binária balanceada, é uma árvore complexa, mas tem um bom tempo de execução para suas operações, sendo eficiente na prática.
Para que as árvores rubro-negras permaneçam balanceadas além da característica que dá nome à árvore, vindo de um bit extra em cada nodo que determina se esta é “vermelha” ou“preta”, devem-se obedecer às seguintes regras:
1- Cada nodo da árvore possui um valor;
2- A cada nodo inserido na árvore deve-se obedecer ao esquema de menor para o lado esquerdo e maior para o lado direito;
3- A cada nodo é associada uma cor: vermelha ou preta;
4- Nodos vermelhos que não sejam folhas possuem somente filhos pretos;
5- Todos oscaminhos a partir da raiz até qualquer folha passam obrigatoriamente pelo mesmo número de nodos pretos;
6- O nodo raiz da árvore é sempre preto.

[pic]

2 Complexidade

As árvores rubro-negras possuem complexidade logarítmica O(log n), em suas operações (inserção, remoção e busca), para qualquer que seja a altura da árvore.
Já em uma Árvore não balanceada napior hipótese pode ter grau de complexidade O(n), garantindo assim um bom funcionamento em apenas árvores de pequena altura.

3 Funcionamento

São árvores balanceadas seguindo um critério ligeiramente diferente do usado em árvores de busca binária, ela é complexa, mas tem um bom tempo de execução para suas operações sendo eficiente na prática.
Toda vez que for realizada uma operação naárvore, regras são testadas, para que ela permaneça balanceada, não podendo desobedecer nenhuma das regras, caso aconteça será realizado rotações ou ajuste de cores.
A inserção começando por uma busca da posição, se dá partindo da raiz até o valor mais próximo ao qual vai ser inserido. Após analisar o seu antecessor se este for vermelho haverá necessidade de alterar as cores de...
tracking img