QUESTIONÁRIO 04 - ÁRVORES AVL (BALANCEADAS)

1)         Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Para construirmos uma árvore balanceada ou AVL primeiramente precisamos utilizar o conceito de ABB. Portanto explique o conceito de árvore balanceada ou AVL?

Resposta: Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos. Para definir o balanceamento é utilizado um fator específico para nós. O Fator de Balanceamento (FB) é utilizado pela seguinte fórmula:

FB(nó) = altura(dir)  - altura(esq)

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

2)         Sabendo que podemos inserir elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de inserção na árvore AVL e do seu algoritmo.

Resposta: Primeiro, c é inserido como folha A, seguindo o algoritimo do caso geral das ABBs. Se depois da inserção a árvore permanece AVL, então nada mais temos a fazer. Caso contrário, é necessário remanejar a árvore.

3)         Sabendo-se que os conceitos de rotação simples a direita/esquerda e de rotação dupla a direita/esquerda são essenciais na inserção de elementos na árvore avl. Explique os conceitos de rotação simples e rotação dupla.
Resposta: Uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".

4)         Sabendo que podemos retirar elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de remoção na árvore AVL e do seu algoritmo.
Resposta: A remoção deve ser dada por uma rotação em torno do nó a ser removido, a fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.

1. Remover X da árvore AVL usando o mesmo algoritmo de remoção de um nó em uma árvore de busca binária. Recursivamente, empilhar cada nó que é visitado a partir do nó raiz até o nó X, incluindo-o;
2. Verificar se a pilha está vazia
• Se sim, o algoritmo termina.
• Senão, vá para o passo (3).
3. Desempilhar um nó e verificar se a diferença de altura entre a sub-árvore da esquerda e da direita desse nó é maior que 1.
• Se sim, você precisará rotacionar os nós. Dependendo do tipo de rotação realizada, o algoritmo pode não terminar aqui. Se ele não terminar, vá para o passo (2).
• Senão, vá para o passo (2). 

Note que a operação de remoção pode ser realizada em tempo O(lg(n)). Na remoção de um elemento em uma árvore AVL, pode haver a necessidade de realizar mais de duas rotações (o que não acontece na inserção), podendo se estender para uma rotação em cada nível (O(log(n))) no pior caso. A figura a seguir mostra um exemplo deste caso:

5)         Através dos conceitos discutidos, dê dois exemplos de inserção em árvores AVL e dois exemplos de remoção em árvores AVL.

Resposta: Exemplo de remoção:                                                                                                            Exemplo 1 : Dada a árvore abaixo, retirando o 5 resulta uma arvore desbalanceada no nó 10(b). A partir daí, raciona-se como se estivéssemos inserindo: que nó inserido teria causado esse desequilíbrio? O 30. Aplicando os conhecimentos de inserção em arvore AVL, constata-se que uma rotação simples a esquerda resolve o problema. O resultado esta na AVL(C).

 

Exemplo 2: Retirando a folha 12 de (a), na figura abaixo, desbalanceia a raiz (b); supondo-se a inserção recente de 8, corrige-se o desequilíbrio mediante uma rotação dupla a esquerda (c).

Exemplo de inserção:

Exemplo 1: Inserção seqüencial ( Chaves de 1 a 7) em arvore AVL em destaque nós P e U dos exemplos que precisam de rotação ( e Y, filho que precisa “Trocar de Pai) em vermelho), nos retângulos arvore antes e após a rotação:

 

Exemplo 2:

Inserção das Chaves 80,40,60,50 e 45 (nessa seqüência ):

QUESTIONÁRIO 03 - ÁRVORE BINÁRIA DE BUSCA

1)   Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Portanto explique como serão inseridos os elementos 10, 20, 15, 18,  30, 40 e 13 numa árvore binária de busca.
Resposta: Primeiramente, ordenar os números em ordem crescente:

10, 13, 15, 18, 20, 30, 40.

      Após a ordenação dos números, identifica-se que a raiz será o número 18, pois se encontra no meio do intervalo de números acima;

      Em seguida, colocar todos os números menores que 18 na subárvores da esquerda e maiores que 18 na subárvores da direita.

      Veja como ficou inseridos os elementos na figura da árvore abaixo.

2)   Sabendo que podemos inserir elementos numa árvore binária e que isso é uma operação básica das árvores, indique e explique quais são as operações básicas de uma árvore binária?
Resposta: Inserção quando adciona-se um elemento na árvore na posição correta para que a propriedade fundamental seja mantida. Para inserirmos um valor x em uma árvore usamos sua estrutura recursiva, e a ordenação especifica na propriedade fundamental.
Remoçao quando se permite retirar um determinado elemento da árvore. Primeiro quando se deseja retirar um elemento da folha de árvore, basta retirar o elemento da árvore e atualizar o pai, pois seu filho não existe mais. Segundo passo quando o nó a ser retirado possui um único filho, para retirar esse elemento é necessário antes acertar o ponteiro do pai, pulando o nó, o único neto passa a ser o filho direto.
Construção as operações de inserção devem ser efetuadas conforme a ordem das chaves o 1º passo é inserir as chaves que ficaram mais proximas da raiz, se caso tivermos um conjunto de chaves deve se inserir o valor médio das chaves, inserindo as chaves inferior e as superiores a esse valor.

3)   Sabendo que as árvores binárias podem ser cheias e completas e que uma árvore otimal é uma árvore completa que a operação de inserção segue a regra de inserção por ordem das chaves. Como as inserções sempre ocorrem à nível de folha,  deve-se primeiro inserir as chaves que ficarão mais perto da raíz. Se temos um conjunto de chaves {c1,..,ci} tal que c1<...<ci, deve se inserir o valor médio das chaves, inserir o conjunto das chaves inferior a esse valor, e inserir o conjunto das chaves superior a esse valor.  Portanto no conjunto de chaves K={1,2,3,4,5,6,7}.  Uma ordem de inserção otimal seria o 4, 2, 6, 1, 7, 5 e 3. Explique como ficaria uma inserção otimal do conjunto K={2,4,6,8,10,12,14}.
Resposta:  Se temos um conjunto de chaves {c1,. . . c} tal que c1 < ... < c, deve se inserir o valor médio das chaves, inserir o conjunto das chaves inferior a esse valor, e inserir o conjunto das chaves superior a esse valor.
Então, pela inserção K={2,4,6,8,10,12,14}, o número 8 é a raiz pois se encontra no meio desse intervalo de números. Veja na figura abaixo a inserção otimal do intervalo de números acima:

4)   Uma das operações mais úteis das ABB é a localização, outra característica desse tipo de árvore são os chamados percursos que mostram os elementos que a árvore contém e que são classificados em pré-fixado/pré-ordem, pós-fixado/pós-ordem e in-ordem/em ordem. Explique como funciona o procedimento para realizar cada percurso considerando as subárvores. Existe alguma diferença com relação às árvores binárias comuns?

Percurso de uma árvore binária em pré-fixado / pré-ordem 

Percorrer uma árvore binária em pré-ordem:

    1.Visitar a raiz.

    2. Percorrer a sua subárvore esquerda em pré-ordem.

    3. Percorrer a sua subárvore direita em pré-ordem.



O percurso em pré-ordem segue os nós até chegar os mais “profundos”, em “ramos” de subárvores da esquerda para a direita. É conhecida usualmente pelo nome de percurso em profundidade (depth-first).

Percurso de uma árvore binária em pós-fixado / pós-ordem

Percorrer uma árvore binária em pós-ordem:

1. Percorrer a sua subárvore esquerda em pós-ordem.

2. Percorrer a sua subárvore direita em pós-ordem.

3. Visitar a raiz.

Outro Exemplo:

A representação de uma expressão aritmética com o operador no final dos operando é conhecida pelo nome de notação reversa ou polonesa.

Percurso de uma árvore binária em in-ordem / em ordem

Percorrer uma árvore binária em in-ordem:

1. Percorrer a sua subárvore esquerda em in-ordem.

2. Visitar a raiz.

3. Percorrer a sua subárvore direita em in-ordem.

A in-ordem visita a raiz entre as ações de percorrer as duas subárvores. É conhecida também pelo nome de ordem simétrica.



QUESTIONÁRIO 02 – ÁRVORES BINÁRIAS

1) Uma árvore é um conjunto de 1 ou mais nós, onde existe um nó especial chamado raiz e os demais nós formam conjuntos disjuntos onde cada conjunto é uma árvore (subárvore). O que caracterizaria então uma árvore Binária?
Resposta: Uma árvore binaria deve conter no máximo 2 filhos(nós), e nela possuem grau zero ou um.

2) Uma árvore binária tem por tanto uma subárvore da esquerda e outra subárvore da direita (mesmo que exista uma só ou nenhuma), existe alguma maneira de calcular o número máximo de elementos de uma árvore conhecendo sua altura?
Resposta: Sim, isso acontece através da Formula: 2n – 1 = Numero máximo de elementos de uma árvore binária.

3) Nas árvores binárias podemos percorrer os elementos através de alguns percursos, quais são eles?
Resposta: IN-Ordem, PRÉ-Ordem, PÓS-Ordem.

4) A definição do percurso EM-Ordem/IN-Ordem é:
Resposta: A raiz fica no meio das sub-arvores esquerda e direita.

5) A definição do percurso PRÉ-Ordem/PRÉ-Fixado é:
Resposta: A raiz vem antes das sub-arvores esquerda e direita.

6) A definição do percurso PÓS-Ordem/PÓS-Fixado é:
Resposta: A raiz vem depois das sub-arvores esquerda e direita.

7) Existe outra maneira de percorrer uma árvore (não obrigatoriamente binária), conhecida como percurso por extensão ou largura. Explique esse processo.
Resposta: Percurso por Extensão ou Largura: Os nós são visitados na ordem dos níveis da árvore, isto é: primeiramente são visitados os nós do nível 0, depois do nível 1, depois do nível 2 eassim por diante; os nós são visitados da esquerda para a direita em cada um dos níveis.



Ordem de Processamento: A B E C F G D H

Exercício do Slide

Faça o percurso em pré-ordem, in-ordem e pós-ordem da seguinte árvore.

PRÉ-ORDEM (RED) – A B D G C E H I F 

IN/EM-ORDEM (ERD) – D G B A H E I C F

PÓS-ORDEM (EDR) – G D B H I E F C A



QUESTIONÁRIO 01 – ÁRVORES, CONCEITOS GERAIS

1)   A estrutura de uma árvore é especializada em representar hierarquia. Defina e caracterize de forma completa o conceito da Estrutura Árvore.

Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:

1. uma estrutura (uma árvore);
2. um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
3. Não Existe árvores vazias, no minímo haverá um nó raiz(que não possui pai)

Cada árvore tem apenas uma raiz. Além disso, 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.

2)         O conceito da estrutura árvore é muito importante para as disciplinas de Sistema Operacional e Banco de Dados. Dê exemplos da aplicação prática da estrutura de dados árvore, explicando cada exemplo (pelo menos 3).
Hierarquia de classes: São as classes e subclasses, ou seja, uma classe subordinando a outra;
Ordenação de Valores: São as  Árvore ordenada na esquerda, na  raiz, e na direita;
Organogramas de empresas: É a  hierarquia entre os empregados de uma empresa.

3)         Para compreender o conceito de árvore é necessário entender alguns conceitos básicos. Explique o conceito de raíz, nó filho, nó pai, nó terminal, nó ascendente, nó descendente, grau, altura, nível, profundidade, caminho e floresta.
Os conceitos básicos da estrutura árvore são:

• Raiz – é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);
• Nós – são todos os itens guardados na árvore;
• Nós Filhos – são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);
• Nós Pais – são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);
• Folhas ou nó terminal – são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13);
• Nó Ascendente- Nó acima de um dado nó, em direção a raiz (No caso da figura acima, o nó 8 é ancestral do nó 3, 10 ,1, 6 …, 13);
• Nó Descendente- Nó abaixo de um dado nó (No caso da figura acima, o nó 3 e 10 é ascendente de 8);
• Grau de um nó é o número de nós  filhos do mesmo. Obviamente um nó folha tem grau zero;
• Nível de um nó é o número de nós existentes no caminho entre a raiz e o próprio nó;
• Altura de uma árvore  (também denominada profundidade) é a distância entre x e o seu descendente mais afastado. Mais precisamente, a altura de x é o número de passos do mais longo caminho que leva de x até uma folha somando um;
• caminho da árvore é composto por uma seqüência de nós consecutivos (n₁, n₂, …, n_k-1, n_k) tal que existe sempre a relação n_i é pai de n_i+1;
• Floresta: é um conjunto de zero ou mais árvores disjuntas, ou seja, se for eliminado o nó raiz da árvore, as sub-árvores que restarem chama-se de florestas.

4)         Existem diversas maneiras de representar a estrutura de uma árvore. Demonstre e conceitue a representação Hierárquica, Diagrama de Inclusão, Expressão parametrizada e Expressão não parametrizada.


Representação hierárquica





Representação por conjuntos (diagrama de inclusão)

      Representação por expressão parentetizada (parênteses aninhados)
      Cada conjunto de parênteses correspondentes contém um nodo e seus  filhos.
      Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

      Representação por expressão não parentetizada
      Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida por esses filhos, representados do mesmo modo.