Búsquedas con distintas probabilidades de acceso

El mayor interés de los splay trees es que se acercan a los árboles óptimos que diseñamos en el capítulo de cotas inferiores cuando teníamos probabilidades de acceso conocidas, pero sin necesidad de ningún preprocesamiento. Demostraremos que si realizamos $m$ búsquedas sobre un splay tree $T$, donde el elemento $x$ es buscado $q(x)$ veces (por lo tanto $\sum_{x \in T} q(x) = m$), entonces el costo total de las búsquedas es

$$O\left(m + \sum_{x \in T} q(x)\log \frac{m}{q(x)} \right)$$

Para ello, reusaremos el análisis ya hecho y sólo cambiaremos la noción de tamaño de un árbol. Definiremos ahora el peso de un nodo como la probabilidad de ser buscado, $w(x) = \frac{q(x)}{m}$, y definiremos el tamaño de un subárbol con raíz $x$ como la probabilidad de que la búsqueda pase por el nodo $x$, es decir,

$$s_i(x) ~~=~~ \sum_{y \in S_i(x)} w(y)$$

Note que $s_i(x)$ es un número entre $0$ y $1$, por lo que $r_i(x)$ es negativo, pero aún el logaritmo es monótonamente creciente. Todo el análisis realizado anteriormente vale, pues lo único que utilizamos sobre $s_i(x)$ fue que $s_i(\cdot)$ (y $r_i(\cdot)$) es mayor en un subárbol que en un subconjunto disjunto de sus subárboles. Tenemos entonces que el costo amortizado de $splay(x)$ es

$$\begin{array}{c c c} \hat{c}(x) & \le & 1+3(r_m(x)-r_0(x)) ~~=~~ 1+3(\log_2 s_m(x) - \log_2 s_0(x))\\ & = & 1+3(\log_2 1 - \log_2 s_0(x)) ~~=~~ 1+3 \log\frac{1}{s_0(x)} \\ &\le& 1+3\log\frac{1}{w(x)} ~~=~~ 1+3\log\frac{m}{q(x)}. \end{array}$$

En la segunda línea usamos que, al final de la operación, $x$ está en la raíz, por lo cual $s_m(x) = 1$. En la tercera línea usamos que, sin importar dónde estuviera $x$ en el árbol antes de empezar la operación, tendremos $s_0(x) \ge w(x)$.

Sabemos que realizamos $splay(x)$ $q(x)$ veces, de modo que sumando sobre todos los $x$ obtenemos el costo prometido. Note que esto implica un costo amortizado de $O(1+H)$ por operación, donde $H$ es la entropía de las probabilidades de acceso a los elementos.

Los splay trees tienen otras propiedades interesantes que se pueden demostrar de forma similar, variando la definición de $s(x)$.