Estrutura de Dados - Arvores

Estrutura de Dados - Arvores

  • Motivação

  • Definição

  • Representação

  • Alocação

  • Exemplos

  • Principais Conceitos

    • Caminho
    • Altura, Nível e Grau de um nó
    • Árvore ordenada
    • Árvores isomorfas
    • Árvore cheia

  • As listas ligadas fornecem usualmente maior flexibilidade que as matrizes, mas são estruturas lineares e é difícil utilizá-las para uma representação hierárquica de objetos.

  • Embora as pilhas e filas reflitam-se em alguma hierarquia, elas são limitadas a somente uma dimensão.

  • Para superar estas limitações, introduzimos um novo tipo abstrato de dados chamado de árvore.

  • Árvores admitem tratamento computacional eficiente quando comparadas às estruturas mais genéricas como os grafos (mais flexíveis e complexos).

  • Exemplos de utilização de árvores:

    • Organização de pastas de um computador (árvore de diretórios)
    • Organogramas
    • Árvores de decisão
    • Resolução de expressões aritméticas
    • Tabela de um campeonato de futebol

  • Diferente de uma árvore natural, as árvores do tipo abstrato são representadas de cima para baixo, com a raiz no topo e as folhas na base. A raiz é um nó que não tem ancestrais; ele só pode ter filhos. As folhas, por outro lado, não possuem filhos.

  • Em uma definição mais formal, uma árvore não vazia consiste em um conjunto de nós, onde:

    • Existe um nó raiz.
    • Todo nó possui exatamente um pai, exceto o raiz, que não possui pai e que é ancestral de todos os demais nós.
    • Os nós que não possuem filhos são chamados de folhas ou terminais.
  • Se o conjunto de nós é vazio, dizemos que a árvore é vazia.

  • Um conjunto de árvores disjuntas forma uma floresta.

  • Os filhos de um nó são sub-árvores deste.

ADJACÊNCIA (ALOCAÇÃO ESTÁTICA)

  • ADJACÊNCIA (ALOCAÇÃO ESTÁTICA)

  • Nesta modalidade, os nós da árvore são representados de forma sequencial na memória.

  • Os números que aparecem à direita da informação de cada nó indicam o grau do nó correspondente.

  • Não é conveniente para representar árvores, na maioria dos casos, devido às dificuldades que oferece para a manipulação da estrutura (inserções, remoções, busca etc).

ENCADEADA (ALOCAÇÃO DINÂMICA)

  • ENCADEADA (ALOCAÇÃO DINÂMICA)

  • Alternativa mais adequada para a manipulação de árvores.

  • Cada nó possui um campo para guardar sua informação (chave), e campos de referência para suas subárvores.

  • O problema principal deste esquema é a possibilidade dos nós terem números diferentes de subárvores. A solução imediata é limitar o número de subárvores.

CAMINHO:

  • CAMINHO:

  • Uma sequência de nós distintos v1, v2, ..., vk, tal que para cada nó (vértice) vi (i variando de 1 a k-1), vi é pai de vi+1.

  • Diz-se que v1 alcança vk, e que vk é alcançado por v1.

  • Um caminho de vk vértices é obtido pela sequência de k-1 pares. O valor k-1 é o comprimento do caminho.

ALTURA:

  • ALTURA:

  • A altura de um nó vi é o maior caminho deste até uma folha.

  • Se o nó vi é uma folha, sua altura é zero.

  • A altura de uma árvore é calculada pela altura de sua raiz.

  • Uma árvore vazia tem altura -1.

NÍVEL:

  • NÍVEL:

  • O nível, ou profundidade, de um nó vi é o comprimento do caminho da raiz até o nó em questão.

  • Se vi é a raiz da árvore, seu nível é 0.

  • Formalmente definindo, o nível de vi é 0, se vi é a raiz da árvore. Caso contrário, o nível de vi é 1 + n, onde n é o nível do pai de vi.

GRAU:

  • GRAU:

  • O grau de saída, ou apenas grau, de um nó vi é a quantidade de filhos dele.

  • O grau de uma árvore é o maior valor de grau de seus vértices.

  • Calcule o grau, nível e altura de cada um dos vértices da árvore a seguir:

ÁRVORE ORDENADA X ORIENTADA:

  • ÁRVORE ORDENADA X ORIENTADA:

  • Quando a ordem das subárvores de cada nó é significativa, dizemos que a árvore é ordenada. Neste caso, pode-se falar em primeira subárvore, segunda subárvore etc. Geralmente a ordenação se dá da esquerda para a direita.

  • Quando a ordem das subárvores não é relevante, dizemos que a árvore é orientada, uma vez que apenas a orientação dos nós é importante.

ÁRVORES ISOMORFAS:

  • ÁRVORES ISOMORFAS:

  • De uma forma geral, duas árvores não ordenadas são isomorfas quando puderem se tornar coincidentes através de uma permutação na ordem das subárvores de seus nós. Duas árvores ordenadas são isomorfas somente se forem coincidentes.

ÁRVORE CHEIA:

  • ÁRVORE CHEIA:

  • Uma árvore de grau g está cheia se todos os seus nós não terminais estão com o número máximo (g) de filhos, e se as folhas estão no mesmo nível.

  • Uma árvore de grau g está cheia se todos os seus níveis estão com a quantidade máxima de nós.

  • A quantidade máxima de nós de um nível n de uma árvore de grau g é gn.

  • Uma árvore de grau g e altura h tem no máximo (gh+1 – 1) / (g - 1) nós.

SUBÁRVORE E SUBÁRVORE PARCIAL:

  • SUBÁRVORE E SUBÁRVORE PARCIAL:

  • Seja T uma árvore, e v um nó de T. Seja Tv a subárvore de T de raiz v. Seja S um conjunto de elementos de Tv. T’ = Tv – S é uma subárvore parcial de T.

  • Observe que a diferença entre uma subárvore de raiz v e uma subárvore parcial de raiz v é que a primeira contém obrigatoriamente todos os descendentes de v; enquanto que a segunda, não necessariamente.

  • Definição

    • Árvore binária
    • Árvore estritamente binária
    • Árvore completa
    • Altura máxima e mínima
  • Representação

  • Alocação

  • Percurso

    • Largura
    • Profundidade
  • Conversão para árvore binária

ÁRVORES BINÁRIAS:

  • ÁRVORES BINÁRIAS:

  • São estruturas do tipo árvore, onde o grau de cada nó é menor ou igual a 2.

  • Distinguem-se as subárvores de um nó entre subárvore da direita e subárvore da esquerda. Assim, se o grau de um nó for igual a 1, deve ser especificado se a sua subárvore é a da esquerda ou a da direita.

  • Se T é uma árvore binária com altura h e n nós, então: 2h + 1 – 1 ≥ n ≥ h + 1.

ÁRVORE ESTRITAMENTE BINÁRIA, COMPLETA E CHEIA

  • ÁRVORE ESTRITAMENTE BINÁRIA, COMPLETA E CHEIA

  • Uma árvore é estritamente binária se todos os seus nós possuem 0 ou 2 filhos.

  • Uma árvore é completa quando todas as suas folhas estão nos dois últimos níveis. Ou seja, se um nó não possui pelo menos uma das subárvores (esquerda ou direita), ele deve estar no último ou no penúltimo nível.

  • Uma árvore binária cheia é aquela em que, se v é um nó com alguma de suas subárvores vazias, então v se localiza no último nível.

ALTURA MÁXIMA E MÍNIMA:

  • ALTURA MÁXIMA E MÍNIMA:

  • A altura h de uma árvore binária com n nós está entre o valor de log2n como inteiro, arredondado para menos, e o valor de n. Logo:  log2n ≤ h ≤ n - 1.

  • O pior caso acontece com as árvores degeneradas ou ziguezagues.

  • O melhor caso acontece com a árvore completa.

DINÂMICA:

  • DINÂMICA:

  • Cada nó possui um campo para guardar sua informação (chave) k, e campos de referência para suas subárvores direita e esquerda.

  • ESTÁTICA:

  • Não indicada, pois requer alocação de espaço considerando uma árvore cheia (já que deve ser alocado espaço para todas as possíveis subárvores).

  • Os filhos de um nó i ficam nas posições 2i (esquerdo)e 2i + 1 (direito).

  • Se um nó é folha, ele deve estar no último nível, ou seus filhos estão vazios.

EXEMPLOS:

  • EXEMPLOS:

  • Tomemos como base a árvore ao lado.

  • Se ela fosse cheia, ela teria 7 nós, com 4 no último nível.

  • DINÂMICA:

  • ESTÁTICA:

Processo em que se visita cada nó da árvore apenas uma vez.

  • Processo em que se visita cada nó da árvore apenas uma vez.

  • Pode ser visto como uma linearização da árvore (todos os nós em uma linha).

  • O percurso diz apenas que cada nó deve ser visitado uma única vez; mas não especifica em que ordem estes nós devem aparecer. Desta forma, para n nós, tem-se n! possíveis listagens da árvore.

  • Para a árvore a seguir, por exemplo, existem 6 possíveis listagens.

  • Ex.: a b c

  • a c b

  • b a c

  • b c a

  • c a b

  • c b a

  • Em face da abundância de percursos, e da inutilidade da maioria deles, o estudo destes se restringe a duas classes: extensão e profundidade.

Consiste em visitar cada nó começando do nível mais baixo (ou mais alto) e movendo para baixo (ou para cima) nível a nível, visitando nós em cada nível da esquerda para a direita (ou da direita para esquerda).

  • Consiste em visitar cada nó começando do nível mais baixo (ou mais alto) e movendo para baixo (ou para cima) nível a nível, visitando nós em cada nível da esquerda para a direita (ou da direita para esquerda).

  • Neste caso, já quatro situações distintas:

    • De cima para baixo, da esquerda para a direita (mais utilizado).
    • De cima para baixo, da direita para esquerda.
    • De baixo para cima, da esquerda para a direita.
    • De baixo para cima, da direita para a esquerda.
  • Vejamos os percursos na árvore a seguir:

    • a b c
    • a c b
    • b c a
    • c b a

DE CIMA PARA BAIXO, DA DIREITA PARA A ESQUERDA:

  • DE CIMA PARA BAIXO, DA DIREITA PARA A ESQUERDA:

  • Inicialmente, o nó raiz é colocado numa fila de nós.

  • Enquanto houver elementos na fila:

    • Retirar e listar o nó que está na cabeça da fila
    • Enfileirar os filhos do nó que foi retirado da fila.

Consiste basicamente em três tarefas:.

  • Consiste basicamente em três tarefas:.

    • V – Visitar um nó (e listar o seu valor).
    • L – Percorrer a subárvore da esquerda (left).
    • R – Percorrer a subárvore da direita (right).
  • Estas três tarefas podem estar organizadas de 6 formas distintas (3!):

    • VLR  a b c
    • RLV  c b a
    • LVR  b a c
    • RVL  c a b
    • LRV  b c a
    • VRL  a c b
  • Os percursos I, III e V são os mais conhecidos. São percursos em que os movimentos são sempre da esquerda para a direita. Seus nomes são, respectivamente, pre-order, in-order e pos-order.

Considerando que o percurso na árvore comece pela raiz, desça pela sua esquerda (e pela esquerda de cada nó), até chegar novamente à raiz, agora pela direita, podemos caracterizar cada um dos três percursos como:

  • Considerando que o percurso na árvore comece pela raiz, desça pela sua esquerda (e pela esquerda de cada nó), até chegar novamente à raiz, agora pela direita, podemos caracterizar cada um dos três percursos como:

  • Pre-order: o nó é listado da primeira vez que passa por ele.

  • In-order: o nó é listado da segunda vez que passa por ele.

  • (depois de listar a sua subárvore esquerda, ainda que vazia).

  • Pos-order: o nó é listado da última vez que passa por ele.

  • (depois de listar a sua subárvore direita, ainda que vazia).

EXERCÍCIO:

  • EXERCÍCIO:

  • Listar os nós da árvore a seguir em pre-order, in-order e pos-order.

  • RESPOSTAS:

  • pre-order: a b d c e g h f

  • in-order: d b a g e h c f

  • pos-order: d b g h e f c a

Uma árvore com grau maior que 2 pode ser transformada em binária, se ligarmos os nós irmãos e removermos a ligação entre um nó pai e os nós filhos, exceto as do primeiro filho.

  • Uma árvore com grau maior que 2 pode ser transformada em binária, se ligarmos os nós irmãos e removermos a ligação entre um nó pai e os nós filhos, exceto as do primeiro filho.

  • Se um nó tem n filhos, para i de 2 até n, o nó i passa a ser visto como filho direito do seu irmão i-1.

  • Tomemos como exemplo a árvore a seguir:

  • Motivação

  • Definição

  • Representação

  • Alocação

  • Custo de Manutenção

Examinando-se a representação de uma árvore binária, pode-se constatar a existência de muitas referências (para subárvores) nulas nos nós.

  • Examinando-se a representação de uma árvore binária, pode-se constatar a existência de muitas referências (para subárvores) nulas nos nós.

  • De fato, é fácil verificar que em uma árvore binária de n nós, ocorrem n+1 referências nulas. A árvore a seguir possui 5 nós e 6 referências nulas:

  • O principal motivo de se ter uma árvore binária alinhada (ou costurada) é a utilização das referências nulas, para facilitar o caminhamento sobre a árvore.

As árvores alinhadas, são também chamadas de árvores amarradas ou costuradas.

  • As árvores alinhadas, são também chamadas de árvores amarradas ou costuradas.

  • As arvores alinhadas devem considerar um percurso de caminhamento. Veremos aqui árvores alinhadas nos três percursos em profundidade (pre-order, pos-order e in-order).

  • São árvores binárias cujas referências nulas de seus nós são substituídas por “amarras” ou “costuras”, que são, na realidade, referências a outros nós da árvore, considerando uma ordem de caminhamento, como segue:

    • Se a subárvore esquerda de um nó é vazia, a referência esquerda deste nó aponta para o seu predecessor.
    • Se a subárvore direita de um nó é vazia, a referência direita deste nó aponta para o seu sucessor.

São utilizados dois campos adicionais (do tipo booleano) ao da árvore binária convencional, indicando se as referencias esquerda e direita são filhos (1) ou “costuras” (0).

  • São utilizados dois campos adicionais (do tipo booleano) ao da árvore binária convencional, indicando se as referencias esquerda e direita são filhos (1) ou “costuras” (0).

  • No exemplo a seguir temos a representação de uma árvore binária costurada em pre-order, e a representação da sua alocação.

O custo de manutenção de tais árvores é alto, considerando que após cada operação de inserção ou remoção de nós as costuras devem ser ajustadas.

  • O custo de manutenção de tais árvores é alto, considerando que após cada operação de inserção ou remoção de nós as costuras devem ser ajustadas.

  • Considerando que o percurso em árvores é geralmente para listar os nós da esquerda para a direita, pode-se desconsiderar as amarras à esquerda. Neste caso, teríamos uma árvore costurada (no percurso adotado) à direita.

  • Neste caso, apenas os sucessores seriam interessantes para serem utilizados nas “amarras” ou “costuras”.

  • No exemplo, temos uma árvore binária alinhada em pre-order à direita.

  • Definição

  • Busca

  • Inserção

  • Remoção

    • Por cópia
    • Por fusão
  • Exercícios

  • TAD

  • São árvores binárias em que todas as chaves da subárvore esquerda de um vértice (nó) são menores que a chave dele; e, analogamente, todas as chaves da subárvore direita deste nó são maiores que a chave dele.

  • A busca de um elemento é proporcional à altura da árvore.

Iniciando pela raiz da árvore. Para cada nó da árvore, comparar uma chave a ser localizada X com a chave do nó corrente V. Podem acontecer três situações:

  • Iniciando pela raiz da árvore. Para cada nó da árvore, comparar uma chave a ser localizada X com a chave do nó corrente V. Podem acontecer três situações:

  • Se X é igual à chave de V; retorne V.

  • Se X é menor que a chave de V; buscar X na subárvore esquerda de V.

  • Se X é maior que a chave de V; buscar X na subárvore direita de V.

  • A busca para quando X é encontrado, ou quando não há mais opções.

Fluxograma para localização de uma chave em uma árvore binária de busca:

  • Fluxograma para localização de uma chave em uma árvore binária de busca:

  • Considere:

  • K = chave do nó atual

  • X = chave procurada

Para inserir uma chave X em uma árvore binária de busca, segue-se um processo semelhante ao de busca.

  • Para inserir uma chave X em uma árvore binária de busca, segue-se um processo semelhante ao de busca.

  • Se a árvore estiver vazia, inserir a chave na raiz.

  • Se a chave X for menor que a chave do nó corrente, inserir X na subárvore esquerda deste.

  • Se a chave X for maior que a chave do nó corrente, inserir X na subárvore direita deste.

  • Todo nó é inserido nas folhas da árvore.

A complexidade deste processo é proporcional à quantidade de filhos (subárvores) que o nó a ser removido tem. Desta forma, existem três casos.

  • A complexidade deste processo é proporcional à quantidade de filhos (subárvores) que o nó a ser removido tem. Desta forma, existem três casos.

  • Se o nó não possui filhos, ele é removido e o ponteiro de seu ascendente imediato (pai) é atualizado para nulo.

  • Se o nó possui apenas um filho, ele é removido e o ponteiro de seu ascendente imediato (pai) é atualizado para o seu filho.

  • Se o nó possui os dois filhos, o processo de remoção pode se dar basicamente de duas formas:

    • Por fusão
    • Por cópia

CASO I:

  • CASO I:

  • EX.: Remover o nó que contém a chave 5 da árvore abaixo:

CASO II:

  • CASO II:

  • EX.: Remover o nó que contém a chave 6 da árvore abaixo:

CASO III (FUSÃO):

  • CASO III (FUSÃO):

  • Na subárvore esquerda (direita) do nó V a ser deletado, localizar o nó X mais à direita (esquerda). X passa a ser pai da subárvore direita (esquerda) de V. A raiz da subárvore esquerda (direita) de V assume o lugar dele. Em seguida, o nó V é removido.

  • EX.: Remover o nó que contém a chave 4 da árvore abaixo:

CASO III (CÓPIA):

  • CASO III (CÓPIA):

  • Na subárvore esquerda (direita) do nó V a ser deletado, localizar o nó X mais à direita (esquerda). A chave de X é copiada para V. O nó X é então removido da árvore seguindo um dos dois primeiros casos, dependendo do seu número de filhos (subárvores).

  • EX.: Remover o nó que contém a chave 4 da árvore abaixo:

  • Inserir em uma árvore binária de busca, na ordem em que aparecem, as seguintes chaves: 5 8 6 7 2 4 3 1 5 6 2 3.

  • Listar os nós da árvore do item a em extensão (de cima para baixo e da esquerda para a direita).

  • Listar os nós da árvore do item a em pre-order, pos-order e in-order.

  • Apagar, da árvore do item a, a chave 5, por fusão.

  • Apagar, da árvore do item a, a chave 5, por cópia.

  • Motivação

  • Definição

    • Heap de máximo
    • Heap de mínimo
  • Inserção

  • Remoção

  • Motivação

  • Definição

  • Rotação

    • Simples
    • Dupla
  • Inserção

  • Remoção

Comentários