Sujeito a mudanças...
Maio
Leitura recomendada: CLRS, cap 13. Veja também os exercícios desse capítulo. Para descobrir mais sobre árvores AVL, olhe o livro do Manber (QA758 M267i), páginas 75 a 77, ou o livro do Wirth (QA758 W799), página 218.
Leitura recomendada: sec 4.5 do livro do Aho, Hopcroft e Ullman [QA758 A286d] e/ou sec 4.2.2 do livro do Jayme Szwarcfiter e Lilian Markenzon, Estruturas de Dados e seus Algoritmos.
Exercício: Reescreva a recorrência para a
variante do problema que, além das probabilidades p1,...,pn de
buscas bem-sucedidas, tem também as probabilidades q0,...,qn das
buscas mal-sucedidas. A probabilidade qi é a estimativa da
probabilidade de uma chave x entre i e i+1 ser procurada na
árvore.
Exemplo: n=3, q0=1/11, p1=2/11, q1=0,
p2=1/11, q2=2/11, p3=3/11, q3=2/11. Calcule o número esperado de
comparações para cada uma das ABBs para o conjunto S={1,2,3}
considerando estas probabilidades. Deduza qual é a melhor ABB
dentre estas.
Reescreva o algoritmo visto em aula para a nova recorrência.
Leitura recomendada: CLRS, cap 18, e seção
6.2.4 do volume 3 do Knuth (pg 481-489).
Veja aqui uma implementação real
de B-árvores. Em particular, olhe o arquivo btree.c.
Essa implementação faz parte do SCLite,
uma biblioteca em C que implementa um banco de dados SQL.
Leitura recomendada: CLRS, sec 6.1 a 6.3.
Exercício 1: Escreva a função sobeheap, que
recebe como parâmetros H, n e i, onde H[1..n] é um heap a menos da
posição i, cujo valor da chave foi alterado para um valor maior
que o anterior.
Exercício 2: Escreva a função desceheap, que
recebe como parâmetros H, n e i, onde H[1..n] é um heap a menos da
posição i, cujo valor da chave foi alterado para um valor menor
que o anterior.
Exercício 3: Escreva a função alterachave, que
recebe como parâmetros H, n, i e x, onde H[1..n] é um heap, e
altera o valor da chave da posição i para x, ajustando o heap se
necessário.
Exercício 4: Escreva a função remove, que
recebe como parâmetros H, n e i, onde H[1..n] é um heap, e
remove a chave da posição i do heap, ajustando-o conforme o necessário.