Pourquoi la suppression est-elle généralement beaucoup plus difficile à mettre en œuvre que l’insertion dans de nombreuses structures de données?

Pouvez-vous penser à une raison spécifique pour laquelle la suppression est généralement beaucoup plus difficile à implémenter que l'insertion de nombreuses structures de données (la plupart?)?

Exemple rapide: listes chaînées. L'insertion est triviale, mais la suppression comporte quelques cas particuliers qui la rendent beaucoup plus difficile. Les arbres de recherche binaires à auto-équilibrage tels que AVL et Red-black sont des exemples classiques d'implémentation de suppression douloureuse.

Je voudrais dire que cela a à voir avec la façon de penser de la plupart des gens: il est plus facile pour nous de définir les choses de manière constructive, ce qui conduit facilement à des insertions faciles.

C'est plus qu'un simple état d'esprit; Il existe des raisons physiques (numériques) pour lesquelles la suppression est plus difficile.

Lorsque vous supprimez, vous laissez un trou où quelque chose se trouvait. Le terme technique pour l'entropie qui en résulte est "fragmentation". Dans une liste chaînée, cela nécessite que vous «corrigiez» le nœud supprimé et libérez la mémoire qu'il utilise. Dans les arbres binaires, cela provoque un déséquilibre de l'arbre. Dans les systèmes de mémoire, la mémoire devient inutilisée pendant un certain temps si les blocs nouvellement alloués sont plus grands que les blocs laissés par suppression.

En bref, l'insertion est plus facile car vous devez choisir l'endroit où vous allez insérer. La suppression est plus difficile car vous ne pouvez pas prédire à l'avance quel élément sera supprimé.

Pourquoi a-t-il tendance à être plus difficile à supprimer qu'à insérer? Les structures de données sont conçues plus avec l'insertion dans l'esprit que la suppression, et à juste titre.

Considérez ceci - pour supprimer quelque chose d'une structure de données, il faut qu'elle soit là en premier lieu. Vous devez donc d'abord l'ajouter, ce qui signifie qu'au plus vous avez autant de suppressions que d'insertions. Si vous optimisez une structure de données pour l'insertion, vous aurez au moins autant d'avantages que si elle avait été optimisée pour la suppression.

De plus, à quoi sert-il de supprimer séquentiellement chaque élément? Pourquoi ne pas simplement appeler une fonction qui le nettoie en une seule fois (éventuellement en créant simplement une nouvelle)? De plus, les structures de données sont particulièrement utiles lorsqu'elles contiennent quelque chose. Donc, le cas d’avoir autant de suppressions que d’insertions ne sera pas, dans la pratique, très courant.

Lorsque vous optimisez quelque chose, vous voulez optimiser ce que vous faites le plus et qui prend le plus de temps. En utilisation normale, la suppression d'éléments d'une structure de données est moins fréquente que l'insertion.

Ce n'est pas plus dur.

Avec les listes doublement liées, lors de l'insertion, vous allouez de la mémoire, puis vous liez avec le nœud principal ou précédent, et avec le nœud suivant ou le nœud suivant. Lorsque vous supprimez, vous supprimez exactement le même lien, puis vous libérez de la mémoire. Toutes ces opérations sont symétriques.

Cela suppose que dans les deux cas, vous avez le noeud à insérer / supprimer. (Et dans le cas de l'insertion, vous devez également insérer le nœud avant, donc, d'une certaine manière, l'insertion peut être considérée comme légèrement plus compliquée.) Si vous essayez de supprimer sans avoir le nœud à supprimer, mais la charge utile du nœud, vous devrez bien sûr commencer par rechercher la charge utile dans la liste, mais ce n’est pas un défaut de suppression, n’est-ce pas?

Il en va de même pour les arbres équilibrés: un arbre doit généralement être équilibré immédiatement après une insertion et également immédiatement après une suppression. C'est une bonne idée d'essayer de ne créer qu'un seul programme d'équilibrage et de l'appliquer après chaque opération, qu'il s'agisse d'une insertion ou d'une suppression. Si vous essayez d'implémenter une insertion qui laisse toujours l'arbre équilibré et une suppression qui laisse toujours l'arbre équilibré, sans que les deux partagent la même routine d'équilibrage, vous compliquez inutilement votre vie.

En bref, il n’ya aucune raison pour que l’un soit plus dur que l’autre, et si vous constatez que c’est le cas, il est en fait possible que vous soyez victime de la tendance (très humaine) de trouver plus naturel de penser de manière constructive plutôt que soustractive, ce qui signifie que vous pouvez implémenter la suppression d'une manière plus compliquée que nécessaire. Mais c'est un problème humain. D'un point de vue mathématique, il n'y a pas de problème.

En termes d'exécution, en regardant la comparaison de complexité temporelle des opérations de structure de données sur Wikipedia, notez que les opérations d'insertion et de suppression ont la même complexité. L'opération de suppression décrite ici est une suppression par index, dans laquelle vous avez une référence à l'élément de structure à supprimer. l'insertion est par article. En pratique, la durée d'exécution la plus longue pour la suppression est due au fait que vous avez généralement un élément à supprimer et non son index. Vous avez donc également besoin d'une opération de recherche. La plupart des structures de données de la table ne nécessitent pas de recherche supplémentaire pour une insertion car la position de placement ne dépend pas de l'élément ou la position est déterminée implicitement lors de l'insertion.

En ce qui concerne la complexité cognitive, la réponse à la question est la suivante: les cas extrêmes. La suppression peut en contenir plus que l’insertion (ceci n’a pas encore été établi dans le cas général). Cependant, au moins certains de ces cas extrêmes peuvent être évités dans certaines conceptions (par exemple, un nœud sentinelle dans une liste chaînée).

En plus de tous les problèmes mentionnés, l’intégrité référentielle des données est impliquée. Pour que la structure de données, comme les bases de données SQL, soit correctement construite, l’intégrité référentielle Oracle est très importante.
Pour vous assurer que vous ne détruisez pas accidentellement de nombreuses choses inventées.
Par exemple, la suppression en cascade supprime non seulement ce que vous tentez de supprimer, mais déclenche également le nettoyage des données associées.
Cette base de données nettoie les données indésirables et préserve l’intégrité des données.
Par exemple, vous avez des tables avec des parents et des types en tant qu’enregistrements liés dans la seconde table.
Où parent est la table principale. Si vous ne disposez pas d'une intégrité référentielle renforcée, vous pouvez supprimer tous les enregistrements d'une table. Par la suite, vous ne saurez plus comment obtenir des informations complètes sur la famille, car vous avez des données dans la table enfant et rien dans la table parent.
C'est pourquoi le contrôle d'intégrité référentielle ne vous permettra pas de supprimer l'enregistrement de la table parent tant que les enregistrements de la table enfant n'auront pas été nettoyés.
Et c’est pourquoi, dans la plupart des sources de données, il est plus difficile de supprimer des données.