Questionário 03 - Árvores Binária de Busca

1- Uma Árvore binária e uma arvore onde cada nó tem no máximo 2 filhos . Uma árvore binária de busca é uma árvore e binária de 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 . Portanto explique como serão inseridos os elementos 10,20,15,18,30,40 e 13 numa árvore binária de busca.

R:

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?

R: Busca : A operação para buscar um elemento na árvore explora a propriedade de ordenação da árvore, tendo um desempenho computacional proporcional a sua altura (0(logn) para o caso de árvore balanceada.

Inserção: A operação de inserção adiciona um elemento na árvore na posição correta para que a propriedade fundamental seja mantida.

Remoção : Essa operação é um pouco mais complexa que a de inserção. Existe três situações possíveis . A primeira , e mais simples, é quando se deseja retirar um elemento que é folha da árvore . Neste caso , basta retirar o elemento da árvore e atualizar o pai, pois seu filho não existe mais.

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

R: 8,4,12,2,14,10,6

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çacom relação às árvores binárias comuns?

R: Em pre ordem :

Visita a raiz;

Percorre sua subárvore esquerda, em pré-ordem;

Percorre sua subárvore direita, em pré-ordem;

Percurso em pré-ordem

In-ordem

• Percorrer sua subárvore esquerda, em in-ordem;

• Visitar a raiz;

• Percorrer sua subárvore direita, em in-ordem;

Pós-ordem

• Percorrer sua subárvore esquerda, em pós-ordem;

• Percorrer sua subárvore direita, em pós-ordem;

• Visitar a raiz;