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:
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.
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:
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.
Conteudo Muinto Bom...
ResponderExcluir