T06 IPL, EPL e buscas em ABBs
Dada uma árvore binária \(T\), denotamos por $\mathrm{ipl}(T)$ seu internal path length, isto é, a soma das profundidades de seus nós internos. Ademais, denotamos por $\mathrm{epl}(T)$ seu external path length: a soma das profundidades de seus nós externos.
(i) Prove que $\mathrm{epl}(T)=\mathrm{ipl}(T)+2N$, onde $N$ é o número de nós internos em 𝑇. [Sugestão. Faça indução em $N$.]
Suponha agora que $T$ seja uma ABB. Assim, $T$ armazena $N$ chaves em seus nós internos.
(ii) Suponha que fazemos uma busca com sucesso em $T$: isto é, buscamos uma das $N$ chaves presentes em $T$. Qual é o número de comparações entre chaves que fazemos em tal busca em média? Em outras palavras, se as chaves são $k_0,\dots,k_{N-1}$, e a busca da chave $k_i$ acarreta a execução de $c_i$ comparações, quanto é a média desses números $c_i$? Dê sua resposta em termos de $\mathrm{ipl}(T)$.
(iii) Suponha agora que fazemos uma busca sem sucesso em $T$: isto é, buscamos uma chave $k$ que não está presente em $T$. Qual é o número de comparações entre chaves que fazemos em tal busca em média?
Mais precisamente, suponha que executamos a busca de um elemento $k$ em $T$ e $k$ é diferente das chaves $k_0,\dots,k_{N-1}$ presentes em $T$. Podem ocorrer: (a) $k<k_0$, (b) $k_{N-1}<k$ e (c) $k_{i-1}<k<k_i$ para algum $0<i<N$. Seja $c_0$ o número de comparações feitas se (a) ocorre. Seja $c_N$ o número de comparações feitas se (b) ocorre. Finalmente, seja $c_i$ ($0<i<N$) o número de comparações feitas se (c) ocorre. Estamos interessados na média dos $N+1$ números $c_0,c_1,\dots,c_N$, que pode ser interpretado como sendo o número médio de comparações que a busca faz quando a busca é sem sucesso. Dê sua resposta em termos de $\mathrm{epl}(T)$.
(iv) Fixe uma ABB $T$ com $N$ nós internos. Seja $C$ o número médio de comparações em uma busca com sucesso em $T$. Seja $S$ o número médio de comparações em uma busca sem sucesso em $T$. Prove que $S=(C+1)N/(N+1)$ e deduza que $S\sim C+1$ quando $N\to\infty$.