Diccionarios
• El TDA diccionario
• Búsqueda binaria
• Arboles de búsqueda binaria
1
EL TDA Diccionario
• Un diccionario es un modelo abstracto de una base de datos
– Como una lista de prioridad, un diccionario almacena pares de llaves-elementos
– La principal operación soportada por un diccionario es la búsqueda por la llave
• métodos contenedor simple:
size()
isEmpty()
elements()
• métodos de consulta:
findElement(k)
findAllElements(k)
• métodos de actualización: insertItem(k, e)
removeElement(k)
removeAllElements(k)
• elemento especial
NO_EXISTE_CLAVE, retornado por una búsqueda no exitosa
2
Búsqueda Binaria
• Estrecha el rango de búsqueda en etapas
• findElement(22)
3
Pseudocódigo para Búsqueda
Binaria
Algorithm BusquedaBinaria(S, k, low, high)
if low > high then
return NO_EXISTE_KEY
else
mid  (low+high) / 2
if k = key(mid) then
return key(mid)
else if k < key(mid) then
return BusquedaBinaria(S, k, low, mid-1)
else
return BusquedaBinaria(S, k, mid+1, high)
2
4
5
7
8
9
12
low
2
14
17
19
22
27
28
33
4
5
7
8
9
12
14
4
5
7
8
9
12
14
37
high
mid
17
19
22
low
2
25
17
25
27
28
33
high
mid
19
low mid
22
25
37
27
28
33
37
4
Tiempo de ejecución de la Búsqueda
Binaria
• El rango de los elementos candidatos a buscar es la mitad después de
cada comparación
En la implementación basada en array el acceso por índice toma un
tiempo O(1), por tanto la búsqueda binaria corre en tiempo O(log n)
5
Arboles binarios de búsqueda
• Un árbol de búsqueda binaria es un árbol T tal que
– cada nodo interno almacena un elemento (k, e) de un diccionario.
– Las llaves almacenadas en los nodos en el subárbol izquierdo de v son
menores que o iguales a k.
– Las llaves almacenadas en los nodos en el subárbol derecho de v son
mayores que o iguales a k.
– Los nodos externos no tienen elementos pero sirven de marcadores.
6
Búsqueda
• Un árbol de búsqueda binaria T es un árbol de decisión, donde la
pregunta realizadad en un nodo interno v es si la llave busacada k es
menor que, igual a, o mayor que la llave almacenada en v.
• Pseudocodigo: Algorithmo BuscaArbol(k, v):
Input: Una llave de búsqueda k y un nodo v de un árbol binario de
búsqueda T.
Ouput: Un nodo w del subárbol T(v) de T con raíz v.
if v es un nodo externo then
return v
if k = key(v) then
return v
else if k < key(v) then
return BuscaArbol(k, T.leftChild(v))
else { k > key(v) }
return BuscaArbol(k, T.rightChild(v))
7
Ejemplo de Búsqueda I
hallarElemento(76)
76>44
76<88
76>65
76<82
8
Ejemplo de Búsqueda II
Búsqueda sin exito hallarElement(25)
25<44
25>17
25<32
25<28
Nodo
hoja
9
Inserción
10
Inserción
11
Eliminación
12
Eliminación
13
Complejidad Temporal
• En cada nodo O(1)
• Tiempo de ejecución de cada operación O(h), donde h es la altura del
árbol
• La altura del árbol binario de búsqueda es n en el peor de los casos
• Para obtener un buen tiempo de ejecución, es necesario
mantener el árbol balanceado, i.e., con altura O(logn).
14
Descargar

Diccionarios