T07 Profundidade média dos nós em uma AB
Árvores binárias (ABs) são estruturas fundamentais para implementar tabelas de símbolos. Em tais aplicações, a profundidade dos nós tem papel importante.
Profundidade de nós em ABs. A profundidade \(\mathrm{prof}(x)\) de um nó $x$ em uma AB $T$ é definida como sendo 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.
Seja $T$ uma AB. Lembre que o internal path length $\mathrm{ipl}(T)$ de $T$ é
$\mathrm{ipl}(T)=\sum_x\mathrm{prof}(x)$,
onde a soma estende-se sobre todos os nós internos $x$ de $T$. (Lembre que em certos contextos chamamos os nós de uma AB de nós internos; veja este post.) Neste exercício, você provará que a profundidade média $N^{-1}\sum_x\mathrm{prof}(T) = N^{-1}\mathrm{ipl}(T)$ dos nós em uma AB $T$ com $N$ nós é pelo menos $\sim\lg N$.
Seja $T$ uma AB com $N$ nós.
(1) Prove por indução em $N$ que
$\mathrm{ipl}(T)\geq(N+1)\lg(N+1)−2N$.
(2) Deduza que a profundidade média dos nós de $T$ é pelo menos $\lg(N+1)−2\sim\lg N$.
Sugestão. Será útil você saber que a função $f(x)=x\lg x$, definida nos reais positivos, é uma função convexa, isto é,
$f(tx_1+(1−t)x_2)\leq tf(x_1)+(1−t)f(x_2)$
vale para todo $0\leq t\leq1$ e $x_1$ e $x_2$ reais positivos. A convexidade de $f$ pode ser verificada usando cálculo (você lembra como?). Veja esta página para familiarizar-se com a desigualdade acima. Para usar a convexidade de $f$, tome $x_1=2(N_1+1)$, $x_2=2(N_2+1)$ e $t=1/2$, onde $N_1$ é o número de nós na subárvore esquerda de $T$ e $N_2$ é o número de nós na subárvore direita de $T$.
Observações. Suponha que estamos usando uma AB $T$ como uma árvore binária de busca.
(i) Segue do que você provou acima que, por "melhor" que seja $T$, uma busca com sucesso em $T$ faz em média pelo menos $1+N^{-1}\mathrm{ipl}(T)\geq\lg(N+1)−1\sim\lg N$ comparações.
(ii) Segue também que, por "melhor" que seja $T$, uma busca sem sucesso em $T$ faz em média pelo menos $\lg(N+1)$ comparações.