¿Qué estructuras de datos admiten la inserción, eliminación y selección de un elemento aleatorio con un límite de complejidad de tiempo [matemática] O (1) [/ matemática]?

Con la ayuda de la tabla Hash y la lista enlazada doblemente , podemos realizar las tres operaciones en tiempo O (1), pero la complejidad del peor caso dependerá de la función hash subyacente.

Inserción: inserte en una lista doblemente vinculada y almacene la dirección en una tabla hash. O (1)

Eliminación: obtenga la dirección del nodo de la lista doblemente vinculada de la tabla hash y elimínela de la lista doblemente vinculada. O (1)

Selección: Al usar la tabla hash, la selección se puede hacer en O (1), generando un número aleatorio de [0 … hash.size ()].

La ventaja de una lista doblemente vinculada sobre una matriz (tamaño fijo) es que no tenemos que preocuparnos por el tamaño.

Estructura de datos con tabla hash H y una matriz A. Las claves de tabla hash son los elementos en la estructura de datos, y los valores son sus índices en la matriz.

1. insert (value) : agrega el valor a la matriz y deja que sea su índice en A. Establece H [valor] = i.
2. eliminar (valor) : vamos a reemplazar la celda que contiene el valor en A con el último elemento en A. dejemos que ‘l’ sea el último elemento en la matriz A en el índice k. permítame ser H [valor], el índice en la matriz del valor que se eliminará. Establezca A [i] = l, H [l] = i, disminuya el tamaño de la matriz en uno y elimine el valor de H.
3. contiene (valor): devuelve H.contains (valor)
4. getRandomElement (): let r = random (tamaño actual de A). devuelve A [r].

Fuente: http://stackoverflow.com/questio …