T05 Altura média dos nós em uma ABC
Um fato interessante que vimos sobre a montagem do heap na primeira fase do heapsort é que aquela fase faz no máximo $2N$ comparações e no máximo $N$ trocas, onde $N$ é número de elementos no vetor sendo ordenado. Assim, essa primeira fase tem complexidade $O(N)$. Veja a página 44 de
https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/24PriorityQueues.pdf
Ao concluir esse exercício, você saberá justificar a proposição na página indicada acima para todo valor de $N$ e não apenas para $N$ da forma $2^{h+1}-1$.
Lembre que heaps têm por base árvores binárias completas (ABCs): árvores binárias (ABs) cujos níveis são completos, a menos possivelmente do último nível, que está preenchido "da esquerda para a direita". Um fato crucial é que a altura média dos nós em uma ABC é no máximo $1$.
Altura de nós em ABs. Em uma AB, cada nó \(x\) é a raiz de uma subárvore: a subárvore "enraizada em $x$". Definimos a altura $h(x)$ de $x$ como sendo a altura dessa subárvore enraizada em $x$. Assim, $h(x)=0$ se $x$ é uma folha (isto é, não tem filhos) e se um nó $x$ não é folha mas só tem folhas como filhos, então $h(x)=1$.
Seja $T$ uma ABC. Estamos interessados em determinar ou estimar a soma
\( S=\sum_xh(x), \)
onde a soma estende-se sobre todo nó $x$ de T.
Preliminares. Seja $N\geq1$ um inteiro e suponha que a representação binária de $N$ seja $(b_nb_{n-1}\dots b_0)_2$. Temos então $b_n=1$ e $n=\lfloor\lg N\rfloor$. Escrevemos
\( N=(b_n\dots b_0)_2. \)
Seja $T$ uma ABC com $N$ nós. Sejam $T_1$ e $T_2$ as subárvores esquerda e direita de $T$. Sejam $N_1$ o número de nós em $T_1$ e $N_2$ o número de nós em $T_2$.
(1) Prove que se $b_{n-1}=1$, então $N_1=2^n-1$ e $N_2=(b_{n-1}\dots b_0)_2$.
(2) Prove que se $b_{n-1}=0$, então $N_1=(1b_{n-2}\dots b_0)_2$ e $N_2=2^{n-1}-1$.
Soma das alturas dos nós em uma ABC. Seja $T$ uma ABC com $N$ nós. Seja $u_N$ o número de bits $1$ na representação binária de $N=(b_n\dots b_0)_2$, isto é, $u_N=|\{i:b_i=1\}|$. Seja $S$ a soma das alturas de todos os nós em $T$.
(3) Prove que $S=N-u_N$.
Observações
- Seque de (3) que $S/N<1$, isto é, a altura média dos nós em uma ABC é menor que $1$.
- A proposição na página 44 de https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/24PriorityQueues.pdf segue de (3).
- A profundidade de um nó $x$ em uma AB $T$ é definida como sua distância à raiz de $T$. Assim, a raiz de $T$ tem profundidade $0$, os filhos da raiz têm profundidade $1$, os netos têm profundidade $2$, etc. Em um exercício teórico futuro, você provará que, em qualquer árvore binária $T$ com $N$ nós, a profundidade média dos nós em $T$ é pelo menos $\sim\lg N\to\infty$.