Jointure plus rapide de structures de données de type treap avec approximativement la même taille

16

Étant donné deux arbres AVL T1 et T2 et une valeur tr telle que xT1,yT2,x<tr<y , il est facile de construire un nouvel arbre AVL contenant tr et les valeurs en T1 et T2 dans le temps O(1+|h(T1)h(T2)|) , oùh(T) désigne la hauteur d'un arbreT (tant que les arbres stockent leur hauteur).

Cela est également possible pour les arbres rouge-noir, et je suppose que de nombreux autres types d'arbres équilibrés sont également présents.

Est-ce possible pour les treaps ou les structures de données de type treap? Et si nous omettons tr ?

Le papier des tracés dans Algorithmica montre comment faire cela en temps prévu. S'il existe un moyen d'effectuer une jointure O (1) attendue sur des treaps (ou des structures de données de type treap) avec à peu près la même taille (ou priorité root), je pense qu'il pourrait être possible d'utiliser une astuce de Kaplan & Tarjan de bootstrapping les épines afin de faire des tracés (ou des structures de données de type treap) avec une jointure doublement logarithmique.O(min(h(T1),h(T2)))

jbapple
la source
Voici un code Haskell que j'ai écrit montrant une jointure rapide des arbres AVL avec approximativement la même taille: haskell.pastebin.com/nfGV8Ffz
jbapple
Je doute que cela soit possible, car il semble (sans preuve) que la profondeur attendue du nouveau nœud (contenant la valeur t_r) soit plus qu'une constante même dans le cas où h (T_1) = h (T_2).
Tsuyoshi Ito
Tsuyoshi Ito: Je suis d'accord, si vous attribuez une priorité au nouveau nœud de la même manière que vous attribuez des priorités aux autres nœuds. Et si vous lui affectiez une priorité garantie supérieure à celles des nœuds racine? Cela détruit la nature IID des priorités, mais que se passe-t-il si vous marquez ensuite les autres priorités comme décalées, d'une manière ou d'une autre, comme les chemins dans les arbres rouges-noirs persistants sont marqués aux points de terminaison? Ou que se passe-t-il si l'on stocke les valeurs uniquement dans les feuilles d'un treap, et effectue une jointure sans t_r?
jbapple
Les nœuds dans les pièges avec n descendants ont laissé des descendants avec une probabilité 1 / n. Cela peut contribuer aux longs temps de fusion, même pour des treaps de taille égale - la sélection d'une nouvelle racine nécessite de s'y rendre, ce qui, puisque la profondeur moyenne dans l'arbre est Theta (lg n), prend également du temps Theta (lg n). Que se passe-t-il si un nœud de récupération avec n descendants a laissé des enfants avec une probabilité (n choisissez i) / 2 ^ n, et que les valeurs ne sont stockées que dans les feuilles comme dans un arbre B +. Ensuite, joindre deux tailles égales redistribue un petit nombre d'éléments d'un arbre à l'autre dans l'attente.
jbapple
Si mes calculs sont corrects, le nombre attendu d'éléments redistribués est Theta (sqrt n), qui, en supposant que tout le reste pourrait être élaboré (comme la propriété de recherche de doigt), prendrait encore du temps Theta (lg n) dans l'attente. Et si vous utilisiez une distribution encore plus serrée?
jbapple

Réponses:

3

Non, il n'est pas possible de le faire avec des Treaps ordinaires si les priorités sont aléatoires.

L'affirmation précise que je ferai est que pour effectuer une telle fusion sur deux treaps de taille égale avec des priorités aléatoires, il faut mettre à jour Θ(logn) pointeurs dans l'attente.

Voici un croquis de preuve grossière:

Tenez compte du nombre de pointeurs que vous devez modifier dans l'attente d'effectuer l'opération. Il est plus facile de prouver une borne si nous n'insérons pas t r mais fusionnons simplement T 1 et T 2 . Considérons la colonne vertébrale droite S 1 de T 1 et la colonne vertébrale gauche S 2 de T 2 . Colorez les éléments de S 1 rouge et ceux de S 2 bleu. Ordre S 1S 2Θ(logn)trT1T2S1T1S2T2S1S2S1S2par priorité. Nous devons changer un pointeur à chaque fois que la couleur change dans cette séquence. Étant donné que les deux épines ont une taille avec une forte probabilité et que les priorités sont aléatoires, il n'est pas trop difficile de voir que le nombre de changements de couleur dans la séquence est également Θ ( log n ) . Nous devons donc mettre à jour les pointeurs Θ ( log n ) pour la fusion (sans ajouter t r ).Θ(logn)Θ(logn)Θ(logn)tr

Maintenant, ajouter pendant la fusion n'aide pas vraiment. Le nombre de changements de pointeur dans ce cas peut être inférieur comme suit: Ordonner S 1S 2{ t r } par priorité. Supprimez tout ce qui est inférieur à t r dans la séquence. Le nombre de changements de couleur dans la séquence résultante est alors notre borne inférieure. Puisque t r a une priorité aléatoire, la hauteur attendue du sous-arbre enraciné dans le treap final est O ( 1 ) , donc il n'a que O ( 1 ) nœuds de S 1trS1S2{tr}trtrO(1)O(1) avec une priorité inférieure à celle attendue, nous n'avons donc perdu que leschangements de pointeur O ( 1 ) dans notre borne inférieure lors de l'ajout de t r .S1S2O(1)tr

Maintenant, cela dit, il existe probablement un moyen d'obtenir une structure de données "semblable à un treap" qui permet des fusions temporelles attendues constantes.


la source
Oui, je recherche une structure de données "semblable à un treap". Bien que j'en ai mentionné autant dans les commentaires et ma réponse défunte, je ne l'ai pas mise dans le titre ou la question.
jbapple
Merci pour votre réponse. J'ai modifié le titre et le texte de la question afin d'être moins ambigu.
jbapple
1

Mise à jour: voir ci-dessous pour une mise à jour sur l'inexactitude de cette opération de jointure

Voici un croquis très sommaire d'une solution possible:

Je pense que je peux avoir une solution à ce problème en utilisant un type d'arbre B + équilibré de manière aléatoire. Comme les trésors, ces arbres ont une représentation unique. Contrairement aux treaps, ils stockent plusieurs clés plusieurs fois. Il pourrait être possible de résoudre ce problème en utilisant une astuce des "Arbres de recherche biaisés" de Bent et al. Consistant à stocker chaque clé uniquement au niveau le plus élevé (c'est-à-dire le plus proche de la racine) dans lequel elle apparaît)

Un arbre pour un ensemble ordonné de valeurs uniques est créé en associant d'abord chaque valeur à un flux de bits, similaire à la façon dont chaque valeur dans un treap est associée à une priorité. Chaque nœud de l'arborescence contient à la fois une clé et un flux binaire. Les nœuds non foliaires contiennent, en outre, un nombre naturel indiquant la hauteur de l'arbre enraciné à ce nœud. Les nœuds internes peuvent avoir un nombre d'enfants différent de zéro. Comme les arbres B +, chaque chemin non auto-intersecté de la racine à une feuille a la même longueur.

Chaque nœud interne contient (comme dans les arbres B +) la plus grande clé k de ses feuilles descendantes. Chacun contient également un nombre naturel i indiquant la hauteur de l'arbre enraciné en v , et le flux de bits associé à k à partir du i + 1 ème bit. Si chaque clé de l'arborescence enracinée en v a le même premier bit dans son flux binaire, chaque enfant de v est une feuille et i est 1 . Sinon, les enfants de v sont des nœuds internes qui ont tous le même i ème bit dans le flux binaire associé à leur clé.vkivki+1vvi1vi

Pour créer une arborescence à partir d'une liste triée de clés avec des flux binaires associés, collectez d'abord les clés en groupes contigus en fonction du premier bit de leurs flux. Pour chacun de ces groupes, créez un parent avec la clé et le flux binaire de la plus grande clé du groupe, mais en supprimant le premier bit du flux. Effectuez maintenant la même procédure de regroupement sur les nouveaux parents pour créer des grands-parents. Continuez jusqu'à ce qu'il ne reste qu'un nœud; c'est la racine de l'arbre.

La liste suivante de clés et (début de) flux binaires est représentée par l'arborescence en dessous. Dans les préfixes de flux binaire, un '.' signifie tout. C'est-à-dire que tout flux binaire pour la clé A avec un 0 en premier lieu produit le même arbre que n'importe quel autre, en supposant qu'aucun flux binaire d'une autre clé ne soit différent.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Chaque enfant d'un nœud interne particulier a le même bit en premier lieu de son flux binaire. C'est ce qu'on appelle la "couleur" du parent - 0 est rouge, 1 est vert. L'enfant a une "saveur" en fonction du premier bit de son flux binaire - 0 est cerise, 1 est menthe. Les feuilles ont des saveurs, mais pas de couleur. Par définition, un nœud cerise ne peut pas avoir de parent vert et un nœud menthe ne peut pas avoir de parent rouge.

n21n (n1i1)(n+1)/2n234nO(lgn)

Pour joindre deux arbres de même hauteur, vérifiez d'abord si leurs racines sont de la même couleur. Si c'est le cas, coupez de la racine gauche son enfant le plus à droite et de la racine droite son enfant le plus à gauche, puis joignez récursivement ces deux arbres. Le résultat sera un arbre de la même hauteur ou un plus grand car les arbres ont la même saveur (voir ci-dessous). Si le résultat de la jonction récursive des deux arbres a la même hauteur que les deux enfants coupés, faites-en l'enfant du milieu d'une racine avec les autres enfants de la racine gauche devant elle et les autres enfants de la racine droite après elle. S'il est plus grand de 1, faites de ses enfants les enfants du milieu d'une racine avec les autres enfants de la racine gauche avant et les autres enfants de la racine droite après elle. Si les racines ont des couleurs différentes, vérifiez si elles ont la même saveur. S'ils le font, donnez-leur un nouveau parent avec la clé et le flux binaire de la racine droite, élidant son premier bit. Si ce n'est pas le cas, donnez à chaque racine un nouveau parent avec la clé et le flux binaire de l'ancienne racine (en supprimant chaque premier bit), puis joignez récursivement ces arbres.

1/21/2O(1)1/4, et les appels récursifs ultérieurs sont toujours sur des arbres de couleurs différentes, donc la même analyse s'applique.

1/2O(1)

O(1)

a 01110
b 110..
c 10...
d 00000

L'arbre fait par [a,b]a une hauteur 2, l'arbre fait par [c,d]a une hauteur 2, et l'arbre fait par joinEqual (tree [a,b]) (tree [c,d])a une hauteur 3. Cependant, l'arbre fait par [a,b,c,d]a une hauteur 5.

Voici le code que j'ai utilisé pour trouver cette erreur .

jbapple
la source