¿Por qué la eliminación suele ser mucho más difícil de implementar que la inserción en muchas estructuras de datos?

¿Puede pensar en alguna razón específica por la cual la eliminación es generalmente mucho más difícil de implementar que la inserción para muchas (la mayoría) de estructuras de datos?

Ejemplo rápido: listas vinculadas. La inserción es trivial, pero la eliminación tiene algunos casos especiales que la hacen significativamente más difícil. Los árboles de búsqueda binarios de equilibrio automático como AVL y Rojo-negro son ejemplos clásicos de implementación de eliminación dolorosa.

Me gustaría decir que tiene que ver con la forma en que la mayoría de la gente piensa: es más fácil para nosotros definir las cosas de manera constructiva, lo que lleva muy bien a inserciones fáciles.

Es más que un simple estado mental; Hay razones físicas (es decir, digitales) por las que la eliminación es más difícil.

Cuando eliminas, dejas un agujero donde solía estar algo. El término técnico para la entropía resultante es "fragmentación". En una lista vinculada, esto requiere "parchear" el nodo eliminado y desasignar la memoria que está utilizando. En árboles binarios, causa un desequilibrio del árbol. En los sistemas de memoria, hace que la memoria no se use por un tiempo si los bloques recién asignados son más grandes que los bloques que quedan por eliminación.

En resumen, la inserción es más fácil porque puedes elegir dónde vas a insertar. La eliminación es más difícil porque no puede predecir de antemano qué elemento se eliminará.

¿Por qué tiende a ser más difícil eliminar que insertar? Las estructuras de datos están diseñadas más teniendo en cuenta la inserción que la eliminación, y con razón.

Considere esto: para eliminar algo de una estructura de datos, tiene que estar allí en primer lugar. Por lo tanto, primero debe agregarlo, lo que significa que a lo sumo tiene tantas eliminaciones como inserciones. Si optimiza una estructura de datos para la inserción, se garantiza que obtendrá al menos tanto beneficio como si se hubiera optimizado para su eliminación.

Además, ¿de qué sirve eliminar secuencialmente cada elemento? ¿Por qué no simplemente llamar a alguna función que la borra de una vez (posiblemente simplemente creando una nueva)? Además, las estructuras de datos son más útiles cuando realmente contienen algo. Entonces, el caso de tener tantas eliminaciones como inserciones no es, en la práctica, muy común.

Cuando optimizas algo, quieres optimizar las cosas que hace más y que toman más tiempo. En uso normal, la eliminación de elementos de una estructura de datos ocurre con menos frecuencia que la inserción.

No es mas dificil.

Con listas doblemente vinculadas, cuando inserte, estará asignando memoria, y luego se vinculará con el nodo principal o el nodo anterior, y con el nodo de cola o el siguiente. Cuando elimine, estará desvinculando exactamente de lo mismo y luego liberando memoria. Todas estas operaciones son simétricas.

Esto supone que en ambos casos tiene el nodo para insertar / eliminar. (Y en el caso de la inserción, que también tiene el nodo para insertar antes, por lo que, en cierto modo, la inserción podría considerarse un poco más complicada). Si está tratando de eliminar no tener el nodo para eliminar, sino la carga útil del nodo, entonces, por supuesto, primero tendrá que buscar en la lista la carga útil, pero eso no es un defecto de eliminación, ¿verdad?

Con árboles balanceados, lo mismo aplica: un árbol generalmente necesita balancearse inmediatamente después de una inserción y también inmediatamente después de una eliminación. Es una buena idea intentar tener una sola rutina de equilibrio y aplicarla después de cada operación, independientemente de si fue una inserción o una eliminación. Si está intentando implementar una inserción que siempre deja el árbol equilibrado, y también una eliminación que siempre deja el árbol equilibrado, sin que ambos compartan la misma rutina de equilibrio, está complicando innecesariamente su vida.

En resumen, no hay ninguna razón por la cual uno debería ser más difícil que el otro, y si descubres que es así, es posible que seas víctima de la tendencia (muy humana) de pensar que es más natural pensar de manera constructiva que sustractiva, lo que significa que podría estar implementando la eliminación de una manera que es más complicada de lo que debería ser. Pero eso es un problema humano. Desde un punto de vista matemático, no hay problema.

En términos de tiempo de ejecución, mirando el comparación de la complejidad del tiempo de las operaciones de estructura de datos en Wikipedia, tenga en cuenta que las operaciones de inserción y eliminación tienen la misma complejidad. La operación de eliminación perfilada allí es una eliminación por índice, donde tiene una referencia al elemento de estructura que se va a eliminar; La inserción es por artículo. El mayor tiempo de ejecución para la eliminación en la práctica se debe a que generalmente tiene un elemento para eliminar y no su índice, por lo que también necesita una operación de búsqueda. La mayoría de las estructuras de datos en la tabla no requieren una búsqueda adicional para una inserción porque la posición de colocación no depende del elemento, o la posición se determina implícitamente durante la inserción.

En cuanto a la complejidad cognitiva, hay una respuesta en la pregunta: casos extremos. La eliminación puede tener más de ellos que la inserción (esto aún no se ha establecido en el caso general). Sin embargo, al menos algunos de estos casos extremos se pueden evitar en ciertos diseños (por ejemplo, tener un nodo centinela en una lista vinculada).

Además de todos los problemas mencionados, hay una integridad referencial de datos involucrada. Para la estructura de datos más adecuada como bases de datos en SQL, la integridad referencial de Oracle es muy importante.
Para asegurarse de no destruirlo accidentalmente, se inventaron muchas cosas diferentes. Es por eso que la verificación de integridad referencial no le permitirá eliminar registros de la tabla primaria hasta que se limpien los registros de la tabla secundaria. Y es por eso que en la mayoría de las fuentes de datos es más difícil eliminar datos.
Por ejemplo, en cascada en la eliminación, que no solo elimina lo que intente eliminar, sino que también desencadena la limpieza de los datos relacionados.
Esta base de datos de limpieza de datos basura y mantiene intacta la integridad de los datos.
Por ejemplo, tiene tablas con padres y clases como registros relacionados en la segunda tabla.
Donde padre es la mesa principal. Si no tiene una integridad referencial reforzada, puede eliminar cualquier registro en cualquier tabla y más adelante no sabrá cómo obtener información familiar completa porque tiene datos en la tabla secundaria y nada en la tabla primaria.