Prueba de que un árbol de búsqueda binario construido aleatoriamente tiene altura logarítmica

¿Cómo demuestra que la altura esperada de un árbol de búsqueda binario construido aleatoriamente con $n$ nodos es $O(\log n)$ ? Hay una prueba en CLRS Introducción a los algoritmos (capítulo 12.4), pero no la entiendo.

Primero pensemos en esto intuitivamente. En el mejor de los casos, el árbol está perfectamente equilibrado; En el peor de los casos, el árbol está completamente desequilibrado:

$p$$n=\sum_{i=0}^{h}2^i =2^{h+1}-1$$h$ , lo que quiere decir que tiene unaaltura O ( log n ) . Para el árbol completamente desequilibrado, la altura del árbol es simplemente n - 1 → O ( n ) . Entonces tenemos nuestros límites.$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)$

$\{ 1,2,\dots,n\}$$n$

$$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ $i^{th}$$i-1$elementos y el subárbol derecho tiene elementos , de manera más compacta: . A partir de ahí, tiene sentido que si cada elemento tiene la misma probabilidad de ser elegido, el valor esperado es solo el promedio de todos los casos (en lugar de un promedio ponderado). Por lo tanto:$n-i$$h_n=1+\max (h_{i-1},h_{n-i})$$\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

Como estoy seguro de que has notado, me he desviado ligeramente de cómo CLRS prueba esto, porque CLRS usa dos técnicas de prueba relativamente comunes que son desconcertantes para los no iniciados. El primero es usar exponentes (o logaritmos) de lo que queremos encontrar (en este caso, altura), lo que hace que las matemáticas funcionen un poco más limpiamente; el segundo es usar funciones de indicador (que solo voy a ignorar aquí). CLRS define la altura exponencial como , por lo que la recurrencia análoga es .$Y_n=2^{h_n}$$Y_n=2\times\max (Y_{i-1},Y_{n-i})$

Suponiendo que la independencia (que cada sorteo de un elemento (de los elementos disponibles) sea la raíz de un subárbol es independiente de todos los sorteos anteriores), todavía tenemos la relación: para lo cual hice dos pasos: (1) mover el afuera porque es una constante y una de las propiedades de las sumas es que , y (2) mover el 2 afuera porque también es una constante y una de las propiedades de los valores esperados es . Ahora vamos a reemplazar el

$$\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 con algo más grande porque, de lo contrario, simplificar es difícil. Si argumentamos por , no negativo : , luego: tal que el último paso se desprende de la observación de que para , e y va todo camino hacia , e , entonces cada término$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$a aparece dos veces, por lo que podemos reemplazar toda la suma por una análoga. La buena noticia es que tenemos una recurrencia ; La mala noticia es que no estamos mucho más allá de donde comenzamos.$Y_{n-1}$$\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$

En este punto, CLRS extrae una prueba de inducción de su ... repertorio de experiencia matemática, uno que incluye una identidad que dejan que el usuario pruebe. Lo importante de su elección es que su término más grande es , y recuerde que estamos usando una altura exponencial tal que . Quizás alguien comentará por qué se eligió este binomio en particular. Sin embargo, la idea general es vincular desde arriba nuestra recurrencia con una expresión para alguna 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 con una línea:

$$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)$$