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?
Ç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.
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?
