J'ai rêvé d'une structure de données, existe-t-elle?

Je n'ai pas réussi à trouver cette structure de données, mais je ne suis pas un expert dans le domaine.

La structure implémente un ensemble et est essentiellement un tableau d'éléments comparables avec un invariant. L'invariant est le suivant (défini récursivement):

Un tableau de longueur 1 est un tableau de fusion.

Un tableau de longueur 2 ^ n (pour n> 0) est un tableau de fusion ssi:

• la première moitié est un tableau de fusion et la seconde moitié est vide ou
• le premier tableau est plein et trié, et la seconde moitié est un tableau de fusion.

Notez que si le tableau est plein, il est trié.

Pour insérer un élément, nous avons deux cas:

• Si la première moitié n'est pas pleine, insérez récursivement dans la première moitié.
• Si la première moitié est pleine, insérez récursivement dans la seconde moitié.
• Après l'étape récursive, si le tableau entier est plein, fusionnez les moitiés (qui sont triées) et redimensionnez-le au double de sa longueur d'origine.

Pour trouver un élément, récursivement dans les deux moitiés, en utilisant la recherche binaire lorsque le tableau est plein. (Cela devrait être efficace car il y a au plus fragments ascendants).$O(\log(n))$

La structure peut être considérée comme une version statique de mergesort.

Il n'est pas clair ce que l'on doit faire pour effacer un élément.

Edit: après avoir amélioré ma compréhension de la structure.

Vous décrivez la méthode logarithmique classique de Bentley-Saxe , appliquée aux tableaux triés statiques. La même idée peut être utilisée pour ajouter la prise en charge des insertions à toute structure de données statique (pas d'insertions ou de suppressions) pour tout problème de recherche décomposable. (Un problème de recherche est décomposable si la réponse pour n'importe quelle union peut être calculée facilement à partir des réponses pour les ensembles A et B. ) La transformation augmente le temps de requête amorti d'un facteur O ( log n ) (sauf si elle était déjà plus grand que certains polynômes en $A\cup B$$A$$B$$O(\log n)$$n$), mais n'augmente l'espace que d'un facteur constant. Oui, il peut être désamorti, grâce à Overmars et van Leeuwen, mais vous ne voulez vraiment pas le faire si vous n'êtes pas obligé.

Ces notes couvrent les bases.

Les tableaux d'anticipation sans cache sont la progéniture mutante des arbres Bentley-Saxe et van Emde Boas sur les stéroïdes.

Ceci est similaire à une arborescence de fusion à structure logarithmique ou à un cache de tableaux d'anticipation inconscients (ou COLA).

$2^k-1$$2^i$$0 \leq i < k$

$2^0$$2^1$

$O(\lg n)$$O(n)$$O(\lg^2 n)$