Prova de que uma árvore de pesquisa binária construída aleatoriamente tem altura logarítmica

Como você prova que a altura esperada de uma árvore de pesquisa binária criada aleatoriamente com nós é O (\ log n) ? Há uma prova no CLRS Introduction to Algorithms (capítulo 12.4), mas eu não entendo.$n$$O(\log n)$

Vamos primeiro pensar sobre isso intuitivamente. No melhor cenário, a árvore está perfeitamente equilibrada; no pior cenário, a árvore está totalmente desequilibrada:

Começando no nó raiz , essa árvore esquerda tem o dobro de nós em cada profundidade subsequente, de forma que a árvore tenha nós e uma altura (que é neste caso 3). Com um pouco de matemática, , ou seja, tem altura. Para a árvore totalmente desequilibrada, a altura da árvore é simplesmente . Então, nós temos nossos limites.n = Σ h i = 0 2 i = 2 h + 1 - 1 h n ≤ 2 H + 1 - 1 → h ≤ ⌈ log 2 ( n + 1 ) - 1 ⌉ ≤ ⌊ l o g 2 N ⌋ S ( log n ) n - 1 → O ( n $p$$n=\sum_{i=0}^{h}2^i =2^{h+1}-1$$h$$n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$$O(\log n)$$n-1\rightarrow O(n)$

Se estivéssemos construindo uma árvore balanceada a partir de uma lista ordenada , escolheríamos o elemento do meio como nosso nó raiz. Se estivermos construindo uma árvore aleatoriamente, é provável que qualquer um dos nós seja escolhido e a altura da nossa árvore seja: Sabemos que em uma árvore de pesquisa binária, a subárvore esquerda deve conter apenas chaves menores que o nó raiz. Portanto, se escolhermos aleatoriamente o elemento , a subárvore esquerda possui elementos e a subárvore direita possui elementos, de forma mais compacta:$\{ 1,2,\dots,n\}$$n$

$$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ $i^{th}$$i-1$$n-i$$h_n=1+\max (h_{i-1},h_{n-i})$. A partir daí, faz sentido que, se cada elemento tiver a mesma probabilidade de ser escolhido, o valor esperado seja apenas a média de todos os casos (em vez de uma média ponderada). Portanto:$\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

Como tenho certeza de que você notou, desviei um pouco de como o CLRS prova isso, porque o CLRS usa duas técnicas de prova relativamente comuns que são desconcertantes para os não iniciados. O primeiro é usar expoentes (ou logaritmos) do que queremos encontrar (neste caso, altura), o que torna a matemática um pouco mais limpa; o segundo é usar funções indicadoras (que vou ignorar aqui). O CLRS define a altura exponencial como , portanto a recorrência análoga é .$Y_n=2^{h_n}$$Y_n=2\times\max (Y_{i-1},Y_{n-i})$

Supondo que a independência (que cada desenho de um elemento (dentre os elementos disponíveis) seja a raiz de uma subárvore seja independente de todos os desenhos anteriores), ainda temos a relação: para o qual realizei duas etapas: (1) movendo o fora porque é uma constante e uma das propriedades das somas é que , e (2) movendo o 2 para fora porque também é uma constante e uma das propriedades dos valores esperados é . Agora vamos substituir o

$$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$$ $\frac{1}{n}$$\sum_i ci=c\sum_i i$$\operatorname{E}[ax]=a\operatorname{E}[x]$$\max$funcionar com algo maior, porque de outra forma simplificar é difícil. Se argumentarmos por não negativo , : , então: modo que o último passo decorra da observação de que para , e e indo todo o caminho para , e , portanto, cada termo$X$$Y$$\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$ $$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$$ $i=1$$Y_{i-1}=Y_{0}$$Y_{n-i}=Y_{n-1}$$i=n$$Y_{i-1}=Y_{n-1}$$Y_{n-i}=Y_{0}$$Y_0$para aparece duas vezes, para que possamos substituir o somatório inteiro por um análogo. A boa notícia é que temos um nome de repetição ; a má notícia é que não estamos muito mais longe do que começamos.$Y_{n-1}$$\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$

Neste ponto, o CLRS extrai um nome de operação prova de indução de seu ... repertório de experiência matemática, um que inclui uma identidade eles deixam para o usuário provar. O que é importante sobre a escolha deles é que seu maior termo é e lembre-se de que estamos usando a altura exponencial que . Talvez alguém comente por que esse binômio em particular foi escolhido. A idéia geral, porém, é ligar acima de nossa recorrência com uma expressão para alguma constante .$\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$$\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$$n^3$$Y_n=2^{h_n}$$h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$$n^k$$k$

Para concluir com um liner:

$$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n)$$