algorithm - tablas - ¿Por qué la eliminación de elementos de la tabla hash con una lista doblemente vinculada es O(1)?

tabla hash en c codigo

Question

En el libro de texto de CLRS "Introducción al algoritmo", hay un párrafo en la pág. 258.

Podemos eliminar un elemento en tiempo O (1) si las listas están doblemente enlazadas. (Tenga en cuenta que CHAINED-HASH-DELETE toma como entrada un elemento x y no su clave k, para que no tengamos que buscar primero x. Si la tabla hash admite la eliminación, entonces su lista vinculada debe estar doblemente vinculada para que podemos eliminar un elemento rápidamente. Si las listas solo estuvieran vinculadas individualmente, para eliminar el elemento x, primero tendríamos que encontrar x en la lista para poder actualizar el siguiente atributo del predecesor de x. Con listas vinculadas individualmente, ambas eliminaciones y la búsqueda tendría los mismos tiempos de ejecución asintóticos).

Lo que me desconcierta es este gran parentesco, no pude entender su lógica. Con la lista doblemente enlazada, todavía hay que encontrar x para eliminarla, ¿en qué se diferencia esto de la lista enlazada individualmente? ¡Por favor ayúdame a entenderlo!

Answer 1

Codificación del punto de vista: se puede usar unordered_map en c ++ para implementar esto.

unordered_map<value,node*>mp;

Donde node* es un puntero a una estructura que almacena los indicadores clave, izquierdo y derecho!

Cómo utilizar:

Si tiene un valor v y desea eliminar ese nodo, simplemente haga lo siguiente:

1. Acceda a ese valor de nodos como mp[v] .

2. Ahora simplemente haga que su puntero izquierdo apunte al nodo a su derecha.

Y listo, ya está.

(Solo para recordar, en C ++ unordered_map toma un O (1) promedio para acceder a un valor específico almacenado).

Answer 2

El libro de texto está mal. El primer miembro de una lista no tiene un puntero "anterior" utilizable, por lo que se necesita un código adicional para encontrar y desvincular el elemento si resulta ser el primero en la cadena (por lo general, el 30% de los elementos es la cabeza de su cadena, si N = M, (cuando se mapean N elementos en M ranuras; cada ranura tiene una cadena separada.))

EDITAR:

Una forma mejor de usar un enlace de retroceso es usar un puntero al enlace que nos señala (normalmente, el siguiente enlace del nodo anterior en la lista)

struct node {
struct node **pppar;
struct node *nxt;
...
}

la eliminación se convierte entonces en:

*(p->pppar) = p->nxt;

Y una buena característica de este método es que funciona igual de bien para el primer nodo de la cadena (cuyo puntero pppar apunta a un puntero que no forma parte de un nodo).

ACTUALIZACIÓN 2011-11-11

Debido a que la gente no puede ver mi punto, trataré de ilustrarlo. Como ejemplo, hay una tabla de table hash (básicamente una matriz de punteros) y un grupo de nodos one , two , three , uno de los cuales debe eliminarse.

 struct node *table[123];
struct node *one, *two,*three;
/* Initial situation: the chain {one,two,three}
** is located at slot#31 of the array */
table[31] = one, one->next = two , two-next = three, three->next = NULL;
one->prev = NULL, two->prev = one, three->prev = two;
/* How to delete element one :*/
if (one->prev == NULL) {
table[31] = one->next;
}
else {
one->prev->next = one->next
}
if (one->next) {
one->next->prev = one->prev;
}

Ahora es obvio que el código de obove es O (1), pero hay algo desagradable: todavía necesita una array , y el índice 31 , por lo que en la mayoría de los casos un nodo es "autónomo", y un puntero a un nodo es suficiente para eliminarlo de su cadena, excepto cuando sea el primer nodo de su cadena; Luego se necesitará información adicional para encontrar la table y 31 .

A continuación, considere la estructura equivalente con un puntero a puntero como un enlace de retroceso.

 struct node {
struct node *next;
struct node **ppp;
char payload[43];
};
struct node *table[123];
struct node *one, *two,*three;
/* Initial situation: the chain {one,two,three}
** is located at slot#31 of the array */
table[31] = one, one-next = two , two-next = three, three->next = NULL;
one->ppp = &table[31], two->ppp = &one->next, three->ppp = &two-next;
/* How to delete element one */
*(one->ppp) = one->next;
if (one->next) one->next->ppp = one->ppp;

Nota: no hay casos especiales, y no es necesario conocer la tabla principal. (considere el caso en el que hay más de una tabla hash, pero con los mismos tipos de nodo: la operación de eliminación todavía debería saber de qué tabla debe eliminarse el nodo).

A menudo, en el escenario {anterior, siguiente}, los casos especiales se evitan al agregar un nodo ficticio al comienzo de la lista de enlaces dobles; Pero eso también necesita ser asignado e inicializado.

Answer 3

El problema que se presenta aquí es: considera que estás mirando un elemento particular de una tabla hash. ¿Qué tan costoso es borrarlo?

Supongamos que tiene una lista enlazada simple:

v ----> w ----> x ----> y ----> z
|
you''re here

Ahora, si elimina x , necesita conectar w to y para mantener su lista vinculada. Debe acceder a w y decirle que apunte a y (desea tener w ----> y ). ¡Pero no puedes acceder a w desde x porque está simplemente vinculado! Por lo tanto, debe revisar toda su lista para encontrar w en las operaciones O (n) y luego indicar que se vincule a y . Eso es malo.

Entonces, supongamos que estás doblemente vinculado:

v <---> w <---> x <---> y <---> z
|
you''re here

Genial, puedes acceder a wy a desde aquí, ¡así que puedes conectar los dos ( w <---> y ) en la operación O (1)!

Answer 4

En general, usted tiene razón: el algoritmo que ha publicado toma un elemento como entrada y no solo su clave:

Tenga en cuenta que CHAINED-HASH-DELETE toma como entrada un elemento x y no su clave k, por lo que no tenemos que buscar primero x .

Usted tiene el elemento x: como es una lista con doble enlace, tiene punteros a predecesor y sucesor, por lo que puede corregir esos elementos en O (1). Con una sola lista vinculada, solo el sucesor estará disponible, por lo que tendrá que búsqueda del predecesor en O (n).

Answer 5

Me parece que la parte de esto de la tabla hash es principalmente una pista falsa. La pregunta real es: "¿podemos eliminar el elemento actual de una lista enlazada en tiempo constante, y si es así, cómo?"

La respuesta es: es un poco difícil, pero en efecto sí, podemos, al menos generalmente. No (normalmente) tenemos que atravesar la lista enlazada completa para encontrar el elemento anterior. En su lugar, podemos intercambiar los datos entre el elemento actual y el siguiente elemento, y luego eliminar el siguiente elemento.

La única excepción a esto es cuando / si necesitamos / queremos eliminar el último elemento de la lista. En este caso, no hay ningún elemento siguiente para intercambiar. Si realmente tienes que hacer eso, no hay una manera real de evitar encontrar el elemento anterior. Sin embargo, hay formas que generalmente funcionan para evitar eso: una es terminar la lista con un centinela en lugar de un puntero nulo. En este caso, como nunca eliminamos el nodo con el valor centinela, nunca tendremos que eliminar el último elemento de la lista. Eso nos deja con un código relativamente simple, algo como esto:

template <class key, class data>
struct node {
key k;
data d;
node *next;
};
void delete_node(node *item) {
node *temp = item->next;
swap(item->key, temp->key);
swap(item->data, temp->data);
item ->next = temp->next;
delete temp;
}

Answer 6

Mientras revisaba el libro de texto, también me confundí con el mismo tema ( si "x" es un indicador de un elemento o el elemento en sí mismo ) y finalmente llegué a esta pregunta. Pero después de pasar por la discusión anterior y volver a referir el libro de texto, creo que en el libro "x" se supone implícitamente que es un "nodo" y sus posibles atributos son "clave", "siguiente".

Algunas líneas forman el libro de texto.

1) CHAINED-HASH-INSERT (T, x) inserte x en el encabezado de la lista T [h ( x.key )]

2) Si las listas solo estuvieran vinculadas individualmente, para eliminar el elemento x, primero deberíamos encontrar x en la lista T [h ( x.key )] para poder actualizar el siguiente atributo del predecesor de x.

Por lo tanto, podemos asumir que el indicador del elemento está dado y creo que Fezvez ha dado una buena explicación para la pregunta formulada.

Answer 7

Supongamos que desea eliminar un elemento x, al utilizar la lista de enlaces dobles, puede conectar fácilmente el elemento anterior de x al siguiente elemento de x. así que no hay necesidad de pasar por toda la lista y estará en O (1).

Answer 8

Find(x) es, en general, O (1) para una tabla hash encadenada; es irrelevante si usa o no listas enlazadas individualmente o listas doblemente vinculadas. Son idénticos en rendimiento.

Si, después de haber ejecutado Find(x) , decide que desea eliminar el objeto devuelto, encontrará que, internamente, es posible que una tabla hash tenga que buscar su objeto nuevamente. Por lo general, seguirá siendo O (1) y no será un gran problema, pero si descubre que borra muchísimo, puede hacerlo un poco mejor. En lugar de devolver el elemento de un usuario directamente, devuelva un puntero al nodo hash subyacente. A continuación, puede aprovechar algunas estructuras internas. Entonces, si en este caso, eligió una lista doblemente enlazada como la forma de expresar su encadenamiento, durante el proceso de eliminación, no es necesario volver a calcular el hash y buscar la colección nuevamente. Puede omitir este paso. Tienes suficiente información para realizar una eliminación directamente desde donde estás sentado. Se debe tener cuidado adicional si el nodo que está enviando es el nodo principal, por lo que se puede usar un entero para marcar la ubicación de su nodo en la matriz original si es el encabezado de una lista vinculada.

La compensación es el espacio garantizado que ocupa el puntero adicional frente a un posible borrado más rápido (y un código un poco más complicado). Con los equipos de sobremesa modernos, el espacio suele ser muy barato, por lo que podría ser una compensación razonable.