E10 Altura e IPL de ARNEs
Este exercício é uma continuação do E09 Altura e IPL de ABBs.
Neste exercício, você deve repetir o que você fez com BST.java com RedBlackBST.java: altere as implementações de height() e ipl() em RedBlackBSTPlus.java (abaixo) para que eles sejam operações de tempo constante. Você pode adicionar dois inteiros auxiliares em cada nó da árvore. Seu programa deve chamar-se RedBlackBSTDeluxe.java. Você pode experimentar seu programa com os clientes HeightDeluxeRB.java, HeightPlotDeluxeRB.java, IPLDeluxeRB.java, IPLPlotDeluxeRB.java, dados abaixo.
Exemplos de execução. Exemplos de execução são dados no arquivo experiments.txt.
É importante perceber que os exemplos de execução ilustram dois fatos:
- A altura das ARNEs nos experimentos não são muito maiores que o mínimo possível, isto é, \(\log_2N\). (Sabemos que a altura de qualquer ARNE é no máximo $2\log_2N$.)
- A profundidade média dos nós das ARNEs nos experimentos é algo levemente menor que $\log_2N$, o que é muito próximo do melhor possível.
Desempenho. É esperado que os tempos de execução com seu programa RedBlackBSTDeluxe.java sejam comparáveis com os tempos nos exemplos dados.
Entrega. Basta entregar seu programa RedBlackBSTDeluxe.java.
- 14 junho 2022, 22:34 PM
- 14 junho 2022, 22:34 PM