(Não precisa entregar mas ... vale a pena fazer !!)
Considere uma árvore binária implementada por elementos com os
campos info, llink, e rlink. Dada um apontador a uma árvore binária,
escreva um algoritmo que mude todos os apontadores nil da árvore
para apontar para a raiz da árvore.
Escreva um algoritmo breadthfirst(T) que percorre uma
árvore binária T em ordem ``breadth-first'' ou ``por alargamento'',
visitando primeiro a raiz (nível 1), em seguida os seus
filhos (nível 2) da esquerda para a direita, e assim
sucessivamente. Caso precise de alguma estrutura de
dado auxiliar, especifique qual, e suponha existentes rotinas
para a sua manipulação.
Escreva um algoritmo que, dada uma árvore binária de busca,
remove o nó contendo o menor valor.
Uma árvore binária de busca pode ser usada para implementar uma
fila de prioridade. Escreva um algoritmo eficiente para realizar
a operação de remoção de um elemento da fila de
prioridade assim implementada. Qual a complexidade desse
algoritmo no pior caso?
Escreva uma função recursiva que retorna a altura de uma
árvore binária.
Escreva um algoritmo que verifica se uma dada árvore binária
é do tipo AVL. Suponha já existente uma função altura(P) que retorna
a altura de uma árvore binária apontada por P.
Desenhe uma árvore AVL de 20 nós de maior altura.
Desenhe uma árvore AVL de altura 7 com o menor número de
nós.
Desenhe uma árvore de busca do tipo AVL com um total de 36 nós
possuindo a maior altura possível. Mostre seus trabalhos.
Obtenha a árvore de busca binária ótima, com as seguintes chaves
e frequências de acesso, por meio da técnica de programação
dinâmica. Ilustre todos os passos (figuras) como foi feito no
exemplo dado em aula.
Use a técnica de programação dinâmica para mostrar a
melhor maneira de multiplicar 5 matrizes ,
respectivamente, . Mostre também o número de operações
aritméticas usadas.
Considere uma B-árvore de ordem 1 (isté, cada página
ou nó da árvore contém 1 ou 2 chaves). Considere a inserção
das chaves de valores 1, 2, , etc. Após a inserção
de quais chaves ocorrem quebra de páginas? Indique também
as chaves (maiores que a chave 1) que provocam o aumento da
altura da B-árvore.