QUESTIONÁRIO 03 – ÁRVORES 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:
Primeiro ordenamos os valores em ordem crescente:
10 – 13 – 15 – 18 – 20 – 30 - 40
10 – 13 – 15 – 18 – 20 – 30 - 40
Procuramos o valor que se encontra no meio do intervalo e definimos como raiz; neste caso seria o numero 18:
10 – 13 – 15 – 18 – 20 – 30 – 40
Em seguida iremos inserir os demais valores obedecendo a regra de uma árvore binária de busca:
18 – 13 – 30 – 10 – 20 – 15 – 40
Representação Gráfica:
Obs.: Esta árvore é uma árvore de busca otimal.
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?
Consulta/Busca: Percorre a árvore de forma simples obedecendo aos critérios 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 raiz.
Resposta:
Inserção: Insere os valores obedecendo aos critérios de busca, onde os elementos serão sempre inseridos no final da árvore, ou seja, o novo elemento será uma nova folha.
Remoção: Permite retirar um determinado elemento da árvore. Existem três situações possíveis.
A primeira é:
Quando se deseja retirar um elemento que não tem filhos (Folha), basta retirar o elemento da árvore e atualizar o pai, apontando para null.
A segunda é:
Se o nó a ser retirado possui um único filho é necessário antes acertar o ponteiro do pai, deve ser refeito o apontamento do nó pai para o nó neto, ou seja, o pai do neto morreu.
A terceira é:
Quando o nó a ser retirado tem dois filhos devemos proceder da seguinte forma:
a) Encontramos o elemento mais à direita da sub-árvore à esquerda;
b) Trocamos a informação do nó a ser retirado com a informação do nó encontrado;
c) retiramos o nó encontrado (que agora contém a informação do nó que se deseja retirar).
Exemplo da operação para retirar o elemento com informação igual a 6.
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:
Primeiro ordenamos os valores em ordem crescente:
02 – 04 – 06 – 08 – 10 – 12 – 14
02 – 04 – 06 – 08 – 10 – 12 – 14
Procuramos o valor que se encontra no meio do intervalo e definimos como raiz; neste caso seria o numero 08:
02 – 04 – 06 – 08 – 10 – 12 – 14
Em seguida iremos inserir os demais valores obedecendo à regra de uma árvore binária de busca:
08 – 04 – 12 – 02 – 10 – 06 – 14
Representação Gráfica:
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?
Resposta:
In-ordem:
1. Percorre a subárvore esquerda em ordem simétrica;
2. Visita a raiz;
3. Percorre a subárvore direita em ordem simétrica.
Pré-ordem:
1. Visita a raiz;
2. Percorre a subárvore esquerda em pré-ordem;
3. Percorre a subárvore direita em pré-ordem.
Pós-ordem:
1. Percorre a subárvore esquerda em pós-ordem;
2. Percorre a subárvore direita em pós-ordem;
3. Visita a raiz.
A diferença para percorrer uma arvore binária de uma arvore binária de busca é que, a arvore binária pode ser percorrida também pelo percurso de extensão e pelo percurso em nível além dos percurso de pré-ordem, in-ordem e pós-ordem. Já a arvore binária de busca só pode ser percorrido pelo pré-ordem,in-ordem e pós-ordem.
Resposta:
In-ordem:
1. Percorre a subárvore esquerda em ordem simétrica;
2. Visita a raiz;
3. Percorre a subárvore direita em ordem simétrica.
Pré-ordem:
1. Visita a raiz;
2. Percorre a subárvore esquerda em pré-ordem;
3. Percorre a subárvore direita em pré-ordem.
Pós-ordem:
1. Percorre a subárvore esquerda em pós-ordem;
2. Percorre a subárvore direita em pós-ordem;
3. Visita a raiz.
A diferença para percorrer uma arvore binária de uma arvore binária de busca é que, a arvore binária pode ser percorrida também pelo percurso de extensão e pelo percurso em nível além dos percurso de pré-ordem, in-ordem e pós-ordem. Já a arvore binária de busca só pode ser percorrido pelo pré-ordem,in-ordem e pós-ordem.
