E05 Altura e IPL de ABBs e ARNEs
Introdução. Neste exercício, vamos estudar árvores binárias de busca (ABBs) e árvores rubro-negras esquerdistas (ARNEs). 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 nessas árvores, e o IPL está intimamente relacionado com a complexidade de caso médio dessas buscas. Discutimos essas coisas na aula de 6/5/2021.
Vamos estudar a altura e o IPL de árvores obtidas pela inserção e remoção de chaves geradas aleatoriamente. Vamos usar um gerador 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. Aqui estamos interessados apenas nas chaves dos pares chave-valor que armazenamos em nossas tabelas de símbolos implementadas com ABBs ou ARNEs. 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
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 gerados 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 geradas. 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; analogamente, as operações de inserção geradas por RandomOps.java sempre envolvem elementos que não estão presentes na árvore.
O terceiro argumento pode ser negativo. Nesse caso, se esse argumento é $-N$ ($N>0$), 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 (quadrático no tamanho da árvore), degradam as ABBs quando usamos o método de remoção de Hibbard (ficam com altura e IPL notadamente maiores). (Veja a Seção 3.2 de S&W.)
Árvores binárias de busca
Altura e IPL. Lembre que uma árvore binária com $N > 0$ nós tem altura pelo menos . 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 ${\rm IPL}/N$ é $2(H_{N+1}-1)(1+1/N)-2=2\log N-2(2-\gamma)+O((\log N)/N)$, onde $H_N=1+1/2+\dots+1/N$ é o $N$-ésimo número harmônico e $\gamma=0.5772\dots$ é a constante de Euler (talvez você estude a prova desse resultado em MAC0338). Assim, quando consideramos o IPL de uma ABB com $N$ nós, é interessante compararmos ${\rm IPL}/N$ com o valor esperado acima. Isso também é feito a seguir.
BST.java contém um método height(), que devolve a altura da ABB corrente. O programa BSTPlus.java (abaixo) 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 desses programas.
$ 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, HeightPlotPlusBST.java, IPLPlusBST.java e IPLPlotPlusBST.java, você deve ter percebido que eles não se comportam bem com o aumento da escala. Isto é, eles são lentos quando as árvores são moderadamente grandes e executamos sequências longas de operações. 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?
Problema. 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.
Árvores rubro-negras esquerdistas
Repita 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
$ java-algs4 RandomOps 888 1000000 | time java-algs4 HeightDeluxeRB
N: 1000000
Height: 26
Floor of lg N: 19.0
Average ratio: 1.4043441671677048
3.79 real 5.75 user 0.65 sys
$ java-algs4 RandomOps 888 1000000 | time java-algs4 IPLDeluxeRB
N: 1000000
IPL: 18572662
IPL/N: 18.572662
lg N: 19.931568569324174
Average ratio: 0.9312246363732201
3.77 real 5.72 user 0.65 sys
Exemplos adicionais
$ java-algs4 RandomOps 888 1000 -2000000 | java-algs4 HeightPlotDeluxeRB
N: 1000
Height: 12
Floor of lg N: 9.0
Average ratio: 1.3814887613010889
[imagem: 888-1000--2000000-Height-RB.png]
$ java-algs4 RandomOps 888 1000 -2000000 | java-algs4 IPLPlotDeluxeRB
N: 1000
IPL: 8284
IPL/N: 8.284
lg N: 21.93192919800769
Average ratio: 0.8325319096215489
[imagem: 888-1000--2000000-IPL-RB.png]
$ java-algs4 RandomOps 888 1000 -2000000 | time java-algs4 HeightDeluxeRB
N: 1000
Height: 12
Floor of lg N: 9.0
Average ratio: 1.3814887613010889
6.69 real 6.44 user 1.05 sys
$ java-algs4 RandomOps 888 1000 -2000000 | time java-algs4 IPLDeluxeRB
N: 1000
IPL: 8284
IPL/N: 8.284
lg N: 9.965784284662087
Average ratio: 0.8325319096215489
7.05 real 6.70 user 1.19 sys
Tempos de execução
Os tempos de execução dos seus programas devem ser, grosso modo, comparáveis aos tempos nos exemplos acima.
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 dois programas: BSTDeluxe.java e RedBlackBSTDeluxe.java. Eles podem ser apenas pequenas adaptações de BST.java e RedBlackBST.java de S&W.
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 28 May 2021, 7:13 PM
- 8 May 2021, 10:06 PM
- 28 May 2021, 7:13 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:04 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM
- 8 May 2021, 10:06 PM