Consideremos un árbol de búsqueda binario completo de altura $k$ (la raíz está en el nivel $1$ y las hojas en el nivel $k$ ). Por completo me refiero a que todas las hojas están a nivel $k$ y nivel $k$ tiene exactamente $2^{k-1}$ hojas. En otras palabras, hay $2^0 + \cdots + 2^{k-1} = 2^k -1$ nodos del árbol.
Buscar en se refiere al hecho de que dado cualquier árbol que no sea una hoja $x$ entonces el valor de $x$ es mayor que el hijo izquierdo pero menor que el hijo derecho (wlog asume que todos los valores son distintos).
Supongamos que queremos encontrar una hoja con un valor $z$ . Calcular esto es fácil, para cada comparación bajamos un nivel en el árbol, así que en total $k$ Se necesitan comparaciones para determinar la ubicación de $z$ (si existe en el árbol).
¿Y si quisiéramos buscar $z$ en todos los nodos, y no sólo en las hojas. ¿Cuántas comparaciones cabría esperar?
Mis cálculos: 1 comparación es necesaria para determinar si $z$ está en el nivel 1 (la raíz). 2 comparaciones para el nivel 2, etc. Dado $n$ nodos en total, el número de nodos en el nivel $t$ es $2^{t-1}$ . Por lo tanto, la probabilidad de que $z$ está en el nivel $t$ es $2^{t-1}/n$ . Por tanto, el número esperado de comparaciones es $1*(1/n) + 2*(2/n) + \cdots + k*(2^{k-1}/n) = \frac{1}{n}(1*2^0 + 2*2^1 + \cdots k*2^{k-1}).$ Sea $f(x) = x + x^2 + \cdots + x^k$ . Entonces claramente la suma entre paréntesis es igual a $f'(2)$ . $f(x) = \frac{x^{k+1}-x}{x-1}$ y así $f'(2) = 2^k(k-1)-1$ . El número esperado de comparaciones en $n$ los elementos/nodos son, por tanto $\frac{2^k(k-1)-1}{2^k-1}$ que parece estar muy cerca de $\frac{2^k(k-1)-1}{2^k-1} \approx \frac{2^k(k-1)}{2^k}= k-1 < k =$ número de comparaciones cuando se buscan sólo hojas. En otras palabras, la búsqueda de hojas sólo añade una comparación más en la expectativa. Otra forma de decirlo es que la diferencia entre el peor caso y el caso esperado es de una sola comparación. ¿Es esto correcto?
