Blog

Método de Pesquisa e de Ordenação Resumo. O propósito deste artigo é apresentar um Método de Pesquisa denominado Án,’ore 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 AVI- e entre o QuickSort e o MergeSort. troduçao OF6 Swipc nent pa Neste estudo, prete e-z_, fundamentos das es ru bem como seus obje Inclpals ras e Algorítmo Quicksort, As árvores binárias de busca Vermelho-preto, conhecidas ambém como Rubro-negras ou Red-Black Trees, que segundo seu criador Rudolf Bayer em 1972, é um método de pesquisa geralmente mais 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 1962 após uma série de refinamentos. É um método de ordenação mais á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 curso de Sistemas de Informação pela Faculdade Metropol tana 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. ara 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; – Nodos vermelhos que não sejam folhas possuem somente filhos pretos; 5- Todos os caminhos 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 hipótese pode ter grau de complexidade O(n), garantindo assim um bom funcionamento em apenas arvores 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 alguns nodos, para que as regras 4 e 5 sejam obedecidas. Esta inserção dando-se em uma árvore vazia basta alterar a cor do nodo para preto obedecendo assim à regra número 6. pic] A rotação pode ser executada tanto para a direita quanto para a esquerda e quantas vezes forem necessárias. Durante uma rotação apenas os ponteiros dos nodos envolvidos serão alterados, mantendo-se os demais valores dos mesmos.

Como exemplo, vemos também necessidade de uma rotação nos nodos caso haja inserção na cor vermelha sendo que seu antecessor também possui cor vermelha. Não podemos somente alterar a cor do nodo antecessor porque senão estaremos desobedecendo a regra número 5. [picl Assim como a inserção 3 composta de uma etapa de busca e de balanceamento da árvore (caso as propriedades ubro-negras tenham sido destruídas durante a operação). Haverá em alguns casos de remoção troca de valores se o nodo removido possuir dois filhos, a troca se dará entre um dos filhos e o nodo removido, sem alterar as propriedades da árvore. pode ser removido um nodo vermelho sem causar problemas, pois suas regras continuarão intactas.

O que não acontece se for removido um nodo preto, porque para a árvore manter o seu balanceamento deverá haver algumas operações de rotação e ou alteração de cor, pois a quantidade de nodos pretos em pelo menos um dos caminhos foi alterada. Existem dois tipos de remoção em uma árvore, a remoção efetiva que após as operações de rotação e alteração de cor a remoção do nodo é efetivamente realizada, restabelecendo-se as regras da árvore, e a remoção preguiçosa que consiste apena em marcar um determinado nodo como removido, sem retirá-lo efetivamente da árvore. 4 Vantagens e Desvantagens Vantagem: As árvores rubro-negras são geralmente mais utilizadas do que as árvores binárias, por terem implementações mais eficientes. Inserindo e removendo de forma inteligente para assegurar que a árvore permaneça balanceada O(log n).

Desvantagem: É uma árvore complexa, dependendo da inserção ou remoção é necessário alterar toda a estrutura da árvore ou boa parte dela. A distância entre raiz até as folhas podem ser até fator 2 sem falar que a dificuldade de entendimento e implementação é muito maior do que o da árvore AVI_. 5 Situações em que se apli se aplica A árvore rubro-negra é um tipo especial de árvore binária, utilizada para organizar dados que possam ser comparáveis, como são balanceadas não terá o caso da árvore de busca binária sem balanceamento, cujos registros são inseridos em ordem rescente ou decrescente, gerando uma árvore de altura igual a quantidade de elementos que ela possui. Podendo ser utilizadas em aplicações que não toleram um pior caso. Comparativo com outro método de pesquisa Comparando o funcionamento entre os métodos de pesquisa da Árvore rubro-negra e a Árvore AVI_, podemos notar que ambas são balanceadas tendo o mesmo grau de complexidade O(log n), o processo de inserção e remoção de árvores AVI_ e parecido com o processo de inserção e remoção da árvores rubro- negras. No entanto, uma inserção em uma arvore AVI_ pode requerer O(log n) rotações para restaurar a arvore, e a cada nserção e remoção se nao atender as condições propostas é realizada uma rotação simples à esquerda e à direita ou uma rotação dupla. Rotação simples à esquerda e a direita Rotação Dupla à esquerda e a direita Método de Ordenação Este método de orden S 6 ibilitará comparar as torna-o um método eficiente. É provavelmente também o mais utilizado em relação a outro algoritmo, criado por C. A. R.

Hoare em 1960 em visita a Universidade de Moscou como estudante, com a intenção de traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema riginal em subproblemas que possam ser resolvidos mais facilmente e rapidamente foi publicado após uma série de refinamentos me 1962. Sua principal característica consiste na escolha de um elemento para pivô (elemento já ordenado) e dividir os elementos a ordenar em dois subconjuntos na qual no primeiro subconjunto todos os elementos são menores ou iguais ao pivô, e no segundo subconjunto todos os elementos são maiores ou iguais ao pivô. Os dois subconjuntos são ordenados de forma recursiva.

Este algoritmo é rápido em boa parte dos casos onde aplicado, com complexidade média O(n log n); Entretanto no pior caso essa complexidade pode degradar para O(n2); e no melhor caso C(n) = n*logn n -n + 1 Este algoritmo implementa uma solução para a ordenação de um vetor baseado no famoso lema da informática “dividir para conquistar”. O que basicamente o QuickSort faz é ir dividindo o vetor, através da seleção de um pivô (elemento de referência), e ordenando depois cada parte. Este algoritmo pode-se resumir a sucessivas colocações de valores maiores que o pivô à direita e de valores menores à sua esquerda. O QuickSort funciona particionando o vetor recursivamente até que todos os elementos tenham tamanho