Download 2.3 Arboles binarios de busqueda construidos aleatoriamente

Análisis del caso promedio
• El plan:
– Probabilidad
– Análisis probabilista
– Árboles binarios de búsqueda construidos
aleatoriamente
– Tries, árboles digitales de búsqueda y Patricia
– Listas “skip”
– Árboles aleatorizados
Técnicas Avanzadas de Programación - Javier Campos
109
Abb’s construidos aleatoriamente
• Recordar… árbol binario de búsqueda (abb):
– La clave de todo nodo es mayor o igual
si
que las de sus descendientes
izquierdos y menor que las de
su
a
sus descendientes derechos.
– Las operaciones básicas (búsqueda,
sin
ama
inserción, borrado…) tienen un
al
eso
coste O(h), donde h es la altura
del árbol.
– La altura de un abb varía con las inserciones y
borrados y, en el peor caso, puede llegar a ser igual al
número de nodos, O(n).
¿Qué ocurrirá en un caso “promedio”?
Técnicas Avanzadas de Programación - Javier Campos
110
Abb’s construidos aleatoriamente
• Abb de n nodos construido aleatoriamente:
– Es el resultante tras la inserción consecutiva de n
claves en orden aleatorio en un árbol vacío,
suponiendo que las n! permutaciones posibles de las
claves son equiprobables.
– La pregunta: ¿cuál es el coste promedio de las
operaciones con estos árboles?,
es decir, ¿cuál es la altura media de estos árboles?
– La respuesta no es trivial… ¡iremos por partes!
Técnicas Avanzadas de Programación - Javier Campos
111
Abb’s construidos aleatoriamente
• Longitud de los caminos internos y externos de
un árbol binario
si
– Definición. Árbol binario extendido:
el resultante de añadir un nodo
su
a
especial en el lugar de cada
sin
ama
subárbol vacío.
– Definición. Longitud de
al
eso
caminos externos, E: es la suma
E = 26
de las longitudes de todos los
I = 12
caminos desde la raíz hasta las hojas, .
– Definición. Longitud de caminos internos, I: es la
suma de las longitudes de todos los caminos desde la
raíz hasta todos los nodos internos, .
Técnicas Avanzadas de Programación - Javier Campos
112
Abb’s construidos aleatoriamente
• Teorema: E = I + 2n, donde n es el número de
nodos internos.
– Demostración: supongamos que se borra un nodo
interno V a distancia k de la raíz y tal que sus dos hijos
son hojas.
• En tal caso, E disminuye en 2(k+1), porque los hijos de V
desaparecen, y aumenta en k, porque V pasa a ser hoja, luego
E se convierte en E-k-2.
• Por otra parte, I disminuye en k.
• Por tanto, E-I disminuye en 2 por cada nodo que se borra.
• Borrando los n nodos se llega a un árbol vacío, es decir con
E = I = E-I = 0, por tanto, E-I = 2n.
Técnicas Avanzadas de Programación - Javier Campos
113
Abb’s construidos aleatoriamente
• Notación y relación fundamental:
– Cn: número medio de comparaciones en una búsqueda
con éxito en un árbol de n nodos construido aleatoriamente, suponiendo que la búsqueda de toda clave es
equiprobable.
– Cn': número medio de comparaciones en una búsqueda
sin éxito, suponiendo que cada uno de los n+1
intervalos entre las claves y fuera de sus valores
extremos son equiprobables.
– Entonces: Cn = 1 + I/n y Cn' = E/(n+1)
– Por tanto (E = I + 2n):
Técnicas Avanzadas de Programación - Javier Campos
 1
C n  1  C n  1
 n
114
Abb’s construidos aleatoriamente
• Finalmente…
Supongamos que cada una de las n! ordenaciones
posibles de las n claves es una secuencia de inserción
igualmente probable para construir el árbol
– El número de comparaciones necesarias para
encontrar una clave es exactamente uno más que el
número de comparaciones que se necesitaban cuando
esta clave no estaba en el árbol, por tanto:
C0  C1    C n 1
Cn  1 
n
que unido a
 1
C n  1  C n  1
 n
nos da la recurrencia:
(n+1)Cn' = 2n + C0' + C1' +  + Cn-1'
Técnicas Avanzadas de Programación - Javier Campos
115
Abb’s construidos aleatoriamente
– Para resolver (n+1)Cn' = 2n + C0' + C1' +  + Cn-1'
se resta
nCn-1' = 2(n-1) + C0' + C1' +  + Cn-2'
y se obtiene (n+1)Cn' - nCn-1' = 2 + Cn-1'
es decir
Cn' = Cn-1' + 2/(n+1)
y como
C0' = 0, entonces Cn' = 2Hn+1 – 2
donde Hn es la serie armónica
n
Aplicando
1
H n    ln n  O(1)
i 1i
 1
C n  1  C n  1
 n
y simplificando:
 1
C n  21   H n  3  O (log n)
 n
Técnicas Avanzadas de Programación - Javier Campos
116
Abb’s construidos aleatoriamente
• El anterior es un buen resultado, pero…
– Si un abb se construye aleatoriamente y se “somete”
después a una secuencia de inserciones aleatorias y de
borrados aleatorios, el árbol resultante pierde la
aleatoriedad, con lo que se carece de resultados
teóricos sobre el coste promedio de las operaciones.
– No obstante, la evidencia empírica sugiere que tras
una secuencia de borrados e inserciones aleatorios, la
altura del árbol tiende a disminuir, si bien no he
encontrado en la literatura la explicación teórica de
este comportamiento.
Técnicas Avanzadas de Programación - Javier Campos
117
Abb’s construidos aleatoriamente
• Otra definición de “abb’s elegidos al azar”:
– Hipótesis de equiprobabilidad de todos los abb’s
posibles de n nodos.
– Primera cuestión: ver que ésta es una definición de
“abb aleatorio” distinta a la anterior.
• Hay 5 abb’s distintos de 3 nodos (suponer a1<a2<a3), por
tanto cada uno tiene probabilidad 1/5:
a1
a3
a2
a2
a3
a1
a1
a3
a2
a1
a3
a3
a2
Técnicas Avanzadas de Programación - Javier Campos
a2
a1
118
Abb’s construidos aleatoriamente
• Sin embargo, construyéndolos a partir de las permutaciones
posibles de a1, a2, a3 salen 6, cada uno con probabilidad 1/6:
a1
a1a2a3
a3
a2
a2
a2a1a3
a1
a3
a1
a1a3a2
a3
a1
a2
a3
a2
a3
a2
a2a3a1
a1
a3a1a2
a3a2a1
a3
a2
a1
Es decir, ¡éste árbol tiene el doble de
probabilidad que los otros! (1/3)
Técnicas Avanzadas de Programación - Javier Campos
119
Abb’s construidos aleatoriamente
• Cálculo de la profundidad media de un nodo en
un abb de n nodos elegido al azar:
– Recordar: longitud de caminos internos, In, de un
árbol de n nodos (suma de las longitudes de todos los
caminos desde la raíz hasta todos los nodos internos).
– I1 = 0
– Un árbol de n nodos tiene un subárbol izquierdo con i
nodos (para algún 0  i < n) y un subárbol derecho con
n-i-1 nodos, por tanto:
In = Ii + In-i-1 + n -1
Técnicas Avanzadas de Programación - Javier Campos
120
Abb’s construidos aleatoriamente
– Hipótesis adicional: el número de nodos de un
subárbol (izquierdo o derecho) de un abb de n nodos
elegido al azar es equiprobable para todos los valores
posibles (de 0 a n-1), por tanto:
1 n 1
E[ I i ]  E[ I n i 1 ]   I j
n j 0
promedio de la longitud interna del subárbol izquierdo
– Y aplicándolo a la recurrencia anterior (se omite el
operador esperanza por comodidad), se obtiene la
recurrencia:
2  n 1 
I n    I j   n 1
n  j 0 
Técnicas Avanzadas de Programación - Javier Campos
121
Abb’s construidos aleatoriamente
– Resolución de:
2  n 1 
I n    I j   n 1
n  j 0 
• Multiplicando por n:
 n 1 
nI n  2   I j   n 2  n
 j 0 
• Y por tanto:
n 2 
(n  1) I n 1  2   I j   (n  1) 2  (n  1)
 j 0 
• Restando ambas:
nI n  (n  1) I n 1  2 I n 1  2n  2
• Es decir:
nI n  (n  1) I n 1  2n  2
Técnicas Avanzadas de Programación - Javier Campos
122
Abb’s construidos aleatoriamente
– Y para resolver esta nueva recurrencia:
nI n  (n  1) I n 1  2n  2
• Dividiendo por n(n+1) y despreciando la constante:
In
I
2
 n 1 
n 1
n
n 1
• Luego:
I n 1 I n  2 2


n
n 1 n
I n  2 I n 3
2


n 1 n  2 n 1

I 2 I1 2
 
3
2 3
Técnicas Avanzadas de Programación - Javier Campos
n 11
In
I1
 2
sumando :
n 1 2
i 3 i
123
Abb’s construidos aleatoriamente
• Finalmente, como
n 11
2
i 3 i
 O (log n) (serie armónica)
• Se sigue que
I n  O (n log n)
• Y como In es la suma de las longitudes de todos los caminos
desde la raíz hasta todos los nodos internos, entonces la
profundidad media de cada nodo es O(log n).
Técnicas Avanzadas de Programación - Javier Campos
124
Abb’s construidos aleatoriamente
• De nuevo, al anterior es un buen resultado pero…
– El efecto de las operaciones de borrado destruye la
aleatoriedad.
– No he encontrado en la literatura resultados teóricos
sobre el coste promedio resultante considerando
secuencias de operaciones de inserción y borrado.
Abb de 500 nodos
Profundidad media: 9’98
Tras 250.000 pares de operaciones de inserción y borrado. Profundidad media: 12’51
Técnicas Avanzadas de Programación - Javier Campos
125
Abb’s construidos aleatoriamente
• Para evitar el crecimiento de la altura del árbol
hay dos tipos de soluciones:
– Realizar alguna operación de “equilibrado” del árbol
tras cada inserción/borrado (árboles AVL, árboles 2-3,
árboles B, árboles rojinegros).
– Renunciar a un equilibrado tan estricto y aplicar
alguna regla de re-estructuración que ayude a que las
futuras secuencias de operaciones sean más eficientes
(análisis amortizado, lo veremos más adelante).
• Este tipo de estructuras se llaman auto-organizativas (listas
auto-organizativas, árboles auto-organizativos o “splay
trees”).
Técnicas Avanzadas de Programación - Javier Campos
126