1

Diccionarios• El TDA diccionario

• Búsqueda binaria

• Arboles de búsqueda binaria

2

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 especialNO_EXISTE_CLAVE, retornado por una búsqueda no

exitosa

3

Búsqueda Binaria• Estrecha el rango de búsqueda en etapas

• findElement(22)

4

Pseudocódigo para Búsqueda Binaria

Algorithm BusquedaBinaria(S, k, low, high)if low > high then

return NO_EXISTE_KEYelse mid (low+high) / 2

if k = key(mid) thenreturn key(mid)

else if k < key(mid) thenreturn BusquedaBinaria(S, k, low, mid-1)

else return BusquedaBinaria(S, k, mid+1, high)2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

low high mid

high midlow

low mid

5

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)

6

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.

7

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))

8

Ejemplo de Búsqueda I

hallarElemento(76)76>44

76<88

76>65

76<82

9

Ejemplo de Búsqueda II

Búsqueda sin exito hallarElement(25)25<44

25>17

25<32

25<28

Nodo hoja

10

Inserción

11

Inserción

12

Eliminación

13

Eliminación

14

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).