T08 Inserção de chaves em ordem crescente em ARNEs
Assista inicialmente a esse vídeo:
https://algs4.cs.princeton.edu/33balanced/media/red-black-255ascending.mov
acessível em
https://algs4.cs.princeton.edu/33balanced/
Nesse vídeo, vemos como uma ARNE inicialmente vazia evolui quando \(255\) chaves distintas são inseridas em ordem crescente. A ARNE final é uma AB com $255$ nós "perfeitamente balanceada" (todos os níveis da AB estão cheios, com $1, 2, \dots, 2^7$ nós). Vamos denotar por $B_h$ a AB perfeitamente balanceada de altura $h$ (sem nenhum nó vermelho). Assim, a AB final no vídeo é $B_7$.
Neste exercício, você deve provar a seguinte afirmação.
Afirmação T08. Para todo $h\geq0$, quando inserimos $2^{h+1}-1$ chaves distintas em uma ARNE inicialmente vazia em ordem crescente, obtemos, ao final, a árvore $B_h$.
Sugestão. Siga o roteiro abaixo.
1. Vamos chamar o processo de inserir $t$ chaves distintas em ordem crescente em uma ARNE de $I(t)$. Ademais, vamos supor que as chaves que são inseridas em $I(t)$ são todas maiores que as chaves já presentes na ARNE.
2. O processo de inserção em uma ARNE é tal que, quando a altura biternária da ARNE aumenta em uma execução de put(key, val), a raiz termina vermelha quando a execução de put(root, key, val) em put(key, val) termina. Entretanto, a chamada de put(root, key, val) é imediatamente seguida da atribuição root.color = BLACK, tornando a raiz novamente negra.
3. Considere a variante $B_h^r$ de $B_h$, obtida de $B_h$ tornando sua raiz vermelha.
4. Denotamos a AB com raiz $r$, subárvore esquerda $E$ e subárvore direita $D$ por $(r,E,D)$. Quando não estamos prestando atenção na identidade da raiz, escrevemos $(*,E,D)$. Podemos assim escrever $B_h=(*,B_{h-1},B_{h-1})$ para todo $h\geq1$. Podemos também escrever $B_h^r=(*^r,B_{h-1},B_{h-1})$, onde $*^r$ indica que a raiz $*$ é vermelha.
5. Afirmação $(A_h)$. Suponha que inserimos $2^{h+1}$ chaves em $B_h$, em ordem crescentes e todas elas estritamente maiores que as chaves presentes em $B_h$. Então obtemos $B_{h+1}^r$, que é transformada em $B_{h+1}$ imediatamente antes do término do processo (pela atribuição root.color = BLACK; veja (2) acima).
O seguinte diagrama representa a Afirmação $(A_h)$:
\( B_h\to_{I(2^{h+1})} B_{h+1}^r\to B_{h+1}. \)
6. Prove que a Afirmação $(A_0)$ vale.
7. Seja $h\geq1$. Prove que a Afirmação $(A_h)$ vale, supondo que a Afirmação $(A_{h-1})$ vale.
8. Conclua por indução que a Afirmação $(A_h)$ vale para todo $h\geq0$.
9. Conclua que a Afirmação T08 vale.
Programas auxiliares. Você pode achar ilustrativo executar o programa RBBSTDraw.java abaixo (RBBSTDraw.java depende de RedBlackBSTDraw.java, também abaixo).
- 22 avril 2024, 13:52
- 22 avril 2024, 13:52