Treap avec les touches implicites

Question

Il y a une structure de données appelée Treap. Qui est un arbre de recherche binaire aléatoire, qui est aussi un tas sur aléatoirement soi-disant « priorités »

Il y a une variation de cette structure, où les clés sont implicites, ils ne sont pas stockés dans l'arbre, mais nous considérons que l'index ordonné du nœud dans l'arbre comme la clé de ce noeud. Nous devons stocker la taille de sous-arbre dans chaque noeud au lieu de la clé. Cette technique nous permet de penser Treap comme une sorte de tableau, qui prend en charge de nombreuses opérations en O (log n):. Insertion, suppression, de réversion des sous-tableau, l'évolution sur l'intervalle et ainsi de suite

Je sais un peu plus sur cette structure, mais pas tellement. J'ai essayé de le google, mais je l'ai trouvé que beaucoup d'articles sur Treap lui-même, mais rien de ce « Treap implicite » / « liste indexée ». Je ne sais même pas son nom, parce que ma langue maternelle est pas anglais et je donne des cours ont écouté utilisé le terme natif de la structure, pas l'anglais terme original. Ce terme natif peut être traduit directement en anglais comme « Treap sur les touches implicites » ou « arbre cartésien sur les touches implicites ».

point que quelqu'un peut me à l'article sur cette structure ou me dire son nom d'origine? Merci.

P.S. Désolé si mon anglais était pas assez compréhensible.

UPD. Quelques explications supplémentaires sur la structure que je suis à la recherche

Considérons une Treap habituelle avec les priorités choisies au hasard et les clés, qui sont des données réelles de l'utilisateur stockées dans l'arborescence. Alors imaginons que nous avons d'autres informations utilisateur stockées dans chaque nœud, et les touches ne sont que les clés de recherche. L'étape suivante consiste à calculer et à maintenir la taille du sous-arbre dans chaque nœud: il faut mettre à jour ce paramètre après chaque fusion / de Split / Ajout / Suppression, mais il nous permet de trouver, par exemple, l'élément Nième de l'arbre en O (log N) temps.

Quand nous avons des tailles dans chaque sous-arbre noeud, nous pouvons jeter les clés loin et imaginer que Treap représente un tableau de données utilisateur dans afinde traversal. Indice de tableau de chaque élément peut être facilement calculé à partir de tailles sous-arbre. Maintenant, nous pouvons ajouter / supprimer un élément au milieu de tableau ou diviser ce tableau - tout en O (log n)

.

Nous pouvons aussi faire « multiple » opération - par exemple, ajouter une valeur constante à tous les éléments de notre « tableau ». Pour mettre en œuvre, nous devons faire cette opération retardée, ajoutez un paramètre dans chaque nœud qui représente une constante retard qui doit être « plus tard », a ajouté à tous les éléments de ce le sous-tableau de noeud, et « pousser » les changements de haut en bas comme nécessaire. Ajout d'une constante à sous-tableau ou peinture (marquage) du sous-tableau peut être retardé de cette façon, en inversant le sous-tableau (ici l'info retard dans le nœud dans le bit « sous-tableau doit être inversée »), et ainsi de suite.

UPD2: Voici extrait de code - pièce de la petite quantité d'informations que j'ai trouvé. Ne pas remarqué cyrillique :) mots « с неявным ключом » signifie en traduction directe « avec la clé implicite ».

Answer 1

Vous pouvez trouver cette structure de données dans le document de Kaplan et Verbin sur le tri des permutations signées par des reprises (page 7, section 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf .

Answer 2

L'idée clé (sans jeu de mots!) Dans treaps est d'utiliser des clés, qui sont répartis de façon aléatoire. Si vous supprimez les clés, je ne vois pas comment vous pouvez avoir une Treap: alors peut-être je mal compris votre question. Ou peut-être vous faites référence à l'alternative à treaps, répartition aléatoire arbre binaire de recherche . Les deux structures de données utilisent la même idée que vous pouvez atteindre la complexité moyenne cas en vous assurant que votre apparence d'arbre comme un arbre moyen (au lieu d'un cas pathologique).

Avec les treaps, vous le faites en utilisant des priorités aléatoires et l'équilibrage.

Avec répartition aléatoire des arbres binaires, le caractère aléatoire est uniquement inclus lors de la construction: qui est, lorsque vous insérez un nœud dans l'arbre T, il a une probabilité de 1 / être à la racine, où la taille (taille (T) + 1) (T) est le nombre de noeuds de T; et bien sûr si le nœud est pas inséré à la racine, vous continuez récursive jusqu'à ce qu'il soit ajouté. (Voir les articles de mon C. Martinez pour une étude détaillée de ces arbres.)

Cette structure de données se comporte exactement comme un Treap, mais utilise un mécanisme différent qui ne nécessite pas de clés.

Si ce n'est pas ce que vous recherchez, peut-être que vous pourriez partager quelques informations supplémentaires: a votre mention de conférencier personne qui aurait travaillé sur cette structure, où avez-vous ici ce conférencier et ce que son / votre nationalité. Il pourrait ne pas sembler, mais sachant que votre langue maternelle pourrait être un indice important que vous pouvez peg généralement à la baisse des algorithmes / structures de données à un pays spécifique qui a pris naissance il.

Answer 3

Peut-être vous cherchez un corde (forme complexe de chaîne) modifié à vos besoins pour les opérations retardées. Chose intéressante est qu'il ya une question ouverte au sujet des cordes ici et maintenant .

Answer 4

Je ne pense pas qu'il y ait un nom pour cette structure de données, car il est tout simplement une combinaison de deux concepts orthogonaux. Vous pouvez utiliser des clés implicites comme celui-ci avec à peu près toute structure de données d'arbre auto-équilibrage.

Vous pouvez jeter un oeil à des arbres Scapegoat, car ils utilisent la taille de sous-arbre déjà pour le rééquilibrage et ne nécessitent pas de frais généraux par nœud.