Forum Clubic

[algorithmes] Cherche algorithme

On a 2 ensembles de données (listes, arbres… ) L1 et L2, indexés avec une relation d’ordre total.

Cherche algorithme permettant

[] l’insertion/suppression d’1 élément dans un des ensembles
[
] l’insertion/suppression d’une suite consécutive de m éléments de L1. ie: plusieurs éléments dont les index sont croissants et consécutif dans l’ensemble L1 (pas forcément des index consécutifs dans N…)

Tous supression dans un l’ensemble L1 se traduit par un ajout dans L2.

Ex.

L1 à les éléments d’index:
1,2, 3, … 23, 24, 26, 29, 30, 31, 33 …
Il faut déplacer les éléments d’index 24=< i =< 30
pour les mettres dans l’ensemble L2.

:??: J’ai trouvé en (m+1)*log(n) (ou m est le nombre d’éléments à déplacer et n la taille de l’ensemble) mais je pense qu’il y a moyen de faire en log(n).

Ca serait pas plutôt un truc linéaire? Je veux dire: tu sélectionne ton élément i, tu le déplace, tu regarde le suivant (ou le courant, vu que tu déplace), si [valeur(i+1)-valeur(i)] = 1, tu déplace…

Ca fait déjà k éléments à déplacer, avec k le nombre d’élément consécutifs

Puis pareil à gauche (en décroissant?) je suppose, donc ça fait p éléments.

Plus le parcours dans la liste qui est linéaire, genre O(n)…

Ton truc doit donner du O(n+k+p) où n est l’indice de l’élément.

Maintenant je sais pas, moi et l’algo… :o

Oui, si on utilise des listes, mais j’utilise des arbres justement!