Download 07-Diccionario

7. El TDA Diccionario
¿Qué es un Diccionario ?
• Dado un conjunto de elementos {X1, X2, ..., XN}, todos
distintos entre sí, se desea almacenarlos en una
estructura de datos que permita la implementación
eficiente de las operaciones:
• búsqueda(X): dado un elemento X, conocido como
llave de búsqueda, encontrarlo dentro del conjunto o
decir que no está.
• inserción(X): agregar un nuevo elemento X al conjunto.
• eliminación(X): eliminar el elemento X del conjunto.
• Estas operaciones describen al TDA diccionario. En el
presente capítulo se verán distintas implementaciones
de este TDA y se estudiarán las consideraciones de
eficiencia de cada una de dichas implementaciones.
interface Diccionario {
public Object
buscar(Comparable x);
public boolean cambiar(Comparable x,Object y);
public boolean agregar(Comparable x,Object y);
public boolean borrar(Comparable x);
}
Implementaciones sencillas
• Una lista enlazada, con la inserción de nuevos
elementos al comienzo.
– búsqueda: O(n) (búsqueda secuencial).
– inserción: O(1) (insertando siempre al comienzo de la
lista).
– eliminación: O(n) (búsqueda + O(1)).
• Arreglo ordenado: inserción y eliminación
ineficientes ("correr" los elementos)
• Sin embargo, la ventaja que tiene mantener el
orden es que es posible realizar una búsqueda
binaria para encontrar el elemento buscado.
Programacion de la Búsqueda binaria
Invariante
Inicialmente: i = 0 y j = n-1.
En cada iteración:
Si el conjunto es vacío (j-i < 0), o sea si j < i, entonces el
elemento x no está en el conjunto (búsqueda infructuosa).
En caso contrario, m = (i+j)/2. Si x = a[m], el elemento fue
encontrado (búsqueda exitosa).
Si x < a[m] se modifica j = m-1, sino se modifica i = m+1 y se
sigue iterando.
Programacion de la Búsqueda binaria
public int busquedaBinaria(int []a, int x) {
int i=0, j=a.length-1;
while (i<=j) {
int m=(i+j)/2;
if (x==a[m])
return m;
else if (x<a[m])
j=m-1;
else
i=m+1;
}
return NO_ENCONTRADO;
// NO_ENCONTRADO se define como -1
}
Eficiencia de la Búsqueda binaria
• Todo algoritmo de búsqueda basado en comparaciones
corresponde a algún árbol de decisión.
• Cada nodo de dicho árbol corresponde al conjunto de
elementos candidatos en donde se encuentra el
elemento buscado.
• Los arcos del árbol corresponden a los resultados de
las comparaciones, (mayor que o menor que)
• Es decir, es un árbol de decisión binario.
• El número de comparaciones realizadas por el
algoritmo de búsqueda es igual a la altura del árbol de
decisión (profundidad de la hoja más profunda).
Eficiencia de la Búsqueda binaria
Lema: sea D un árbol binario de altura h. D tiene a lo más 2h hojas.
Demostración: por inducción.
Lema: un árbol binario con H hojas debe tener una profundidad de
al menos
Demostración: directo del lema anterior.
Si n es el número de nodos de elementos del conjunto, el número
de respuestas posibles (hojas del árbol de decisión) es de n+1, el
lema anterior implica que el costo en el peor caso es mayor o igual
que el logaritmo del número de respuestas posibles.
Corolario: cualquier algoritmo de búsqueda mediante
comparaciones se demora al menos
preguntas en el
peor caso. Por lo tanto, la búsqueda binaria es óptima.
Métodos auto-organizantes
• Idea: cada vez que se accede a un elemento Xk se modifica la
lista para que los accesos futuros a Xk sean más eficientes.
Algunas políticas de modificación de la lista son:
• TR (transpose): se intercambia de posición Xk con Xk-1
(siempre que k>1).
• MTF (move-to-front): se mueve el elemento Xk al principio de
la lista.
• Se puede demostrar que
Costooptimo<=CostoTR<=CostoMTF<=2Costooptimo.
¿Arbol Binario de Búsqueda o
Arbol de Búsqueda Binaria(ABB)?
• Estructura de datos (recursiva) que está vacía , o contiene un
nodo raíz con un valor y referencias a dos ABBs (izquierdo y
derecho)
• los valores contenidos en el subárbol izquierdo son menores
que el valor en la raíz
• los valores contenidos en el subárbol derecho son mayores
que el valor en la raíz
Ejemplo:
raíz
D
izq valor der
B
A
F
C
E
G
Diccionario: implementación con ABB
 tiempo de todas las operaciones proporcional a altura del árbol
 si está balanceado, altura=log2n
E E’
izq pal sig der
raíz
C C’
B B’
G G’
D
D’
H H’
class Nodo{
public Comparable palabra;
public Object significado;
public Nodo izq, der;
public Nodo(
Comparable x,Object y,Nodo z,Nodo w){
palabra=x; significado=y; izq=z; der=w;
}
}
class DiccionarioArbol implements Diccionario
{
protected Nodo raiz;
public Diccionario(){
raiz=null;
}
public Object buscar(Comparable x){
Nodo r=referencia(x,raiz);
return r==null ? null : r.significado;
}
public boolean cambiar(Comparable x,Object y){
Nodo r=referencia(x,raiz);
if(r==null) return false;
r.significado = y;
return true;
}
//búsqueda iterativa en un ABB
protected Nodo referencia(Comparable x,Nodo r){
while(r!=null){
int c=x.compareTo(r.palabra);
if(c==0) return r;
r = c<0 ? r.izq : r.der;
}
return null;
}
//búsqueda recursiva en un ABB
protected Nodo referencia(Comparable x,Nodo r){
if(r==null) return null;
int c=x.compareTo(r.palabra);
if(c==0) return r;
return referencia(x, c<0 ? r.izq : r.der);
}
public boolean agregar(Comparable x,Object y)
throws DiccLleno{
if(referencia(x,raiz)!=null) return false;
raiz=agregar(x,y,raiz);
return true;
}
protected Nodo agregar
(Comparable x,Object y,Nodo r)
throws DiccLleno{
if(r==null) return new Nodo(x,y,null,null);
if(x.compareTo(r.palabra) < 0)
r.izq=agregar(x,y,r.izq);
else
r.der=agregar(x,y,r.der);
return r;
}
Solución 2: en un sólo recorrido no recursivo del ABB
public boolean agregar(Comparable x,Object y)
throws DiccLleno{
Nodo q=new Nodo(x,y,null,null);
if(raiz==null){raiz=q; return true;}
Nodo r=raiz;
while(true){
int c=x.compareTo(r.palabra);
if(c==0) return false; //ya existe
if(c<0)
if(r.izq==null){r.izq=q; break;}
else r=r.izq;
else
if(r.der==null){r.der=q; break;}
else r=r.der;
}
return true;
}
public boolean borrar(Comparable x){
Nodo r=referencia(x, raiz);
if(r==null) return false;
raiz=borrar(x,raiz);
return true;
}
//borrar Nodo con x y devolver raíz del ABB
protected Nodo borrar(Comparable x,Nodo r){
if(r==null) return null;
int c=x.compareTo(r.palabra);
if(c==0) return borrar(r);
if(c<0)
r.izq=borrar(x,r.izq);
else
r.der=borrar(x,r.der);
return r;
}
Caso 1 y 2: borrar hoja izquierda o derecha(ej:“H”)
E E’
raíz
izq pal sig der
C C’
G
B
B’
D
r
G’ null
D’
H
H’
H
H’
Caso 3: borrar raíz reemplazando por mayor de árbol izquierdo
Caso 3.1: borrar “C” (mayor en raíz de árbol izquierdo)
E E’
raíz
izq pal sig der
r
G G’
null B B’
B
B’
D
D’
Caso 3: borrar “E” (mayor en el extremo derecho de árbol izquierdo)
r
D D’
raíz
izq pal sig der
C C’ null
G G’
B
B’
D
D’
H
H’
protected Nodo borrar(Nodo r){
//caso 1: sólo árbol derecho
if(r.izq==null) return r.der;
//Caso 2:solo árbol izquierdo
if(r.der==null) return r.izq;
//Caso 3:reemplazar por mayor de arbol izq
//caso 3.1: mayor en raíz de árbol izquierdo
if(r.izq.der==null){
r.palabra = r.izq.palabra;
r.significado = r.izq.significado;
r.izq = r.izq.izq; //enlazar hijos menores
}
//caso 3.2: mayor a la derecha de árbol izq
else{
//buscar ref de antecesor de mayor
Nodo rAnt=r.izq;
while(rAnt.der.der!=null)
rAnt=rAnt.der;
//reemplazar raiz por mayor
r.palabra = rAnt.der.palabra;
r.significado = rAnt.der.significado;
rAnt.der = rAnt.der.izq;//enlazar menores
}
return r;
}
Propuesto: borrar reemplazando por menor de árbol derecho
Solución 2: en un recorrido no recursivo
public boolean borrar(Comparable x)
{
//buscar ref r de x, recordando ref antecesor
Nodo r=raiz, rAnt=null;
while(r!=null)
{
int c=x.compareTo(r.palabra);
if(c==0) break;
rAnt=r;
r=c<0 ? r.izq: r.der;
}
if(r==null) return false;//no está
//borrar nodo r, actualizando antecesor
if(r==raiz)
raiz=borrar(r);
else if(r==rAnt.izq)
rAnt.izq=borrar(r);
else
rAnt.der=borrar(r);
return true;
}
Árboles AVL
(Adelson-Velskii & Landis, 1962)
En árboles de búsqueda binaria la complejidad de las
operaciones encontrar, insertar y eliminar son en el
peor caso: (n).
Puede mejorarse! Idea: árboles balanceados.
Definición: Un árbol es un árbol de búsqueda binario
en el cual para cada sub-árbol T ' = < L, x, R > se
cumple que | h(L) - h(R) |  1
El factor de balance es frecuentemente incluido como
información en cada nodo.
22
|h(I) – h(D)| < = 1
Este es un árbol AVL
23
Este no es un árbol AVL (el nodo con un * no cumple la condición requerida)
24
Objetivos
1. Cómo pueden mantenerse las características de un
árbol AVL (invariante de la estructura de datos)
cuando se insertan y eliminan nodos?
2. Veremos que para árboles AVL la complejidad de las
operaciones es en el peor caso
= O(altura del árbol AVL) y que esto es
= O(log n)
25
Preservación del invariante de un AVL
• Despues de insertar y eliminar nodos de un parbol
debemos procurar que el árbol resultante siga
manteniendo las carácterísticas de un árbol AVL.
• Por ejemplo: si ponemos el 1, 2 y 3 en ese órden, al
insertar 3 se desbalancea
• Al insertar 5,4,7,6 y 9 y luego eliminar 4 se
desbalancea
• Solución ? Re-balancing: rotaciones simple y doble
26
Existen sólo 2 casos (y sus espejos)
• Caso desbalanceo por inserción
– El nuevo elemento es insertado en el subárbol
derecho (izquierda) del hijo derecho, quien ya era
más alto que el subárbol izquierdo por un nivel.
– El nuevo elemento es insertado en el sub-arbol
izquierdo(derecho) del hijo derecho(izquierdo) el
cual ya era mayor que el subárbol
izquierdo(derecho) en 1
27
Rotacion simple (para el caso en que el subárbol
derecho crece demasiado cuando se le hace una
inserción en su subárbol derecho)
Es transformado en
28
Rotación doble (para el caso en que el subárbol
derecho crezca demasiado cuando se le hace una
inserción en su subárbol izquierdo)
Rotacion doble
Es transformado en
29
b
Primera rotación
a
x
W
nuevo
nuevo
a
c
y
Z
Segunda rotación
b
W
c
nuevo
y
Z
30
Re-balanceo después de la inserción:
Deapues de una inserción el árbol puede aún estar
balanceado o :
teorema: después de una inserción solo se necesita una
rotación simple o doble en el primer nodo
desbalanceado * para restablecer las propiedades de
balance de un árbol AVL.
(* : on the way from the inserted node to the root).
Razón: despues de la rotación el árbol vuelve a su
altura original !
31
El mismo análisis para borrar nodos
• Solo 2 casos (y sus espejos)
– El elemento borrado reduce la altura del subárbol
derecho (izquierdo) que ya era más chico en 1 que
el izquierdo (derecho)
– El elemento borrado reduce la altura del izquierdo
(derecho) dejando el subárbol izquierdo del
derecho (derecho del izquierdo) con una altura
mayor en 2
32
Gráficamente
Nodo borrado
1
1
1
Las situaciones son las mismas que para la insersión
33
Re-balanceo despues de borrado
Despues de borrar un nodo el árbol puede aún estar balanceado
o habrá que re-balancearlo:
Teorema: despues de borrar un nodod en un arbol AVL las
propiedades de balanceo del sub-árbol que tiene su raíz como
primer* nodo que se desbalancea se poueden restituir con
una rotación simple o doble.
(* : on the way from the deleted note to the root).
Sin embargo: la altura del sub-arbol resultante puede haberse
acortado en 1, eso significa que se puede haber introducido
un desbalance por lo que podría ser necesario
(recursivamente) hacer rotaciones hasta llegar eventualmente
a la raíz
34
About Implementation



While searching for unbalanced sub-tree after an operation
it is only necessary to check the parent´s sub-tree only
when the son´s sub-tree has changed it height.
In order make the checking for unbalanced sub-trees more
efficient, it is recommended to put some more information
on the nodes, for example: the height of the sub-tree or
the balance factor (height(left sub-tree) – height(right subtree)) This information must be updated after each
operation
It might be convenient to have an operation that returns
the parent of a certain node (for example, by adding a
pointer to the parent).
35
Complexity analysis– worst case
Sea h la altura de un arbol AVL.
Búsqueda: como en un árbol de búsqueda binaria O(h).
Insert: como en un árbol de búsqueda binaria (O(h)) mas el costo
de una rotación simple o doble (solo una!), que es constante :
o sea O(h).
delete: como en un árbol de búsqueda binaria (O(h)) más el
costo (posible) de una rotación en cada nodo desde el nodo
eliminado hasta la raíz, que es a lo más órden de la altura del
árbol: O(h).
Todas las operaciones son O(h). ¿Pero cuanto es h ?
36
Calculando altura de un árbol AVL
Sea N(h) el numoero mínimo de nodos para un árbol AVL de
altura h (h altura máxima para n)
In an AVL-tree having height h.
Principio de construccion
N(0)=1, N(1)=2,
0
N(h) = 1 + N(h-1) + N(h-2) for h  2.
N(3)=4, N(4)=7
Se parece a los números de Fibonacci
fibo(0)=0, fibo(1)=1,
fibo(n) = fibo(n-1) + fibo(n-2)
fib(3)=1, fib(4)=2, fib(5)=3, fib(6)=5, fib(7)=8
Calculando podemos decir que:
N(h) = fibo(h+3) - 1
1
2
3
37
Sea n el numero de nodos de un árbol AVL de altura h. Entonces se
cuple que n  N(h) , pues N(h) es el número mínimo
Recordemos que fibo(n) =(1 /sqrt(5)) (Ф1n - Ф2n)
con Ф1= (1+ sqrt(5))/2 ≈ 1.618
Ф2= (1- sqrt(5))/2 ≈ 0.618
Podemos entonces escribir
n  fibo(h+3)-1 = (Ф1 h+3 – Ф2h+3 ) / sqrt(5) – 1
n  (Ф1 h+3/sqrt(5)) – 3/2,
Por lo tanto, aplicando log a ambos lados
h+3+log Ф1(1/sqrt(5))  log Ф1(n+3/2),
Por lo tanto, hay una constante c para la cual
h  log Ф1(n) + c
= log Ф1(2) • log2(n) + c
= 1.44… • log2(n) + c = O(log n).
38
Arboles B (búsqueda externa)
• Los algoritmos vistos hasta ahora funcionan bien cuando
todos los datos estan en memoria RAM, la vual es (más)
rápida
• Grandes conjuntos de datos están guardados
normalmente en memoria secundaria (hard disk) de
acceso (más) lento (de 100-1000 veces más lento)
Acceso: siempre a un bloque completo (page) de datos
(4096 bytes), que es guardado en RAM (caché)
Por eficiencia: mantener el número de accesos a las páginas
bajo!
Un nodo = una página
39
Preámbulo: Arboles 2-3
• Los nodos internos pueden contener hasta 2
elementos
• por lo tanto un nodo interno puede tener 2 o 3 hijos,
dependiendo de cuántos elementos posea el nodo.
40
Propiedad
• todas las hojas están a la misma profundidad, es
decir, los árboles 2-3 son árboles perfectamente
balanceados
• La altura está acotada por
41
Inserción
• se realiza una búsqueda infructuosa y se inserta
dicho elemento en el último nodo visitado durante la
búsqueda,
• implica manejar dos casos distintos:
42
Ejemplos
43
Eliminación
• Físicamente se debe eliminar un nodo del último
nivel
• Si el elemento a borrar está en un nodo interno el
valor se reemplaza por el inmediatamente
anterior/posterior
• Estos necesariamente están en último nivel
44
Caso simple
• El nodo donde se encuentra Z contiene dos
elementos. En este caso se elimina Z y el nodo queda
con un solo elemento.
45
Caso complejo 1
• El nodo donde se encuentra Z contiene un solo
elemento. En este caso al eliminar el elemento Z el
nodo queda sin elementos (underflow). Si el nodo
hermano posee dos elementos, se le quita uno y se
inserta en el nodo con underflow.
46
Caso complejo 2
• Si el nodo hermano contiene solo una llave, se le quita un
elemento al padre y se inserta en el nodo con underflow.
• Si esta operación produce underflow en el nodo padre, se
repite el procedimiento anterior un nivel más arriba.
Finalmente, si la raíz queda vacía, ésta se elimina.
• Costo de las operaciones de búsqueda, inserción y eliminación
en el peor caso: Θ (log(n))
47
Para búsqueda esterna: una variante de árboles de
búsqueda:
1 node = 1 page
Multiple way search trees
48
Multiple way-search trees
Definición (recursiva) :
• La forma básica de un multiple way-search tree es un conjunto
vacío de claves {}
• Sean T0, ..., Tn multiple way-search trees con claves tomadas de
un conjunto común S, y sean k1,...,kn una secuencia de claves tales
que k1 < ...< kn. Entonces la secuencia :
T0 k1 T1 k2 T2 k3 .... kn Tn
Es un multiple way-search tree si se da que:
• Para cada claves x de T0 x < k1
• Para i=1,...,n-1, para cada clave x en Ti, ki < x < ki+1
• Para cada clave x de Tn kn < x
49
B-Tree
Definicion:
Un B-Tree of Order m es un multiple way tree con las siguientes
características
• 1  #(claves en la raíz)  2m
y
m  #(claves en el nodo)  2m
para todos los otros nodos.
• Todos los caminos de la raíz a alguna hoja son del mismo largo.
• Cada nodo interno (no hoja) con s claves tiene exactamente s+1
hijos.
• Árboles 2-3 es un caso particular para m=1
50
Ejemplo: un B-tree de orden 2:
51
Evaluación de B-trees
El número minimo posible de nodos que puede tener un B-tree
de orden m y altura h:
• Número de nodos en cada sub-tree
1 + (m+1) + (m+1)2 + .... + (m+1)h-1
= ( (m+1)h – 1) / m.
La raíz del ábol minimal tiene una sola clave y dos hijos, todos los
demas tienen m claves.
Sumando: número minimo de claves n en un B-tree de altura h:
n  2 (m+1)h – 1
Por lo tanto para todo B-tree de altura h con n llaves s e cumple:
h  logm+1 ((n+1)/2) .
52
Ejemplo
Lo siguiente se cumple para todo B-tree de altura h con n llaves:
h  logm+1 ((n+1)/2).
Ejemplo: para
• Page size: 1 KByte y (1024
• Cada clave mas el puntero: 8 bytes, nos caben 128 datos en
un nodo.
• Si tomamos m=63, para un número de datos de
n= 1 000 000
• Tenemos
h  log 64 500 000.5 < 4 por lo cual hmax = 3.
53
Algoritmo de búsqueda en un B-tree
Algorithm search(r, x)
//buscar x en un árbol de raiz r;
//variable global p = puntero al último node visitado
en r, buscar la primera clave y >= x o hasta que no hayan mas
if (y == x) {para, p = r, encontrado}
else
if (r una hoja) {parar, p = r, no encontrado}
else
if (no es la la última clave) {
search(puntero a nodo hijo anterior a y , x) }
else search(puntero a ultimo hijo, x)
54
Insert y delete de claves
Algoritmo insertar (r, x)
//insertar clave x en el árbol de raíz r
search( x , r);
if (x no encontrado) {
sea p la hoja donde paró la búsqueda:
insertar x en el nodo apuntado por p
en la posicion correcta ;
if (p tiene ahora mas de 2m+1 claves)
overflow(p);
}
55
Algoritmo de Particion (1)
Algoritmo
overflow (p) = split (p)
Algoritmo split (p)
caso 1: p tiene un padre q.
Dividir nodo p. La clave de la
mitad va para el padre.
consideración: el splitting puede
ir subiendo hasta llegar a la
raiz, en cuyo caso la altura de
todo el el árbol se incrementa
en uno.
56
Algoritmo Split (2)
Algoritmo split (p)
Caso 2: p es la raíz.
Dividir nodo .
crear un nodo nuevo
sobre el actual que
contiene la clave del
medio (root tiene
una clave).
57
Algoritmo borrar (r,x)
//borra la clave key x from tree having root r
search for x in the tree with root r;
if x found
{ if x is in an internal node
{ exchange x with the next bigger key x' in the tree
// if x is in an internal node then there must
// be at least one bigger number in the tree
//this number is in a leaf !
}
be p the leaf, containing x;
erase x from p;
if p is not in the root r
{ if p has m-1 keys
{underflow (p)} } }
58
Algorithm underflow (p)
if p has a neighboring node with s>m nodes
{ balance (p,p') }
else
// because p cannot be the root, p must have a neighbor with
m keys
{ be p' the neighbor with m keys; merge (p,p')}
59
Algorithm balance (p, p')
// balance node p with its neighbor p'
(s > m , r = (m+s)/2 -m )
60
Algorithm merge (p,p')
// merge node p with its neighbor
perform the following operation:
afterwards:
if( q <> root) and (q
has m-1 keys)
underflow (q)
else (if(q= root) and (q
empty)) {free q let
root point to p^}
61
Recursion
If when performing underflow we have to perform
merge, we might have to perform underflow
again one level up
This process might be repeated until the root.
62
Example:
B-Tree of
order 2 (m = 2)
63
Cost
Be m the order of the B-tree,
n the number of keys.
Costs for search , insert and delete:
O(h) = O(logm+1 ((n+1)/2) )
= O(logm+1(n)).
64
Remark:
B-trees can also be used as internal storage structure:
Especially: B-trees of order 1
(then only one or 2 keys in each node –
no elaborate search inside the nodes).
Cost of search, insert, delete:
O(log n).
65
Remark: use of storage memory
Over 50%
reason: the condition:
1/2•k  #(keys in the node)  k
For nodes  root
(k=2m)
66
Arboles Digitales
• Cuando sucede que:
– Los elementos de un conjunto se pueden representar
como una secuencia de bits:
X = b0b1b2...bk
– Ninguna representación de un elemento en particular
es prefijo de otra.
• Se puede usar un árbol digital:
– árbol binario donde la posición de un elemento no
depende de su valor, sino de su representación binaria.
– elementos se almacenan solo en sus hojas, pero no
necesariamente todas las hojas contienen elementos
– también es conocida como trie.
67
Ejemplo
• El siguiente ejemplo muestra un árbol digital con 5 elementos
68
Búsqueda en un árbol digital
• Para buscar un elemento X en un árbol digital se procede de la
siguiente manera:
• Se examinan los bits bi del elemento X, partiendo desde b0 en
adelante.
• Si bi = 0 se avanza por la rama izquierda y se examina el
siguiente bit, bi+1.
• Si bi = 1 se avanza por la rama derecha y se examina el
siguiente bit.
• El proceso termina cuando se llega a una hoja, único lugar
posible en donde puede estar insertado X.
69
Inserción en un árbol digital
• Suponga que se desea insertar el elemento X en el árbol
digital.
• Se realiza una búsqueda infructuosa de X hasta llegar a una
hoja, suponga que el último bit utilizado en la búsqueda
fue bk.
• Si la hoja esta vacía, se almacena X en dicha hoja. En caso
contrario, se divide la hoja utilizando el siguiente bit del
elemento, bk+1, y se repite el procedimiento, si es necesario,
hasta que quede solo un elemento por hoja.
• Con este proceso de inserción, la forma que obtiene el árbol
digital es insensible al orden de inserción de los elementos.
70
Eliminación en un árbol digital
• Suponga que el elemento a eliminar es X. Se elimina el
elemento de la hoja, y por lo tanto esta queda vacía.
• Si la hoja vacía es hermana de otra hoja no vacía, entonces
ambas se fusionan y se repite el procedimiento mientras sea
posible.
71
Costo promedio de búsqueda en un
árbol digital
• El costo promedio de búsqueda en un árbol digital es mejor
que en un ABB, ya que en un árbol digital la probabilidad que
un elemento se encuentre en el subárbol izquierdo o derecho
es la misma, 1/2, dado que sólo depende del valor de un bit (0
o 1). En cambio, en un ABB dicha probabilidad es proporcional
al "peso" del subárbol respectivo.
• Hn son los números armónicos y P(n) es una función periódica
de muy baja amplitud (O(10-6))
72
Arboles de búsqueda digital
• En este tipo de árboles los elementos se almacenan en
los nodos internos, al igual que en un ABB, pero la
ramificación del árbol es según los bits de las llaves. El
siguiente ejemplo muestra un árbol de búsqueda
digital (ABD), en donde el orden de inserción es B, A, C, D, E:
73
Skip lists
• Diccionarios con listas enlazadas: simple pero O(n) cuando el
diccionario posee n elementos.
• Se puede modificar la estructura de datos de la lista de modo
que cada nodo par se le agrega una referencia al nodo
ubicado dos posiciones más adelante en la lista.
• Modificando ligeramente el algoritmo de búsqueda, a lo
más
nodos son examinados en el peor caso.
74
Skip lists
• Esta idea se puede extender agregando una referencia cada
cuatro nodos: a lo más
nodos son examinados:
• El caso límite: cada 2i nodo posee una referencia al
nodo 2i posiciones más adelante en la lista.
• El número total de referencias se dobla, pero ahora a lo
más
nodos son examinados durante la búsqueda.
• La búsqueda en esta estructura de datos es básicamente una
búsqueda binaria, por lo que el tiempo de búsqueda en el
peor caso es O(log n).
75
Skip lists: problema
• Estructura de datos demasiado rígida para permitir
inserciones de manera eficiente.
• Solución: relajar levemente las condiciones.
• Se define un nodo de nivel k como aquel nodo que
posee k referencias.
• Se observa de la figura que, aproximadamente, la mitad de los
nodos son de nivel 1, que un cuarto de los nodos son de nivel
2, etc. En general, aproximadamente n/2i nodos son de nivel i.
76
Skip lists
• Cada vez que se inserta un nodo, se elige el nivel que tendrá
aleatoriamente en concordancia con la distribución de
probabilidad descrita.
• Por ejemplo, se puede lanzar una moneda al aire, y mientras
salga cara se aumenta el nivel del nodo a insertar en 1
(partiendo desde 1).
• Esta estructura de datos es denominada skip list.
• La siguiente figura muestra un ejemplo de una skip list:
77
Operaciones en Skip lists
• Búsqueda: buscar X, comienzar con referencia superior de la
cabecera. Realizar recorrido a través de este nivel (pasos
horizontales) hasta que el siguiente nodo sea mayor que X o
sea null. Cuando esto ocurra, se continúa con la búsqueda pero
un nivel más abajo (paso vertical). Cuando no se pueda bajar de
nivel, esto es, ya se está en el nivel inferior, entonces se realiza
una comparación final para saber si el elemento X está en la lista.
• Inserción: proceder como en búsqueda, manteniendo una marca
en los nodos donde se realizaron pasos verticales, hasta llegar al
nivel inferior. El nuevo elemento se inserta en la posición en
donde debiera haberse encontrado, se calcula aleatoriamente su
nivel y se actualizan las referencias de los nodos marcados
dependiendo del nivel del nuevo nodo de la lista.
78
ABB óptimos
• Probabilidades de acceso a los elementos no uniforme
• Dado n elementos en un árbol X1 < X2< … < Xn con
probabilidades de acceso conocidas p1, p2, … ,pn y
probabilidades de búsqueda infructuosa q1, q2, …, qn
• Cual es el árbol que minimiza el costo esperado de búsqueda
79
ABB óptimos (cont.)
• Ejemplo, para el árbol con 6 elementos
• El costo de búsqueda esperado es
C(q0,q6)=(2q0+2p1+4q1+4p2+4q2+3p3+4q3+4p4+4q4)+p5+(2q5+2p6+2q6)
=(q0+p1+q1+p2+q2+p3+q3+p4+q4+p5+q5+p6+q6)+
(1q0+1p1+3q1+3p2+3q2+2p3+3q3+3p4+3q4)+ (1q5+1p6+1q6)
=W(q0,q6)+C(q0,q4)+C(q5,q6)
80
ABB óptimos (cont)
• W(q0,q6)+C(q0,q4)+C(q5,q6) esto es, el costo del árbol completo es
igual al "peso" del árbol más los costos de los subárboles.
• Si la raíz es k: Ci,j = Wi,j + Ci,k-1 + Ck,j
81
Construcción de ABB óptimos
• Obviamente hay que conocer las probabilidades de antemano
• Si el árbol completo es óptimo, entonces los sub-árboles también
lo son, pero al revés no necesariamente es cierto, porque la
raíz k puede haberse escogido mal. Luego, para encontrar el
verdadero costo óptimo C_opti,j es necesario probar con todas las
maneras posibles de elegir la raíz k.
• C_opti,j = mini+1<=k<=j {Wi,j + C_opti,k-1 + C_optk,j}
• C_opti,i = 0 para todo i=0..n
• Note que el "peso" Wi,j no depende de la variable k.
• Si se calcula para todo con raiz k en forma recursiva (equivalente
a fuerza bruta) el orden es O(4n) (ver capitulo estructuras
elementales, árboles binarios).
82
Construcción de ABB óptimos
• Usando programación dinámica (tabulación):
for (i=0; i<=n; i++) {
C[i,i]=0; // subarboles de tamaño 0
W[i,i]=qi;
}
for (l=1; l<=n; l++)
for (i=0; i<=n-l; i++) {
j=i+l; W[i,j]=W[i,j-1]+pj+qj;
C[i,j]=mini+1<=k<=j {W[i,j]+C[i,k-1]+C[k,j]}
}
Tiempo: O(n3).
Una mejora: se define ri,j como el k que minimiza
mini+1<=k<=j {W[i,j]+C[i,k-1]+C[k,j]}.
Intuitivamente ri,j-1 <= ri,j <= ri+1,j, y como ri,j-1 y ri+1,j ya son conocidos al momento
de calcular ri,j, basta con calcular
minri,j-1 <= k <= ri+1,j {W[i,j]+C[i,k-1]+C[k,j]}.
Con esta mejora, se puede demostrar que el método demora O(n2) (Ejercicio:
demostrarlo).
83
Sply Trees
• Estructura que garantiza que una secuencia de M operaciones se
hace en O(M log N), alguna en particular puede tomar O(N)
• Cuando una secuencia de M operaciones toma O(M f(N)), se dice
que el costo amortizado en tiempo de cada operación es O(f(N))
• Idea básica: después que un nodo es accesado éste se "sube"
hasta la raíz del árbol a través de rotaciones al estilo AVL
• Si se hace con rotaciones simples puede pasar que algunos nodos
queden muy abajo y se puede demostrar que existe una
secuencia de M operación que tomen O(N) en promedio (poco
probable pero existe)
84
Estrategia
• La estrategia de "splaying" es similar a la idea de las rotaciones
simples.
• Si el nodo k es accesado, se realizaran rotaciones para llevarlo
hasta la raíz del árbol.
• Sea k un nodo distinto a la raíz del árbol que es accesado.
– Si el padre de k es la raíz del árbol, entonces se realiza una rotación simple
entre estos dos nodos.
– En caso contrario, el nodo k posee un nodo padre p y un nodo "abuelo" a.
• Para realizar las rotaciones “convenientes” se deben considerar
dos casos posibles (más los casos simétricos).
85
Caso 1
• El primer caso es una inserción zig-zag, en donde k es un hijo
derecho y p es un hijo izquierdo (o viceversa). En este caso, se
realiza una rotación doble estilo AVL
86
Caso 2
• El otro caso es una inseción zig-zig, en donde k y p son ambos
hijos izquierdo o derecho. En este caso, se realiza la
transformación indicada en la figura
87
Efectos del Splying
• El efecto del splaying es no sólo
de mover el nodo accesado a la
raíz, sino que sube todos los
nodos del camino desde la raíz
hasta el nodo accesado
aproximadamente a la mitad de
su profundidad anterior, a costa
que algunos pocos nodos bajen a
lo más dos niveles en el árbol.
• El siguiente ejemplo muestra
como queda el splay tree luego
de accesar al nodo d.
88
Ejemplo
• El primer paso es un zig-zag entre los nodos d, b y f.
89
Ejemplo
• El último paso es un zig-zig entre los nodos d, h y j.
90
Borrado en Sply trees
• Para borrar un elemento de un splay tree se puede proceder de
la siguiente forma:
– se realiza una búsqueda del nodo a eliminar, lo cual lo deja en la raíz del
árbol. Si ésta es eliminada, se obtienen dos subárboles Sizq y Sder.
– Se busca el elemento m mayor en Sizq, con lo cual dicho elemento pasa a
ser su nueva raíz,
– como m era el elemento mayor Sizq ya no tiene hijo derecho, por lo que se
cuelga Sder como subárbol derecho de Sizq, con lo que termina la operación
de eliminación.
• El análisis de los splay trees es complejo, porque debe considerar
la estructura cambiante del árbol en cada acceso realizado.
• Los splay trees son más fáciles de implementar que un AVL dado
que no hay que verificar una condición de balance.
91
Hashing
• Suponga que desea almacenar n números enteros, sabiendo de
antemano que dichos números se encuentran en un rango
conocido 0, ..., k-1.
• Para resolver este problema, basta con crear un arreglo de
valores booleanos de tamaño k y marcar con valor true los
casilleros del arreglo cuyo índice sea igual al valor de los
elementos a almacenar.
• Es fácil ver que con esta estructura de datos el costo de
búsqueda, inserción y eliminación es O(1).:
92
Problemas
• En muchos casos esto no es posible de implementar
• El valor de k puede ser muy grande, y por lo tanto no habría cupo
en memoria para almacenar el arreglo.
– Piense, por ejemplo, en todos los posibles nombres de personas.
– No sirve para guardar números reales
• Los datos a almacenar pueden ser pocos, con lo cual se estaría
desperdiciando espacio de memoria.
93
Solución
• Una manera de resolver estos
problemas es usando una función h,
denominada función de hash, que
transforme un elemento X,
perteneciente al universo de
elementos posibles, en un
valor h(X) en el rango [0, ..., m-1],
con m << k.
• En este caso, se marca el casillero cuyo
índice es h(X) para indicar que el
elemento X pertenece al conjunto de
elementos.
• Esta estructura de datos es conocida
como tabla de hashing.
94
La Función de hashing h(x)
• La función h debe ser de tipo pseudoaleatorio para distribuir las
llaves uniformemente dentro de la tabla, es decir:
– Pr( h(X) = z) = 1/m para todo z en [0, ..., m-1].
– La llave X se puede interpretar como un número entero, y las
funciones h(X) típicas son de la forma:
h(x) = (c ∙ x mod p) mod m
• donde c es una constante, p es un número primo y m es el
tamaño de la tabla de hashing. Distintos valores para estos
parámetros producen distintas funciones de hash.
• Problema de este nuevo enfoque: colisiones.
95
La paradoja del Cumpleaños
• ¿Cuál es el número n mínimo de personas que es necesario
reunir en una sala para que la probabilidad que dos de ella
tengan su cumpleaños en el mismo día sea mayor que 1/2?
• Sea dn la probabilidad que no haya coincidencia en dos fechas
de cumpleaños.
• Se tiene que:
• ¿Cuál es el mínimo n tal que dn < 1/2?
96
¿ Qué tan probables son las colisiones ?
•
•
•
•
Respuesta: n = 23 => dn = 0.4927.
Note que 23 es una "pequeña" fracción de 365.
Aun asi es posible tener colisiones con alta probabilidad.
Solución: existen dos grandes familias de métodos:
– Encadenamiento (usar estructuras dinámicas).
– Direccionamiento abierto (intentar con otra función de hash).
97
Encadenamiento
• La idea de este método es que todos los elementos que
caen en el mismo casillero se enlacen en una lista, en la
cual se realiza una búsqueda secuencial.
• Basta agregar siempre al comienzo
98
Análisis
• Se define para un conjunto con n elementos:
– Cn : costo esperado de búsqueda exitosa.
– C'n : costo esperado de búsqueda infructuosa.
–
: factor de carga de la tabla.
• Esto implica que el costo esperado de búsqueda sólo
depende del factor de carga α, y no del tamaño de la tabla.
99
Hashing con listas mezcladas
• En este caso no se usa área de rebalse, sino que los
elementos se almacenan en cualquier lugar libre del área
primaria.
• Ejemplo: h(X)= X mod 10
• 25 , 15, 48 se agregaron
en ese orden, 39 puede
haber venido antes,
entre medio o al final.
100
Eliminación
• Con listas separadas el algoritmo es simple, basta con
eliminar el elemento de la lista enlazada correspondiente.
• En el caso de las lista mezcladas, el algoritmo es más
complejo (ejercicio).
• Costos esperados para listas mezcladas :
101
Funciones de hashing para strings
static public int hash(String x,int y){...}
1.Sumar representaciones internas de caracteres
int s=0;
for(int i=0; i<x.length(); ++i)
s += x.charAt(i);
return s % y;
2.Evaluar polinomio, usando caracteres como coeficientes
int s=0, p=1;
for(int i=x.length()-1; i>=0; --i){
s+=x.charAt(i)*p; p*=128;
}
return s % y;
3. Con función predefinida de clase String
return x.hashCode() % y;
Ejemplos (y=100)
función rosa
suma
37
polinomio 69
hashCode 53
Rosa
5
5
57
rosaura
65
29
23
roma
31
1
31
amor
31
22
83
Hashing con direccionamiento abierto
• En general, esto puede ser visto como una sucesión de
funciones de hash {h0(X), h1(X), ...}.
– Primero se intenta con tabla[h0(X)], si el casillero está ocupado se prueba
con tabla[h1(X)], y así sucesivamente.
• Linear probing: Es el método más simple de direccionamiento
abierto, en donde las funciones de hash se definen como:
104
Búsqueda con linear probing
int indice(String x,String[]y,int n){
int i = hash(x,n);
while( y[i] != null ){
if( y[i].equals(x) ) return i;
i = (i + 1) % n;
}
return –1;
}
 Costo esperado
Análisis
Cuando la tabla de hashing está muy llena, este método resulta ser muy lento.
α
Cn
Cn '
.6
1.75
3.63
.7
2.17
6.06
.8
3
13
.9
5.50
50.50
.99
50.50
5,000.50
.999
500.50
500,000.50
A medida que la tabla se va llenando, se observa que empiezan a aparecer
clusters de casilleros ocupados consecutivos:
¿Construcción del arreglo?
//contar número de elementos
BufferedReader A=new BufferedReader(...);
int n=0;
while(A.readLine()!=null)++n;
//arreglo 10% mas grande (con valores null)
String[]a=new String[(int)(1.1*n+0.9)];
//llenar arreglo usando función de hashing
A=new BufferedReader(...);
for(int j=1; j<=n; ++j){
String linea = A.readLine();
int i=hash(linea, a.length);
while(a[i]!=null && !a[i].equals(linea))
i=(i+1)%a.length;
a[i]=linea;
}