Perché la cancellazione di solito è molto più difficile da implementare rispetto all'inserimento in molte strutture di dati?

È più di un semplice stato mentale; ci sono motivi fisici (per esempio digitali) per cui la cancellazione è più difficile.

Quando elimini, lasci un buco dove una volta c'era qualcosa. Il termine tecnico per l'entropia risultante è "frammentazione". In un elenco collegato, questo richiede di "patch attorno "al nodo rimosso e deallocare la memoria che sta usando. Negli alberi binari, provoca sbilanciamento dell'albero. Nei sistemi di memoria, la memoria non viene utilizzata per un po 'se i blocchi appena assegnati sono più grandi dei blocchi lasciati dall'eliminazione.

In breve, l'inserimento è più semplice perché puoi scegliere dove inserire. La cancellazione è più difficile perché non è possibile prevedere in anticipo quale elemento verrà cancellato.

Perché tende ad essere più difficile da eliminare che da inserire? Le strutture dati sono progettate in modo più attento all'inserimento che alla cancellazione, e giustamente.

Considera questo - al fine di eliminare qualcosa da una struttura dati, deve essere lì in primo luogo. Quindi è necessario aggiungerlo prima, il che significa che al massimo si hanno tante cancellazioni quante sono le inserzioni. Se si ottimizza una struttura dati per l'inserimento, si è certi di ottenere almeno tanto beneficio come se fosse stata ottimizzata per l'eliminazione.

Inoltre, che uso c'è nell'eliminare in sequenza ogni elemento? Perché non basta chiamare una funzione che lo cancella tutto in una volta (probabilmente solo creando una nuova)? Inoltre, le strutture dati sono più utili quando contengono effettivamente qualcosa. Quindi, il fatto di avere tante cancellazioni quante sono le inserzioni, in pratica, non sarà molto comune.

Quando ottimizzi qualcosa, vuoi ottimizzare le cose che fa di più e che impiegano più tempo. Nell'uso normale, la cancellazione di elementi di una struttura dati avviene meno frequentemente rispetto all'inserimento.

Non è più difficile.

Con gli elenchi doppiamente collegati, quando inserisci, assegnerai la memoria, quindi collegherai con la testa o il nodo precedente e con la coda o il nodo successivo. Quando si elimina, si scollegherà dallo stesso identico e quindi si libera memoria. Tutte queste operazioni sono simmetriche.

Ciò presuppone che in entrambi i casi si abbia il nodo da inserire / cancellare. (E nel caso dell'inserzione, che hai anche il nodo da inserire prima, quindi in un certo senso, l'inserimento potrebbe essere pensato come leggermente più complicato.) Se stai cercando di cancellare non avendo il nodo da eliminare, ma il < em> payload del nodo, quindi ovviamente dovrai prima cercare l'elenco per il payload, ma questa non è una mancanza di cancellazione, vero?

Con alberi bilanciati, lo stesso vale: un albero in genere ha bisogno di bilanciamento subito dopo un inserimento e anche immediatamente dopo una cancellazione. È una buona idea provare e avere una sola routine di bilanciamento e applicarla dopo ogni operazione, indipendentemente dal fatto che si trattasse di un inserimento o di una cancellazione. Se stai provando a implementare un inserimento che lascia sempre l'albero in equilibrio, e anche una cancellazione che lascia sempre l'albero in equilibrio, senza che i due condividano la stessa routine di bilanciamento, complichi inutilmente la tua vita.

In breve, non vi è alcun motivo per cui uno dovrebbe essere più duro dell'altro, e se si sta scoprendo che lo è, allora è infatti possibile che tu sia vittima della tendenza (molto umana) di trovarlo di più è naturale pensare in modo costruttivo che in modo sottrattivo, il che significa che potresti implementare l'eliminazione in un modo che è più complicato di quanto non debba essere. Ma questo è un problema umano. Da un punto di vista matematico, non ci sono problemi.

In termini di tempo di esecuzione, guardando il confronto della complessità temporale delle operazioni sulla struttura dei dati su Wikipedia, si noti che le operazioni di inserimento e cancellazione hanno la stessa complessità. L'operazione di eliminazione profilata è la cancellazione per indice, in cui si ha un riferimento all'elemento della struttura da eliminare; l'inserimento è per articolo. Il tempo di esecuzione più lungo per la cancellazione in pratica è perché di solito hai un elemento da eliminare e non il suo indice, quindi hai bisogno anche di un'operazione di ricerca. La maggior parte delle strutture dati nella tabella non richiedono una ricerca aggiuntiva per un inserto poiché la posizione del posizionamento non dipende dall'elemento o la posizione viene determinata implicitamente durante l'inserimento.

Per quanto riguarda la complessità cognitiva, c'è una risposta nella domanda: casi limite. La cancellazione può avere più di quelli dell'inserimento (questo deve ancora essere stabilito nel caso generale). Tuttavia, almeno alcuni di questi casi limite possono essere evitati in determinati progetti (ad esempio un nodo sentinella in un elenco collegato).

Oltre a tutti i problemi citati, è coinvolta l'integrità referenziale dei dati. Per la maggior parte costruire correttamente la struttura dei dati come i database in SQL, l'integrità referenziale Oracle è molto importante Per assicurarti di non distruggerlo accidentalmente molte cose diverse inventate.
Ad esempio cascata su cancella che non cancella solo ciò che si tenta di eliminare ma attiva anche la pulizia dei dati correlati.
Questo pulisce il database dai dati spazzatura e mantiene intatta l'integrità dei dati.
Ad esempio, hai tabelle con genitori e tipi come record correlati nella seconda tabella.
Dove genitore è la tabella principale. Se non hai un'integrità referenziale potenziata, puoi eliminare qualsiasi record in qualsiasi tabella e in seguito non sapresti come ottenere informazioni complete sulla famiglia perché hai dati nella tabella figlia e nulla nella tabella genitore.
Questo è il motivo per cui il controllo dell'integrità referenziale non ti consente di eliminare record dalla tabella genitore fino a quando non vengono eliminati i record dalla tabella figlio.
Ed è per questo che nella maggior parte delle fonti di dati è più difficile eliminare i dati.