T10 Profundidade média dos nós de 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 em ABs tem papel importante.
Profundidade de nós em ABs. A profundidade \({\rm prof}(x)\) 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.
Seja $T$ uma AB com $N$ nós. Neste exercício, você provará que a profundidade média dos nós em $T$ é pelo menos $\sim\lg N$. Mais precisamente, você provará que
\( \sum_x{\rm prof}(x)\geq(N+1)\lg(N+1)-2N, \)
onde a soma estende-se sobre todos os nós $x$ de $T$. Segue que a profundidade média $N^{-1}\sum_x{\rm prof}(x)$ dos nós em $T$ é tal que
\( N^{-1}\sum_x{\rm prof}(x)\geq\lg(N+1)-2\sim\lg N. \)
Preliminares. 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. Veja esta página para familiarizar-se com a desigualdade acima.
Soma das profundidades dos nós em uma AB. Seja $T$ uma AB com $N$ nós. Seja
\( P=\sum_x{\rm prof}(x), \)
onde a soma estende-se sobre todos os nós $x$ de $T$. Prove por indução em $N$ que $P\geq(N+1)\lg(N+1)-2N$.
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}\sum_x{\rm prof}(x)\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.