PDF de programación - Tablas Hash y árboles binarios

Tablas Hash y árboles
binarios

Algoritmos

 Tablas hash
 Árboles Binarios
 Árboles Balanceados

Tablas Hash

Introducción

 Las tablas hash son estructuras tipo vector
que ayudan a asociar claves con valores o
datos
Estructura preferida para la implementación de

diccionarios
diccionarios

Proveen un tiempo constante de búsqueda (O(1))

 Concepto clave:

No buscar directamente el valor deseado, sino a
través de una función de dispersión h(x) localizar
la posición del valor buscado

Ejemplo

 Considere que nos dan un conjunto de palabras y
nos piden contar el numero de veces que parece
cada palabra
Se requiere crear un diccionario que represente a cada

palabra válida y a su ves, nos indique en número de
instancias por palabra
instancias por palabra

Tabla Hash

 Una tabla hash se construye con tres

elementos básicos:
Un vector capaz de almacenar “m” elementos
Función de dispersión que permita a partir de los
Función de dispersión que permita a partir de los

datos (llamados clave) obtener el índice donde
estará el dato en el arreglo

Una función de resolución de colisiones

Tablas Hash

Tablas Hash

 En el diseño de una tabla hash, es de gran

importancia la elección de la función de
dispersión
Función sencilla para una evaluación rápida
Distribuir uniformemente en el espacio de
Distribuir uniformemente en el espacio de
almacenamiento

Evitar (si es posible) la aparición de sinónimos o

colisiones

Para dos claves similares, generar posiciones

distantes

Tablas Hash

 Retornando al ejemplo de conteo de palabras

¿como se podría definir una tabla hash para la

búsqueda de una palabra en un diccionario?

 Idea
 Idea

Transformar una palabra en un valor numérico

entre [0, …, m) donde m representa el número de
entradas en el arreglo que almacenará el dato

Tablas Hash

 Solución

Dado que se requiere construir una función que

para dos valores similares, den resultados
alejados entre si, se puede usar la función de
Bernstain
Bernstain

h = 33 * h + p[i]

Tablas Hash

 Ejemplo del conteo de cadenas:

Un string se puede interpretar como una
secuencia de valores ASCII entre 0 – 255
Un string sería un número en base 255
Un string sería un número en base 255
Por ejemplo, la clave “pt” equivale a la entrada

 112 * 33 + 116

Tipos de Tablas Hash

 Existen diferentes tipos de tablas hash:

Tablas de dirección directa: cuando el universo de objetos

U es relativamente pequeño
Elemento con llave k  almacenado en el slot k

Tipos de Tablas Hash

 … tipos de tablas hash:

Tablas de dirección indirecta: Cuando el universo de

objetos U es muy grande, se crea un vector T de
dimensión m, tal que |U| > m
Elemento con llave k  almacenado en el slot h(k)
Elemento con llave k  almacenado en el slot h(k)
|U| > m  $ ki, kj ˛ U: h(ki) = h(kj)  COLISIONES

Tipos de Tablas Hash

 Solución de colisiones a través de encadenamiento

Funciones Hash

 Una función hash h: U  {0, 1, …, m-1}

(considerando un arreglo de dimensión m)
debe de cumplir algunas condiciones:

Cada llave ki debe tener la misma probabilidad de

ser asignada a cualquiera de los “m” slots

 NOTA: esta condición es difícil de garantizar

Funciones Hash

 Método de división:

h(k) = k mod m
P.E. si m = 12 y k = 100  h(k) = 4

 Si se utiliza el método de la división, se debe
 Si se utiliza el método de la división, se debe

evitar que “m” sea una potencia de 2
Se recomienda utilizar un número primo “no

cercano” a una potencia de 2

Funciones Hash

 Método de Multiplicación

Se multiplica la clave k por A, 0 < A < 1 y se

extrae la parte fraccionaria de k*A
Se multiplica el resultado por el número de
Se multiplica el resultado por el número de
entradas de la tabla y se toma el piso o techo

h(k) = int(m*(k*A – int(k*A)))

 Para este método, no se imponen
restricciones sobre el valor de “m”

Árboles Binarios

Introducción

 Un árbol binario es una estructura tipo árbol donde

cada nodo tiene los apuntadores:
Left: árbol izquierdo
Rigth: árbol derecho
p: padre
p: padre

Introducción

 Regla general para un árbol binario

Sea “x” un nodo en un árbol binario

 Si “y” es un nodo en el subárbol izquierdo de x  key[y]

£ key[x]
Si “y” es un nodo en el subárbol derecho de x  key[x]
 Si “y” es un nodo en el subárbol derecho de x  key[x]
£ key[y]

Recorrido de un Árbol Binario

 Para recorrer un árbol binario T, se puede utilizar

una estrategia “inorder”, donde el llamado a la
función es: INORDER-TREE-WALK(root[T])

¿Recorrido del árbol?

Búsqueda en un Árbol Binario

 Se puede implementar una
versión recursiva o iterativa:
Entrada: x (puntero a un
nodo del árbol) – para el
llamado inicial, es la raiz del
árbol
árbol

Salida: puntero al nodo que

contiene la llave

 Complejidad de la

búsqueda:

O(h)

h: altura del árbol

Construcción de un Árbol Binario

 Existen dos operaciones básicas en la

construcción de un árbol binario:
Insertar
Borrar
Borrar

 Ambas reglas deben de mantener la reglas

generales de los árboles binarios

Inserción

Borrar

Borrar