Hash – Tablas de dispersión

Posted: Diciembre 27th, 2008 | Author: | Filed under: Estructuras de datos, Software, TAD | Tags: , , , , , | Comentarios desactivados en Hash – Tablas de dispersión

Es común al crear estructuras de datos y luego trabajar sobre las mismas, tener la necesidad de realizar búsquedas  en forma más frecuente que la necesidad de realizar inserciones. Por ejemplo si tenemos una lista de personas podríamos querer saber si cierta persona está ingresada, o saber información acerca de la misma. Para estos casos en que queremos realizar consultas sobre la estructura de datos puede ser útil trabajar con una estructura de datos que permita realizar búsquedas rápidas (de orden pequeño).

La estructura que vamos a ver es la Tabla de dispersión o Hash, la cual nos permite acceder a una posición dentro de la misma en orden 1, (O(1) caso promedio), realizando una cantidad fija de operaciones. De esta forma nos aseguramos de llegar a donde deberíamos encontrar la información en forma rápida sin importar la cantidad de elementos que tengamos en la estructura.

Un Hash no es más que un arreglo, en el cual podemos usar dos técnicas de ordenamiento interno. Este ordenamiento define donde colocar un elemento al insertar, pudiendo utilizarse dispersion abierta o dispersión cerrada.

Supongamos que tenemos el siguiente Hash:

En principio no es mas que un arreglo, pero crearemos un puntero en cada celda, de forma que podamos tener cualquier tipo de información guardad dentro de las mismas.

typedef struct tablahash{
int totalDisp;
nodoHash* hash[LARGOHASH+1];
};

Dijimos que el hash nos permite acceder en forma rápida a una de las posiciones dentro del mismo, esto se realiza mediante una función de dispersión que dada cierta entrada o valor, nos devuelve el valor dentro del hash donde debemos buscar la información que nos interesa.

Por ejemplo, si tenemos la lista de personas ingresadas por cédula, y le pasamos el numero de cédula 123456789 la función de dispersión nos devolverá la posición X dentro del hash donde debemos buscar la información de esa persona. Una función de dispersión básica pero útil suele ser sumar los valores ASCII de los caracteres y obtener el resto de dividir entre el largo del Hash, ya que no podemos obtener posiciones fuera del Hash mismo.

Un ejemplo de funcìón de dispersión sería el siguiente:

int calcularClaveInsertar(char const* id) {
int i, disp, length;
disp = 0;
length = strlen(id);

for(i=0; i<length; i++)
disp += id[i];
disp = disp % LARGOHASH;

return disp;
}

Esta función recibe un string y nos devuelve la posición correspondiente al mismo dentro del Hash de largo LARGOHASH.

Ya se habran dado cuenta que podemos tener problemas, que pasa si para dos cédulas diferentes tenemos el mismo resultados de dispersión? Y que sucede si tenemos muchos elementos, más de las posiciones disponibles dentro del hash? Estos casos son llamados “colisiones” ya que la información intenta ocupar el mismo lugar de memoria o posición dentro del hash. Para estos casos es que tenemos que analizar los dos tipos de dispersión posible, abierta y cerrada.

En el caso de la dispersión abierta lo que haremos al tener una colisión será simplemente tener una lista encadenada en cada nodo, por lo que iremos ampliando la lista a medida que tenemos colisiones. Si por ejemplo tenemo el hash de largo 10, e insertamos las cadenas  “hola” (104+111+108+97 % 10 = 0), “que” (113+117+101 % 10 = 1), “tal” (116+97+108 % 10 = 1), “hash” (104+97+115+104 % 10 = 0) tendríamos un resultado como el siguiente:

En las posiciones 0 y 1 tuvimos colisiones por lo que tenemos dos listas de dos elementos en cada una. Estos nos lleva a ver que en el peor caso de un hash de dispersión abierta tendremos una única lista de elementos en una sola posición, con lo que nuestro hash será simplemente una lista y no nos será de mucha utilidad.

Por esta razón debemos tomar algunas precauciones al utilizar esta estructura de datos, debemos utilizar una función de dispersión adecuada, es decir que nos devuelva valores lo más distribuidos posibles, debemos utilizar un tamaño de hash mayor a la cantidad de elementos que tendremos o que suponemos llegaremos a tener, y es una buena práctica utilizar un número primo en el largo del hash de forma que nos tengamos muchas colisiones al dividir sobre el largo del hash.

El segundo caso, la dispersión cerrada, no permite la creación de listas, pudiendo haber un solo elemento por cada nodo del hash. Para resolver las colisiones se utilizan funciones de redispersión que permiten buscar otra posición dipsonible para el elemento.

Para las funciones de redispersión tenemos la posibilidad de realizar una función lineal, que al encontrar una colisión sume 1 a la posición encontrada, tratando de encontrar una celda libre a continuación. Por ejemplo si tuviéramos el caso anterior, lo que haríamos hubiera sido insertar la palabra “hola” en la posición 0, luego “que” en la posición 1, cuando vamos a insertar “tal” nos encontramos con la posición 1 ya ocupada, por lo que sumamos 1 y lo insertamos en la posición 2. Cuando vamos a insertar “hash” encontramos la posición 0 ocupada, pasamos a la 1 y lo mismo, sumamos 1 nuevamente y la 2 también esta ocupada por lo que pasamos a la 3 que sí esta libre e insertamos ahí. 

Cuando vamos a buscar un elemento al hash caculamos la función de dispersión, por ejemplo para la palabra “tal”, obtenemos el valor 1, vamos a esa posición y no lo encontramos. Entonces vamos sumando 1 hasta encontrarlo o que la celda sea vacía.

El problema sucede cuando eliminamos un elemento y “cortamos” esta cadena, de forma que no podemos seguir este procedimiento. Por ejemplo supongamos que eliminamos la palabra “tal”, luego queremos saber si “hash” pertenece, para lo cual calculamos la dispersión, obtenemos 0, comenzamos a avanzar sumando 1, pasamos a la posición 1, luego a la 2 y llegamos a una celda vacía. No podemos saber que “hash” está en la próxima posición, ya que la celda vacía indica que se termino la cadena. Podríamos buscar una solución alternativa, por ejemplo marcar las casillas cuando borramos con un valor especial de forma que cuando buscamos y encontramos una de estas casillas sigamos avanzando sin detenernos. Así pasaríamos de la posición 2 a la 3 y econtraríamos “hash”.

El problema con la dispersión cerrada lineal es que comenzamos a agrupar los elementos, de forma que terminamos nuevamente con una lista continua dentro del hash y terminamos trabajando como si se tratara de una lista, perdiendo la eficiencia de acceso rápido en el caso promedio.

Tenemos la posibilidad de modificar la función de redispersión, pasando de una lineal a una cuadrática, la cual nos permite dar “saltos” dentro del hash cuando tenemos colisiones. En lugar de sumar 1 al encontrar una colisión sumamos i^2, de esta forma sumamos 0, 1, 4, 9… evitando crear secuencias continuas en un principio. El problema en el caso de la redispersión cuadrática y de que el tamaño del hash es limitado, es que volvemos a caer sobre las mismas posiciones luego de varios saltos, por lo que no utilizamos todo el espacio disponible.

Con la redispersión cuadrática podemos utilizar hasta la mitad del tamaño del hash (si el largo del mismo es de tamaño primo). Es importante realizar un conteo de los elementos y en caso de que el hash este siendo llenado debemos realizar una reestructuración del hash, creando uno nuevo de mayor tamaño primo, por ejemplo un primo cercano al doble, e insertando los elementos del hash anterior en este nuevo hash. Esta operación es bastante costosa, aunque si se tiene cuidado en la elección del tamaño del hash según las características del problema no debería ser una operación frecuente.

Vemos un ejemplo del código de un hash con dispersión abierta. Definimos la estructura de datos como un arreglo con punteros:

// Nodo de un elemento en el hash
typedef struct nodoEtq {
char* idDisposivo;
nodoEtq* sig;
};

// Nodo del hash
typedef struct nodoHash {
nodoEtq* disp;
};

typedef struct tablahash {
int totalDisp;
nodoHash* hash[LARGOHASH+1];
};

Necesitaremos inicializar el hash, ya que las posiciones del arreglo son punteros.

// Inicializa todas las posiciones del hash
void inicializarHash (nodoHash** hash) {
int i;

for (i = 0; i <= LARGOHASH; i++)
hash[i] = NULL;

return;
}

tablahash * hash = new tablahash;
inicializarHash(hash->hash);
hash->totalDisp = 0;

Luego necesitaremos la función de dispersión y una función auxiliar para saber si una celda del hash es vacía:

// Calcula la clave a usar para insertar
int calcularClaveInsertar(char const* id) {
int i, disp, length;
disp = 0;
length = strlen(id);

for(i=0; i<length; i++)
disp += id[i];

disp = disp % LARGOHASH;
return disp;
}

// Celda vacia del hash
bool esVaciaCeldaHash(nodoHash** hash, int disp) {
return hash[disp] == NULL;
}

La función para insertar elementos en el Hash:

// Inserta en el hash un identificador
nodoEtq* insertarHash(nodoHash** hash, char* id) {
int disp;
nodoEtq* nodoEtiqueta = new nodoEtq;
nodoHash* nodoH = new nodoHash;
char* idDisp = new char[strlen(id)+1];

nodoEtiqueta->idDisposivo = idDisp;
strcpy(nodoEtiqueta->idDisposivo,id);

disp = calcularClaveInsertar(id);

if (hash[disp] == NULL) {
nodoEtiqueta->sig = NULL;
} else {
nodoEtiqueta->sig = hash[disp]->disp;
}

nodoH->disp = nodoEtiqueta;
hash[disp] = nodoH;

return nodoEtiqueta;
}

// Inovación a la insersión
// Creamos un nuevo nodo, insertamos el char* idD e incrementamos la cantidad de elementos.
nodoEtq* nuevoNodo = new nodoEtq;
nuevoNodo = insertarHash(hash->hash, idD);
gl->totalDisp++;

Como dijimos al comenzar, la idea del hash es buscar elementos dentro del mismo en forma rápida, vemos una función para realizar las búsquedas:

// Indica si pertenece un identificador al hash
nodoEtq* perteneceHash(nodoHash** hash, char const* id) {
nodoEtq* nodo;
int pos;

pos = calcularClaveInsertar(id);
if (esVaciaCeldaHash(hash, pos)) {
return NULL;
} else {
nodo = hash[pos]->disp;
while ((nodo != NULL) && (strcmp(nodo->idDisposivo,id) != 0)) {
nodo = nodo->sig;
}

if (nodo != NULL) {
return nodo;
} else {
return NULL;
}

}
}

Al utilizar dispersión abierta tenemos una lista en cada celda, por lo que luego de calcular la dispersión debemos recorrer la lista de ese nodo en busca del elemento o el fin de lista. En caso de encontrar el nodo lo devolvemos, o en caso contrario devolvemos NULL.

Por último, una función para desplegar el hash, puede ser útil para realizar pruebas o ver el estado del hash en un momento dado:

// Función auxiliar para desplegar la lista de cada nodo
void desplegarHashLista(nodoHash* lista) {
nodoHash* recorrer;

recorrer = lista;
while (recorrer->disp != NULL) {
printf(“Valor: %s,”, recorrer->disp->idDisposivo);
recorrer->disp = recorrer->disp->sig;
}

return;
}

// Despliega el hash
void desplegarHash (nodoHash** hash) {
int i;

for (i = 0; i < LARGOHASH; i++) {
if (hash[i] == NULL) {
printf(“NULL “);
} else {
desplegarHashLista(hash[i]);
}
}

return;
}


AVL (Adel’son-Vel’skii Landis) – Árboles binarios Balanceados

Posted: Diciembre 7th, 2008 | Author: | Filed under: Algoritmos, C/C++, Estructuras de datos, Software, TAD | Tags: , , , , , , , | Comentarios desactivados en AVL (Adel’son-Vel’skii Landis) – Árboles binarios Balanceados

Los árboles binarios tienen la utilidad de ordenar la información, separando el conjunto en dos posibilidades, izquierda y derecha, por lo que reducimos el conjunto de búsqueda a la mitad en cada paso. Esto nos lleva a que en un árbol balanceado (si tiene las ramas izquierda y derecha del mismo tamaño +1 o -1) tenemos una altura de Log(n), lo cual hace que las búsquedas sean “rápidas”. El problema que tienen los árboles comunes es que pueden degenerar rapidamente en una lista, por ejemplo si insertamos el elemento 1 como raíz, y luego insertamos los números 2, 3, 4, 5… Tendremos inserciones siempre a la derecha, lo que nos lleva a tener una estructura de lista perdiendo la utilidad de dividir a la mitad en cada paso. Para solucionar esto utilizaremos los AVL, o árboles binarios balanceados, que nos permiten después de cada inserción rotar los nodos de forma de que quede ordenado.

AVL - NO AVL

Los AVL utilizan el factor de balanceo para decidir si es necesario rotar una rama luego de insertar. Este FB (factor de balanceo) nos dice la diferencia de alturas entre el subárbol izquierdo y el derecho, por lo que restando las alturas de los mismos obtenemos este valor.

FB = Altura Subarbol Izquierdo – Altura Subarbol Derecho

En el primer ejemplo del caso anterior tenemos que la primer rama izquierda tiene un desbalanceo, ya que la altura de su subrama izquierda es 2, y la de la derecha es 0, lo que nos da: FB = 2. Tenemos desbalance. En el segundo caso el FB no supera el valor 1, por lo que no hay necesidad de rotar.

Las rotaciones se dividen en dos casos, simples o dobles. Las simples se conocen como LL si son de la rama izquierda, y RR si son de la rama derecha. Las rotaciones dobles son LR o RL, ya que son combinadas y más complejas como sugiere su nombre. Vemos primero las rotaciones simples.

En el caso simple LL, tomemos un nodo 1 que quedará con FB = 2, insertamos un nodo en el subárbol izquierdo de su hijo izquierdo, con lo que tenemos una inserción en la izquierda-izquierda (por eso Left Left). Para balancear el árbol deberemos tomar el hijo izquierdo de 1 (llamémoslo 2), y ponerlo como padre de 1, el hijo derecho de 1 queda en su lugar, el hijo izquierdo de 2 queda en su lugar y el hijo de derecho de 2 debe ir como hijo izquierdo de 1, ya que en su lugar tendremos a 1. Veamos un dibujo:

Lo que hacemos es mover el subárbol que queda con un largo excesivo hacia arriba, sacando al padre para hacer lugar, teniendo cuidado eso si de mantener la relación de mayor menor, lo cual hacemos dejando los subárboles izquierdos de 2 y derecho de 1 en sus lugares (ya que son menores que todos los demas, y mayores respectivamente), y moviendo de lugar el subárbol derecho de 2 hacia el izquierdo de 1. Esto lo podemos hacer ya que este subárbol contiene elementos mayores que los de 2, pero menores que 1.

En el caso de la rotación simple RR sucede lo mismo que acabamos de ver, solo que en el caso de insertar a la derecha del hijo derecho:

Hemos visto los dos casos simples, donde insertamos en la rama menor que todos o mayor que todos. Veremos ahora que sucede cuando insertamos en el hijo derecho del subárbol izquierdo, o en el izquierdo del derecho, es decir cruzado.

En este caso lo que haremos será aplicar dos rotaciones simples, con lo cual haremos que el nodo insertado “suba” acortando la altura del árbol. Noten que el nodo que tiene FB = 2 es el nodo 1, y no el nodo 2 que es donde insertamos (en su subárbol derecho). Por lo cual deberemos modificar la altura de sus hijos para reducir el FB a 1.

El proceso que seguiremos será el siguiente, tomamos el nodo en la rama donde se generó el desbalance, en este caso el 2, como la inserción es en el fijo derecho de 2, tomamos este nodo (el 3), y lo guardamos como la nueva raiz. Guardamos los dos hijos del 3 (ya que en realidad el árbol puede ser más amplio, y haber nodos hacia “abajo”) y ponemos como su hijo izquierdo a 2, y su hijo derecho a 1. Así sabemos que el orden se mantiene, 3, estaba a la derecha de 2, por lo que es mayor, y a la izquierda de 1, por lo que es menor. Colocado 3 en el lugar de 1, tomamos los dos posibles hijos de 3 que guardamos y los colocamos respectivamente como hijo derecho de 2 al hijo izquierdo, y como hijo izquierdo de 1 al derecho de 3. Otra vez manteniendo el orden.

Veamos un ejemplo gráfico:

En resumen la idea es, cuando detectamos que un nodo tiene FB = 2 (recuerden, en valor absoluto), entonces de acuerdo a sea positivo o negativo tomamos la rama izquierda o la derecha, subimos el nodo correspondiente y reasignamos con cuidado los hijos para no perder el orden. Las operaciones LR y RL, como las LL y RR son simétricas, por lo que el código será idéntico cambiando el hijo seleccionado. Como mencionabamos antes, las operaciones complejas se pueden reducir a dos operaciones simples, por ejemplo la LR podemos reducrila a realziar primero una RR en el hijo izquierdo y luego una LL en la raíz.

Pasemos a los ejemplos de código en C para ver como implementar estas rotaciones.

Lo primero que tenemos que hacer, es hacer una modificación al tipo de dato de árbol binario, ya que queremos tener en cuenta el FB en cada nodo, para detectar un desbalance. Agregaremos un campo int con la altura del nodo actual, lo cual nos permite saber sin tener que sumar recursivamente cada vez la altura de un nodo con sus hijos:

struct AVLNode {
int dato;
AVLNode izq;
AVLNode der;
int altura;
};

El siguiente paso es agregar una función que nos permite conocer la altura de un nodo actual, de forma que nuestro TAD quede bien estructurado, y en caso de ser necesario poder actualizar la misma calculando el FB:

int Altura (AVLNode* t) {
if(t == NULL)
return -1;
else
return t->altura;
}

AlturaCalcular (AVLNode* t) {
if(t != NULL)
t->altura = max (altura ((t)->izq), altura ((t)->der)) + 1;
}

Veamos el caso de una rotación simple RR:

void RotarAVLDer (AVLNode* &t) {
nodoAVL *taux;

taux = t->right;
t->right = taux->left;
taux->left = t;

actualizarAlturaAVL(t);
actualizarAlturaAVL(taux);

t = taux;
}

Como ven, pasamos la raíz por referencia, de forma que podemos modificar el puntero y colocar su hijo derecho en su lugar. Pero primero tenemos cuidado de copiar los datos necesarios para no perder las referencias, y de actualizar las alturas correspondientes. Ahora veamos el caso de la rotación doble, para la cual usaremos el hecho de que podemos descomponer la misma en dos rotraciones simples.

void RotarAVLDerDoble (AVLNode* t) {
RotarAVLIzq(&(t)->der);
RotarAVLDer(t);
}

Primero realizamos una LL y luego una RR, RotarAVLIzq es la rotación simple en el hijo izquierdo, análoga a RotarAVLDer que acabamos de ver pero sobre el hijo izquierdo de la raíz.

Con esto tenemos las operaciones básicas para balancear, crearemos una funcion que nos permita balancear cuando lo necesitemos, y luego veremos la de inserción que será simple ya que tenemos las tareas divididas en nuestro TAD AVL.

void BalancearAVL (AVLNode* t) {
if(t != NULL) {
if (Altura(t->izq) – Altura(t–>der) == 2) {  /* FB indica izquierda */
if (altura (t->izq->izq) >= altura (t->izq->der))
/* simple hacia la izquierda */
RotarAVLIzq(t);
else
/* doble hacia la izquierda */
RotarAVLIzqDoble(t);
}

else if (Altura(t->der) – Altura(t->izq) == 2) {  /* FB indica derecha */
if (Altura(t->der->der) >= Altura(t->der->izq))
/* simple derecha */
RotarAVLDer (t);
else
/* doble derecha */
RotarAVLDerDoble (t);
}
}
}

Y por último la inserción:

void InsertarAVL (AVLNode* t, int x) {
if (t == NULL) {
t = ArbolCrearAVL();
ArbolInsertar(t,x);
} else {
if (x < ArbolRaiz(t))
InsertarAVL(&t->izq, x);
else
InsertarAVL(&t->der, x);

BalancearAVL(t);
AlturaCalcular (t);
}
}

Al insertar buscamos la posición del elemento como lo hacemos normalmente en un árbol binario, buscando en derecho o izquierda de acuerdo a la comparación. Una vez que encontramos su posición creamos un nuevo nodo y lo insertamos, al regresar de la recursión debemos balancear los nodos ya que podríamos haber creado un desbalance, actualizando la altura según corresponda.

Con esto completamos nuestro TAD AVL, como ya dijimos tenemos la capacidad de ordenar el árbol y asegurarnos que el orden de búsqueda de un elemento no supere nunca Log(n). Un buen ejercicio de multiestructuras es pensar en la combinación de un AVL con una lista, de forma que podamos buscar determinado valor dentro del AVL, y luego a partir de ese valor podamos recorrer una cantidad de valores ordenados sin tener que buscar cada uno.

Supongamos que tenemos tiempos ordenados en un AVL, y queremos obtener los 10 tiempos siguiente a partir de cierto momento. Entonces lo que podemos hacer es tener un AVL “espejado” en una lista, con lo cual podemos buscar el tiempo deseado en el AVL (o el más cercano a él), y luego de encontrar el mismo saltamos a la lista (mantendremos un puntero a la posición correspondiente en cada nodo del AVL) y recorremos la lista obteniendo los 10 elementos. Así logramos un buen grado de eficiencia, teniendo únicamente que buscar un tiempo en el AVL con un orden Log(n) y luego recorriendo la lista que ya sabemos esta ordenada ya que mantenemos el orden al hacer cada inserción.

En la próxima entrada veremos las tablas de dispersión o Hash, los cuales nos permite hacer búsquedas en un tiempo constante.