Structure de données

Bonjour ^^
Je suis à la recherche d’une structure de données où :

  • la recherche d’un élément dans la structure de données se fait en cout constant
  • la concaténation de deux instances de cette structure de données est constante aussi
    Vous avez une idée ce que ca pourrais être ou à quoi ca ressemblerais?

Pour exemple :

  • la recherche d’un élément dans une liste est linéaire en la taille de la liste, mais la concaténation de deux listes est en cout constant
  • La recherche d’une clé dans un dictionnaire est en cout constant mais la concaténation de deux dictionnaires est linéaire en la taille du dictionnaire

Je suppose qu’une telle structure à forcement des defaults autre part, comme la suppression d’élément par exemple,
mais je n’ai pas vraiment trouvé d’idée qui permettrais d’implémenter une structure avec ces propriétés et est-ce seulement possible?

Merci d’avance pour votre aide ^^

Il y’a des spécialistes des l’algo ici, mais j’ai du mal à imaginer comment une recherche peut être à coût constant.

Avec une hashtable, en moyenne:

Ouais, je pensais « dans une liste » dans ma tête. Je suis pas bien réveillé :stuck_out_tongue:

Ça ressemble à une LinkedHashMap. Le code est dispo dans le JDK.
Et si je vous ai aidé à faire vos devoirs de 1ère ou 2ème année de formation de dev, j’veux un bisou. :stuck_out_tongue:

Tu es sûr que ça se concatène en temps constant ?
L’ajoût d’un lien entre les deux liste est constant en effet, mais ce sont aussi des maps, donc tu vas devoir les merger, c’est du O(n).

L’opération de concaténation revient à fusionner les arbres qui stockent les hashes et à rebrancher les linkedlist, ça ne doit pas être o(n) à mon avis. plutôt un truc genre log(n) au doigt mouillé.
Je viens de voir en passant que l’implem java fait pas du tout ça.
edit: Hum, si c’est du O(n) avec un b-tree, y’a des chances que j’aie totalement tort. Une implem simple est en O(n) Merge Two Binary Trees by doing Node Sum (Recursive and Iterative) - GeeksforGeeks

De ce que j’ai compris sur les linkedHashTables (je ne connaissais pas cette structure) c’est une extension des HashTables, mais avec un ajout ‹ suivant › ‹ precedent › pour conserver l’ordre d’ajout dans la Table, ou éventuellement une liste annexe qui conserve l’ordre. C’est ca?

Mais si on veut ajouter un ensemble d’élément à la table il faut toujours les ajouter 1 à 1.
La structure d’arbre est intéressante pour avoir un ordonnancement d’un ensemble, mais elle reste contraignante à conserver puisque l’on veut garder l’ordre, et donc l’insertion et la recherche sont en O(ln(n)) non?