CCM0128 - Computação II (2022i)

Introdução. Neste exercício, vamos estudar árvores binárias de busca (ABBs) de forma experimental. Mais especificamente, vamos estudar dois parâmetros dessas árvores: altura e internal path length (IPL). A altura está intimamente relacionada com a complexidade de pior caso de buscas em árvores de busca, e o IPL está intimamente relacionado com a complexidade de caso médio de buscas. Discutimos essas coisas nas aulas de 1 e 2/6/2022.

Vamos estudar a altura e o IPL de árvores obtidas pela inserção e remoção de chaves geradas aleatoriamente. Vamos usar um gerador simples de sequências aleatórias de tais operações, e vamos observar esses parâmetros ao longo da execução dessas sequências.

O gerador de operações. Neste exercício, estamos interessados apenas nas chaves dos pares chave-valor que armazenamos em nossas tabelas de símbolos. Assim, no que segue, vamos ignorar os valores associados às chaves (você pode supor que todos os valores são, digamos, o inteiro $0$). Além disso, vamos supor que nossas chaves são inteiros positivos.

Abaixo segue o programa RandomOps.java, que gera sequências aleatórias de operações de inserção e remoção de chaves. RandomOps.java pode ser executado das seguintes formas:

$ java-algs4 RandomOps 888 5
$ java-algs4 RandomOps 888 5 3
$ java-algs4 RandomOps 888 5 3 -3

O primeiro argumento (888) é a semente para o gerador de números aleatórios. O segundo argumento especifica quantas operações de inserção devem ser geradas no começo da sequência. Por exemplo, na execução

$ java-algs4 RandomOps 888 5
  1503564550
   812873750
  1210770050
   392734352
  1760357679

obtemos a sequência "insira 1503564550", "insira 812873750", etc. O terceiro argumento, quando presente, especifica quantas operações adicionais devem ser executadas. Por exemplo, na execução

$ java-algs4 RandomOps 888 5 3
  1503564550
   812873750
  1210770050
   392734352
  1760357679
  1110385979
  -392734352
  -812873750

obtemos a sequência "insira 1503564550", "insira 812873750", etc, seguida das 3 operações "insira 1110385979", "remova 392734352" e "remova 812873750". Assim, depois dessas 8 operações, nossa árvore conteria 4 elementos. As operações de remoção geradas por RandomOps.java sempre removem alguma chave presente na árvore; ademais, as operações de inserção geradas por RandomOps.java sempre envolvem elementos que não estão presentes na árvore.

O terceiro argumento de RandomOps.java pode ser negativo. Neste caso, se esse argumento é $-N$, RandomOps.java gera $N$ pares de remoção e inserção de um mesmo elemento presente na árvore:

$ java-algs4 RandomOps 888 5 -3
  1503564550
   812873750
  1210770050
   392734352
  1760357679
 -1503564550
  1503564550
 -1760357679
  1760357679
 -1503564550
  1503564550

Culberson e Munro descobriram que tais sequências com pares de remoção e inserção de um mesmo elemento aleatório da árvore, quando o número de tais pares é grande, degradam as ABBs quando usamos o método de remoção de Hibbard (isto é, as ABBs ficam com altura e IPL sensivelmente maiores).

Altura e IPL de ABBs.  Lembre que uma árvore binária com $N > 0$ nós tem altura pelo menos \(\lfloor\lg N\rfloor\). Assim, quando consideramos a altura $h$ de uma ABB com $N$ nós, é interessante compararmos $h$ com esse menor valor possível da altura. Isso é feito a seguir.

Vimos que, em uma ABB aleatória com $N$ nós, o valor esperado de IPL$/N$ é $2\sum_{1\leq k\leq N}H_k-2N=2(H_{N+1}-1)(1+{1\over N})-2$ onde $H_k=1+1/2+\dots+1/k$ é o $k$-ésimo número harmônico (veja uma observação sobre isso no fim deste enunciado). Assim, quando consideramos o IPL de uma ABB com $N$ nós, é interessante compararmos IPL$/N$ com o valor esperado acima. Isso também é feito a seguir.

BST.java de S&W contém um método height(), que devolve a altura da ABB corrente. O programa BSTPlus.java contém também o método ipl(), que devolve o IPL da ABB corrente. Os programas HeightPlusBST.java, HeightPlotPlusBST.java, IPLPlusBST.java e IPLPlotPlusBST.java dão informação de como a altura e o IPL evoluem quando alimentamos uma sequência de operações gerada por RandomOps.java.

Exemplos de execução.  Seguem alguns exemplos de execução.

$ java-algs4 RandomOps 323 10000 | time java-algs4 HeightPlusBST
N: 10000
Height: 28
Floor of lg N: 13.0
Average ratio: 2.2215159099236366
0.79 real 0.96 user 0.09 sys
$ java-algs4 RandomOps 323 10000 10000 | time java-algs4 HeightPlusBST
N: 9898
Height: 28
Floor of lg N: 13.0
Average ratio: 2.1626233395767462
1.90 real 2.05 user 0.10 sys
$ java-algs4 RandomOps 323 10000 10000 | java-algs4 HeightPlotPlusBST
N: 9898
Height: 28
Floor of lg N: 13.0
Average ratio: 2.1626233395767462
[imagem: 323-10000-10000-Height.png]
$ java-algs4 RandomOps 323 10000 | time java-algs4 IPLPlusBST
N: 10000
IPL: 153645
IPL/N: 15.3645
Expected: 15.57716959329598
Average ratio: 0.9874976134633189
0.74 real 0.92 user 0.08 sys
$ java-algs4 RandomOps 323 50000 | time java-algs4 IPLPlusBST
N: 50000
IPL: 928540
IPL/N: 18.5708
Expected: 18.794463778715006
Average ratio: 0.9873773096404165
13.04 real 13.18 user 0.11 sys
$ java-algs4 RandomOps 323 10000 | java-algs4 IPLPlotPlusBST
N: 10000
IPL: 153645
IPL/N: 15.3645
Expected: 15.57716959329598
Average ratio: 0.9874976134633189
[imagem: 323-10000-IPL.png]

Implementações mais rápidas de height() e ipl().  Ao executar HeightPlusBST.java e IPLPlusBST.java, você deve ter percebido que eles não se comportam bem com o aumento de escala. Isto é, eles são lentos quando executamos sequências longas de operações e as árvores envolvidas são moderadamente grandes. Note que isso tem a ver com height() e ipl(), isto é, não tem a ver com as operações de inserção e remoção: se você executar as operações geradas por RandomOps.java em uma ABB sem calcular height() e ipl() a cada momento, você verá tempos de execução muito menores. Por que isso ocorre?

Tarefa. Altere as implementações de height() e ipl() em BSTPlus.java de forma que elas sejam operações de tempo constante. Você pode adicionar dois inteiros auxiliares em cada nó da árvore. Seu programa deve chamar-se BSTDeluxe.java. Você pode experimentar seu programa com os clientes HeightDeluxeBST.java, HeightPlotDeluxeBST.java, IPLDeluxeBST.java, IPLPlotDeluxeBST.java, dados abaixo.

Exemplos de execução

$ java-algs4 RandomOps 888 1000000 | time java-algs4 HeightDeluxeBST
N: 1000000
Height: 48
Floor of lg N: 19.0
Average ratio: 2.516576145111492
3.69 real 5.10 user 0.66 sys
$ java-algs4 RandomOps 888 100000 | java-algs4 HeightPlotDeluxeBST
N: 100000
Height: 40
Floor of lg N: 16.0
Average ratio: 2.43541040424682
[imagem: 888-100000-Height.png]
$ java-algs4 RandomOps 888 1000 -2000000 | java-algs4 HeightPlotDeluxeBST
N: 1000
Height: 39
Floor of lg N: 9.0
Average ratio: 3.8081715434575134
[imagem: 888-1000--2000000-Height.png]
$ java-algs4 RandomOps 888 1000000 | time java-algs4 IPLDeluxeBST
N: 1000000
IPL: 23528158
IPL/N: 23.528158
Expected: 24.78548223118499
Average ratio: 0.9443912734610068
3.62 real 5.47 user 0.59 sys
$ java-algs4 RandomOps 888 1000000 | java-algs4 IPLPlotDeluxeBST
N: 1000000
IPL: 23528158
IPL/N: 23.528158
Expected: 24.78548223118499
Average ratio: 0.9443912734610068
[imagem: 888-1000000-IPL.png]
$ java-algs4 RandomOps 888 1000 -2000000 | java-algs4 IPLPlotDeluxeBST
N: 1000
IPL: 17858
IPL/N: 17.858
Expected: 10.98591266282178
Average ratio: 1.3962406633149258
[imagem: 888-1000--2000000-IPL.png]

Observação.  As imagens 888-1000--2000000-Height.png e 888-1000--2000000-IPL.png mostram bem que a ABB degenera com as sequências de operações de Culberson e Munro.

Tempos de execução.  Para verificar a eficiência de suas implementações de height() e ipl(), os programas HeightDeluxeBST.java e IPLDeluxeBST.java serão executados como nos exemplos acima, com sua implementação de BSTDeluxe.java. Seus tempos de execução devem ser comparáveis aos tempos acima e aos tempos em exemplos.txt.

Estudos experimentais.  Apenas como curiosidade, segue uma referência que contém estudos experimentais interessantes sobre o desempenho de diversos tipos de árvores em contextos reais de sistemas de software:

- Ben Pfaff, Performance Analysis of BSTs in System Software, SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems, 2004, pp 410--411 DOI: https://doi.org/10.1145/1005686.1005742 URL: https://web.stanford.edu/~blp/papers/libavl.pdf

Entrega.  Note que você deve entregar somente um programa: BSTDeluxe.java. Ele pode ser apenas uma pequena adaptação de BST.java de S&W.

Observações.  Vimos em aula que o valor esperado $\mu_N$ do IPL de uma ABB aleatória com $N$ nós é $2\sum_{1\leq k\leq N}H_k-2N$. Vale que $\sum_{1\leq k\leq N}H_k=(N+1)H_N-N$ (isso pode ser provado facilmente por indução em $N$). Segue que $\mu_N=2(H_{N+1}-1)(1+1/N)-2$.

Vimos que um argumento simples mostra que $\log(N+1)\leq H_N\leq\log N+1$. De fato, vale que $H_N=\log N+\gamma+o(1)$, onde $\gamma=0.5772\dots$ é uma constante, conhecida como a constante de Euler ou contante de Euler e Mascheroni, e $o(1)$ denota uma função que tende a $0$ quando $N\to\infty$.