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

Étant donné deux arbres AVL $T_1$ et $T_2$ et une valeur $t_r$ telle que $\forall x \in T_1, \forall y \in T_2, x < t_r < y$ , il est facile de construire un nouvel arbre AVL contenant $t_r$ et les valeurs en $T_1$ et $T_2$ dans le temps $O(1+|h(T_1) - h(T_2)|)$ , où$h(T)$ désigne la hauteur d'un arbre$T$ (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 $t_r$ ?

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(T_1),h(T_2)))$

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 $\Theta(\log n)$ 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 1 ∪ S $\Theta(\log n)$$t_r$$T_1$$T_2$$S_1$$T_1$$S_2$$T_2$$S_1$$S_2$$S_1 \cup S_2$par 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 ).$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$t_r$

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 1 ∪ S 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 $t_r$$S_1 \cup S_2 \cup \{t_r\}$$t_r$$t_r$$O(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 .$S_1 \cup S_2$$O(1)$$t_r$

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.

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é.$v$$k$$i$$v$$k$$i+1$$v$$v$$i$$1$$v$$i$

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.

$n$$2^{1-n}$ ${n-1}\choose{i-1}$$(n+1)/2$$n \geq 2$$\leq \frac{3}{4}n$$O(\lg n)$

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/2$$1/2$$O(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/2$$O(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 .