Lista 1 - Teoria de Grafos - Provas

Lista de Exercícios I

1. Pesquise sobre as árvores abaixo. Defina, dê exemplo, desenhe o grafo respectivo, explique o funcionamento (operações básicas), indique principais aplicações e faça uma análise comparativa:

        i. Árvores balanceadas(B, Rubro-Negra, outras)

                i.1) Árvore B

                São árvores de busca de múltiplos caminhos, balanceadas e com eficientes         mecanismos de autobalanceamento. Foi projetada para funcionar  especialmente em         memória secundária. E por permitir fazer operações numa complexidade de tempo         logarítmica ela é muito empregada em aplicações de grandes quantidades de informação         (banco de dados, por exemplo).

                Os nós da árvore B, são comumente chamados de páginas. A ordem M, é o número         máximo de filhos que uma página possui, logo o número máximo de chaves de uma pagina é         M-1. A página raiz possui ao menos duas páginas filhas, com exceção de quando ela é uma         folha.  Seu balanceamento deve-se ao fato de todos as suas páginas filhas estarem no mesmo         nível, isto é, a mesma distância da raiz.

                Operações Básicas:

                1) Busca: é semelhante à busca binária, com a diferença de existir vários caminhos         para os nós seguintes dependendo da ordem da árvore(e não apenas dois, como na binária).         Portanto, a chave primeiramente é comparada com todos os registros da página raiz, caso         não seja encontrada, a pesquisa continua na sub-árvore aonde possa estar o registro,         iniciando o processo novamente, até que percorra a página folha, identificando a ausência da         chave na árvore.

2) Inserção: é realizada nas páginas folhas, e pode ocorrer dois casos de inserção, o primeiro, é quando ainda há espaço para a inclusão de uma chave(número de chaves menor que M-1), e o segundo é quando a página folha está completa (número máximo de chaves, M-1).

                3) Remoção: pode ser realizada em qualquer página(folha ou não) na árvore B,         existem pelo menos 5 casos de remoção, mas todos devem garantir que as propriedades da         árvore B sejam mantidas. Abaixo segue um exemplo em que deseja retirar a chave 9, da         árvore B de ordem 4, onde a chave é deslocada para um local na página folha, e só então é         excluída:

                4) Árvore Rubro-Negra

                É uma árvore binária de busca, onde cada nó tem um atributo de cor: vermelho ou         preto. Seus nós folhas não apontam para NULL, e sim para nós fictícios, que serão as folhas         da árvore. Ela possui as seguintes propriedades:

                1 – Todo nó da árvore ou é vermelho ou preto

                2 – A raiz é preta

                3 – Todas as  folhas  são pretas

                4 – Se um nó é vermelho, então seus filhos são pretos

                    5 – E para todo nó, o caminho partindo deste até as folhas descendentes terão a                         mesma quantidade de nós pretos.

                A árvore rubro-negra é complexa, mas como as propriedades asseguram que o         caminho mais longo da raiz a qualquer folha não seja maior que duas vezes que o caminho         mais curto da raiz a qualquer outra folha nessa árvore, isso nos resulta numa árvore         aproximadamente balanceada. Assim como na inserção e na remoção, a busca também         precisa do tempo de pior caso proporcional a altura da árvore, permite que árvores         rubro-negras sejam eficientes no pior caso.

                 Operações Básicas:

                Inserção: inicia-se pela raiz e compara-se as chaves ate encontrar a subárvore vazia,         onde cria um nó. Esse novo nó é vermelho para garantir a condição preta (5). Se após a         inserção for quebrada qualquer uma das propriedades, devem ser feitas rotações e/ou         inversão de cores dos nós.

                Remoção: existem dois tipos de remoção: a efetiva (física) e a preguiçosa (virtual).

        Exemplo de Árvore Rubro-Negra

[pic 1]

http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png

                i.3) Outras: Árvore AVL

                É uma árvore binária de busca, eficiente quando comparada árvore de busca binária         degenerada, pois como possui altura bem menor, a quantidade necessária de comparações         diminui significantemente. Esta é considerada balanceada quando, para cada nó, a diferença         entre as alturas de suas árvores direita e esquerda são no máximo 1. Diferença essa chamada         de Fator de Balanceamento(FB).

                Existem quatro tipos de restaurações numa árvores AVL, para que ela fique         balanceada seguindo suas propriedades. Essa restauração se chamam rotações, onde a         depender do valor do FB será realizada alguma das rotações:

• Rotação Simples à Direita, caso o FB = 1
• Rotação Simples à Esquerda, caso o FB = -1
• Rotação Dupla à Direito, caso o FB = 2
• Rotação Dupla à Esquerda caso o FB= -2

        ii. Árvores para classificação e recuperação (tries, Patrícias, outras)

                ii.2) Patrícias (PATRICIA - Practical Algorithm to Retrieve Information Coded         in Alphanumeric)

As árvores patricias foram criadas a partir da necessidade de localizar palavras-chaves ou strings em conjuntos enormes, que contenham uma grande quantidade         das mesmas em conjunto, de maneira rápida e eficiente. Assim, um aspecto relevante muito tratado pela Patricia é a busca por segmentos de palavras se assim o usuário desejar.