Download CC3001-7-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.
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, puesto ("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, y que es consistente con las
comparaciones realizadas entre los elementos. Los
arcos del árbol corresponden a los resultados de las
comparaciones, que en este caso pueden ser mayor
que o menor que el elemento buscado, 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.
¿árbol binario de búsqueda o árbol 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
F
A
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 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;
}
AVL-Trees
(Adelson-Velskii & Landis, 1962)
In normal search trees, the complexity of find, insert
and delete operations in search trees is in the worst
case: (n).
Can be better! Idea: Balanced trees.
Definition: An AVL-tree is a binary search tree such that
for each sub-tree T ' = < L, x, R >
| h(L) - h(R) |  1 holds
(balanced sub-trees is a characteristic of AVL-trees).
The balance factor or height is often annotated at each
node h(.)+1.
21
|Height(I) – hight(D)| < = 1
This is an AVL tree
22
This is NOT an AVL tree (node * does not hold the required condition)
23
Goals
1. How can the AVL-characteristics be kept when
inserting and deleting nodes?
2. We will see that for AVL-trees the complexity of the
operations is in the worst case
= O(height of the AVL-tree)
= O(log n)
24
Preservation of the AVLcharacteristics
After inserting and deleting nodes from a tree we must
procure that new tree preserves the characteristics
of an AVL-tree:
Re-balancing.
How ?: simple and double rotations
25
Only 2 cases (an their mirrors)
• Let’s analyze the case of insertion
– The new element is inserted at the right (left) subtree of the right (left) child which was already
higher than the left (right) sub-tree by 1
– The new element is inserted at the left (right) subtree of the right (left) child which was already
higher than the left (right) sub-tree by 1
26
Rotation (for the case when the right sub-tree grows
too high after an insertion)
Is transformed into
27
Double rotation (for the case that the right sub-tree
grows too high after an insertion at its left sub-tree)
Double rotation
Is transformed into
28
b
First rotation
a
x
W
a
c
new
y
Z
Second rotation
b
W
c
y
Z
29
Re-balancing after insertion:
After an insertion the tree might be still balanced or:
theorem: After an insertion we need only one rotation
of double-rotation at the first node that got
unbalanced * in order to re-establish the balance
properties of the AVL tree.
(* : on the way from the inserted node to the root).
Because: after a rotation or double rotation the
resulting tree will have the original size of the tree!
30
The same applies for deleting
• Only 2 cases (an their mirrors)
– The element is deleted at the right (left) sub-tree of
which was already smaller than the left (right) subtree by 1
– The new element is inserted at the left (right) subtree of the right (left) child which was already
higher that the left (right) sub-tree by 1
31
The cases
Deleted node
1
1
1
32
Re-balancing after deleting:
After deleting a node the tree might be still balanced or:
Theorem: after deleting we can restore the AVL balance
properties of the sub-tree having as root the first* node that
got unbalanced with just only one simple rotation or a double
rotation.
(* : on the way from the deleted note to the root).
However: the height of the resulting sub-tree might be
shortened by 1, this means more rotations might be
(recursively) necessary at the parent nodes, which can affect
up to the root of the entire tree.
33
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 is necessary to have an operation that returns the parent
of a certain node (for example, by adding a pointer to the
parent).
34
Complexity analysis– worst case
Be h the height of the AVL-tree.
Searching: as in the normal binary search tree O(h).
Insert: the insertion is the same as the binary search tree (O(h))
but we must add the cost of one simple or double rotation,
which is constant : also O(h).
delete: delete as in the binary search tree(O(h)) but we must add
the cost of (possibly) one rotation at each node on the way
from the deleted node to the root, which is at most the height
of the tree: O(h).
All operations are O(h).
35
Calculating the height of an AVL tree
Be N(h) the minimal number of nodes
In an AVL-tree having height h.
Principle of construction
0
N(0)=1, N(1)=2,
N(h) = 1 + N(h-1) + N(h-2) for h  2.
N(3)=4, N(4)=7
remember: Fibonacci-numbers
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
By calculating we can state:
N(h) = fibo(h+3) - 1
1
2 3
36
Be n the number of nodes of an AVL-tree of height h. Then it holds
that:
n  N(h) ,
Remember fn =(1 /sqrt(5)) (Ф1n - Ф2n)
with Ф1= (1+ sqrt(5))/2 ≈ 1.618
Ф2= (1- sqrt(5))/2 ≈ 0.618
we can now write
n  fibo(h+3)-1 = (Ф1 h+3 – Ф2h+3 ) / sqrt(5) – 1
 (Ф1 h+3/sqrt(5)) – 3/2,
thus
h+3+log Ф1(1/sqrt(5))  log Ф1(n+3/2),
thus there is a constant c with
h  log Ф1(n) + c
= log Ф1(2) • log2(n) + c
= 1.44… • log2(n) + c = O(log n).
37
Arboles B (External Search)
• The algorithms we have seen so far are good when
all data are stored in primary storage device (RAM).
Its access is fast(er)
• Big data sets are frequently stored in secondary
storage devices (hard disk). Slow(er) access (about
100-1000 times slower)
Access: always to a complete block (page) of data
(4096 bytes), which is stored in the RAM
For efficiency: keep the number of accesses to the
pages low!
38
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.
39
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
40
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:
41
Ejemplos
42
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
43
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.
44
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.
45
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))
46
For external search: a variant of search trees:
1 node = 1 page
Multiple way search trees!
47
Multiple way-search trees
Definición: An empty tree is a multiple way search tree with an
empty set of keys {} .
Be T0, ..., Tn multiple way-search trees with keys taken from a
common key set S, and be k1,...,kn a sequence of keys with k1 <
...< kn. Then is the sequence:
T0 k1 T1 k2 T2 k3 .... kn Tn
a multiple way-search trees only when:
• for all keys x from T0 x < k1
• for i=1,...,n-1, for all keys x in Ti, ki < x < ki+1
• for all keys x from Tn kn < x
48
B-Tree
Definition
A B-Tree of Order m is a multiple way tree with the following
characteristics
• 1  #(keys in the root)  2m
and
m  #(keys in the nodes)  2m
for all other nodes.
• All paths from the root to a leaf are equally long.
• Each internal node (not leaf) which has s keys has exactly s+1
children.
• 2-3 Trees is a particular case for m=1
49
Example: a B-tree of order 2:
50
Assessment of B-trees
The minimal possible number of nodes in a B-tree of order m
and height h:
• Number of nodes in each sub-tree
1 + (m+1) + (m+1)2 + .... + (m+1)h-1
= ( (m+1)h – 1) / m.
The root of the minimal tree has only one key and two children,
all other nodes have m keys.
Altogether: number of keys n in a B-tree of height h:
n  2 (m+1)h – 1
Thus the following holds for each B-tree of height h with n keys:
h  logm+1 ((n+1)/2) .
51
Example
The following holds for each B-tree of height h with n keys:
h  logm+1 ((n+1)/2).
Example: for
• Page size: 1 KByte and
• each entry plus pointer: 8 bytes,
If we chose m=63, and for an ammount of data of
n= 1 000 000
We have
h  log 64 500 000.5 < 4 and with that hmax = 3.
52
Key searching algorithm in a B-tree
Algorithm search(r, x)
//search for key x in the tree having as root node r;
//global variable p = pointer to last node visited
in r, search for the first key y >= x or until no more keys
if y == x {stop search, p = r, found}
else
if r a leaf {stop search, p = r, not found}
else
if not past last key search(pointer to node before y, x)
else search(last pointer, x)
53
Inserting and deleting of keys
Algorithm insert (r, x)
//insert key x in the tree having root r
search for x in tree having root r;
if x was not found
{ be p the leaf where the search stopped;
insert x in the right position;
if p now has 2m+1 keys
{overflow(p)}
}
54
Algorithm Split (1)
Algorithm
overflow (p) = split (p)
Algorithm split (p)
first case: p has a parent q.
Divide the overflowed node. The
key of the middle goes to the
parent.
remark: the splitting may go up
until the root, in which case
the height of the tree is
incremented by one.
55
Algorithm Split (2)
Algorithm split (p)
second case: p is the
root.
Divide overflowed
node. Open a new
level above
containing a new
root with the key of
the middle (root has
one key).
56
Algorithm delete (r,x)
//delete 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)} } }
57
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')}
58
Algorithm balance (p, p')
// balance node p with its neighbor p'
(s > m , r = (m+s)/2 -m )
59
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^}
60
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.
61
Example:
B-Tree of
order 2 (m = 2)
62
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)).
63
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).
64
Remark: use of storage memory
Over 50%
reason: the condition:
1/2•k  #(keys in the node)  k
For nodes  root
(k=2m)
65