Estrutura de Dados - Arvores

Estrutura de Dados - Arvores

(Parte 1 de 2)

Slides 11 - Árvores

Conceitos Básicos

  • Árvores são estruturas de dados que seguem o conceito de hierarquia, a forma mais simples de definir a estrutura da arvore é a recursividade.

  • A arvore possui um conjunto de nós, e existe um nó principal chamado raiz.

  • Em uma definição mais formal, uma árvore é uma estrutura que contém um conjunto finito de um ou mais nós, sendo que um dos nós é especialmente designado como o nó raiz e os demais nós são particionados em 0 ou mais conjuntos disjuntos onde cada um desses conjuntos é em si uma árvore, que recebe o nome de sub-árvore.

  • Cada árvore tem apenas uma raiz. Os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas. Os nós que tem filhos são chamados nós internos.

  • Todo nó de uma árvore é a raiz de outra sub-arvore.

  • Existe a analogia com a arvore genealogica, portanto existe os nós filhos, pais, irmão, avós e tios de outro nó. Existe também analogia com descendente e ancestral.

  • O numero de filhos do nó é chamado grau de saída do nó.

  • Os nós folhas tem grau de saída 0.

  • Grau do nó: é o numero de sub-arvores que ele possui.

  • Grau da Árvore: O grau da àrvore é o maior entre os graus de seus nós.

  • Floresta: Uma floresta é o conjunto de zero ou mais àrvores.

  • Caminho: Quantidade de arestas existentes do nó A até o nó B.

  • Altura do nó: A altura de um nó é o maior caminho deste nó ate um nó folha, ou seja, é a quantidade de nós contando do nó até o nó folha. O nó folha tem altura 0.

  • Altura da Árvore: é igual ao maior nível de seus nós.

  • Nível ou Profundidade do nó: O nível ou profundidade de um nó é o tamanho do caminho (quantidade de nós visitados) da raiz até este nó.

  • Nivel ou Profundidade da raiz: O nível da raiz é 0.

Árvore Ordenada X Árvore 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 Isómorfas:

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.

Pode-se definir o conceito de ávores isomorfas quando elas tem a mesma relação de incidêcia entre nós mas são desenhadas de forma diferente, isto é, são distintas quan-do consideradas como ávores ordenadas.

Á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.

Árvore Binária

Definição 1: É um conjunto finito de nós que, ou é vazio, ou consiste de uma raiz ligando duas outras árvores binárias.

Definição 2: É um conjunto finito de nós que, ou está vazio, ou está divido em tres sub-conjuntos:

    • O nó denominado raiz.

    • Dois sub-conjuntos, cada um dos quais é em si outra arvore binária, chamados sub-arvore esquerda e sub-arvore direita.

  • Observação: Note que a árvore binaria não é um caso particular de arvore e sim um conceito diferente. Toda arvore binaria é uma arvore, mas nem toda arvore é uma arvore binaria, mesmo quando cada nó possui grau no maximo dois, pois os nós não são chamados filho esquerdo e filho direito.

Conceitos:

  • O numero máximo de nós no nivel i de um sub-arvore é 2 elevado a i.

  • Árvore estritamente binária é uma árvore em que cada nó possui 0 ou 2 filhos.

  • Árvore binária Completa: 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.

  • Árvore Binária Cheia: 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 Minima:

Alocação:

A alocação pode ser estática ou dinâmica.

  • Dinamica: Cada nó possui um campo para guardar sua informação (a chave) e campos de referencia para suas sub-arvores esquerda e direita.

  • Estática: Não é indicada pois seria necessária indicar o espaço alocado para todas as possíveis sub-arvores – desperdício de memória.

Representação:

A Representação de àrvore binaria pode ser implícita ou encadeada:

  • Representação Implicita: Implementação de arvores com vetores. Assim como as listas as arvores binarias podem ser implementadas utilizando-se o armazena-mento contiguo proporcionado pelos vetores. A ideia é armazenar os niveis sucessivos da arvore sequencialmente nos vetores. Essa representação é apropriada quando estamos trabalhando com arvores binarias completas, mas os processos de inserção e remoção ficam mais complexos, alem de tender a disperdiçar memória e ser pouco flexível.

  • Representação Encadeada: Para reduzir estes problemas computacionais, usa-se a representação encadeada, usando estruturas de dados e ponteiros.

      • Cada nó possui 3 campos: a informação, um ponteiro para a sub-arvore esquerda e um ponteiro para a sub-arvore direita.

      • A arvore é um ponteiro para seu nó raiz.

Percurso:

Processo que permite a visita a cada nó uma única vez. É como se fosse uma linearização da arvore. O percurso diz que deve-se visitar cada no uma única vez mas não explica como, então existem n maneiras de fazer essa visita. 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.

  • Extensão:

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:

I. De cima para baixo, da esquerda para a direita (mais utilizado).

II. De cima para baixo, da direita para esquerda.

III. De baixo para cima, da esquerda para a direita.

IV. De baixo para cima, da direita para a esquerda.

  • Profundidade: O percurso mais usado consiste em tres operações: visitar o nó (e imprimir o seu valor), percorrer a sub-arvore esquerda e percorrer a sub-arvore direita. Para tanto usamos os percursos pre-ordem, in-ordem e pos-ordem.

  • Travessia em Pré-Ordem

      • Se árvore vazia; fim

      • visitar o nó raiz

      • Percorrer em pré-ordem a sub-ávore esquerda

      • Percorrer em pré-ordem a sub-ávore direita

  • Travessia em In-Ordem

        • Se arvore vazia; fim

        • percorrer em in-ordem a sub-arvore esquerda

      • visitar o nó raiz

      • Percorrer em in-ordem a sub-ávore direita

  • Travessia em Pos-Ordem

  • Se arvore vazia; fim

  • Percorrer em pos-ordem a sub-arvore esquerda

      • Percorrer em pos-ordem a sub-ávore direita

      • visitar o nó raiz

aEexercicios

b c

dExercícios

1- Qual é a definição de cada um dos seguintes termos:

a) árvore

b) Sub-árvore

c) Grau de um nó

d) Grau de uma arvore

e) Nós folha, ou no terminal

f) Nós filhos de um nó

g) Nós irmãos de um nó

h) Altura de uma arvore

i) Nível de um nó

j) Arvore binária

k) Arvore estritamente binária

2. Qual é o número do nível da raiz de uma avore?

3. Qual é a altura de uma árvore vazia?

4. Qual numero mínimo de nós que pode conter uma avore de grau n e altura h?

Slides 12 - Árvore Binária de Busca

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 a altura da arvore.

  • Função Busca:

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.

(Parte 1 de 2)

Comentários