Sous-gamme d'un arbre rouge et noir

14

Tout en essayant de corriger un bogue dans une bibliothèque, j'ai cherché des articles sur la recherche de sous-gammes sur des arbres rouges et noirs sans succès. J'envisage une solution utilisant des fermetures à glissière et quelque chose de similaire à l' opération d' ajout habituelle utilisée sur les algorithmes de suppression pour les structures de données immuables, mais je me demande toujours s'il y a une meilleure approche que je n'ai pas pu trouver, ou même une limite de complexité minimale sur une telle opération?

Pour être clair, je parle d'un algorithme qui, étant donné un arbre rouge et noir et deux limites, produira un nouvel arbre rouge et noir avec tous les éléments du premier arbre qui appartiennent à l'intérieur de ces limites.

Bien sûr, une limite supérieure pour la complexité serait la complexité de parcourir un arbre et de construire l'autre en ajoutant des éléments.

Daniel C. Sobral
la source
3
@Radu: Il y a un bug dans la fonction de modification des commentaires. Si vous utilisez du latex dans un commentaire et modifiez le commentaire, vous voyez un comportement étrange, comme la duplication, etc.
Aryabhata
@Radu J'ai ajouté quelques paragraphes pour mieux expliquer ma question.
Daniel C.Sobral
Les arbres sont-ils immuables?
Tsuyoshi Ito
Aussi, vouliez-vous dire borne supérieure au lieu de borne inférieure dans le dernier paragraphe?
Tsuyoshi Ito
2
Il semble que l'opération de division sur les arbres rouge-noir puisse être implémentée dans le pire des cas O (log n), où n est le nombre d'éléments dans un arbre. Cette affirmation se trouve dans l'introduction de l'article «Listes triées caténables purement fonctionnelles dans le pire des cas» par Gerth Stølting Brodal, Christos Makris et Kostas Tsichlas, ESA 2006: cs.au.dk/~gerth/pub/esa06trees.html . Comme je l'ai mentionné dans mon commentaire précédent, cela permet une implémentation O (log n) dans le pire des cas de l'opération de sous-plage.
Tsuyoshi Ito,

Réponses:

10

Cette réponse combine certains de mes commentaires à la question et les développe.

L'opération de sous-plage sur les arbres rouge-noir peut être effectuée dans le pire des cas O (log n), où n est le nombre d'éléments dans l'arbre d'origine. Étant donné que l'arbre résultant partagera certains nœuds avec l'arbre d'origine, cette approche ne convient que si les arbres sont immuables (ou si les arbres sont mutables, mais l'arbre d'origine n'est plus nécessaire).

Remarquez tout d'abord que l'opération de sous-plage peut être implémentée par deux opérations fractionnées. Ici, l' opération de division prend un arbre rouge-noir T et une clé x et produit deux arbres L et R tels que L se compose de tous les éléments de T inférieurs à x et R les éléments de T supérieurs à x. Par conséquent, notre objectif est maintenant d'implémenter l'opération de division sur des arbres rouge-noir dans le pire des cas O (log n).

Comment effectuer l'opération de division sur des arbres rouge-noir en temps O (log n)? Eh bien, il s'est avéré qu'il y avait une méthode bien connue. (Je ne le savais pas, mais je ne suis pas un expert des structures de données.) Considérons l' opération de jointure , qui prend deux arbres L et R de telle sorte que chaque valeur dans L est inférieure à chaque valeur dans R et produit un arbre composé de tous les valeurs dans L et R. L'opération de jointure peut être implémentée dans le pire des cas O (| r L −r R | +1), où r L et r Rsont les rangs de L et R, respectivement (c'est-à-dire le nombre de nœuds noirs sur le chemin de la racine à chaque feuille). L'opération de division peut être implémentée en utilisant l'opération de jointure O (log n) fois, et le temps total le plus défavorable est toujours O (log n) en considérant une somme télescopique.

Les sections 4.1 et 4.2 d'un livre [Tar83] de Tarjan décrivent comment implémenter les opérations de jointure et de division sur des arbres rouge-noir dans le pire des cas O (log n). Ces implémentations détruisent les arborescences originales, mais il est facile de les convertir en implémentations fonctionnelles immuables en copiant les nœuds au lieu de les modifier.

Comme une note de côté, l'ensemble et les modules Carte de Objective Caml fournissent l'opération de scission, ainsi que d' autres opérations standard sur (immuable) équilibrée des arbres binaires de recherche. Bien qu'ils n'utilisent pas d'arbres rouge-noir (ils utilisent des arbres de recherche binaires équilibrés avec la contrainte que la hauteur gauche et la hauteur droite diffèrent d'au plus 2), regarder leurs implémentations pourrait également être utile. Voici l'implémentation du module Set .

Les références

[Tar83] Robert Endre Tarjan. Structures de données et algorithmes de réseau . Volume 44 de CBMS-NSF Regional Conference Series in Applied Mathematics , SIAM, 1983.

Tsuyoshi Ito
la source
@Radu GRIGore: Oui, sauf si je manque quelque chose.
Tsuyoshi Ito du
@Radu GRIGore: Ou peut-être pas, maintenant je ne suis pas sûr. Cette implémentation de l'opération fractionnée alloue O (log n) nouveaux nœuds pour l'arbre de sortie, mais je pense que l'opération entière peut probablement être implémentée de manière récursive en queue, ne nécessitant que O (1) d'espace de travail. Si cela est correct, la réponse à votre question dépendra de ce que vous entendez par «espace supplémentaire».
Tsuyoshi Ito
@Radu GRIGore: Dans ce cas, je pense que l'espace supplémentaire est O (1), bien que je ne l'ai pas vérifié attentivement.
Tsuyoshi Ito du
@Radu GRIGore: Je ne vois pas la raison pour laquelle on se soucie de la quantité d'espace de travail sans se soucier de la quantité d'espace nécessaire pour stocker le résultat lui-même. Dans la théorie de la complexité, le problème spécifie généralement quel est le résultat et donc l'espace nécessaire pour stocker le résultat ne dépend pas d'algorithmes. Cependant, dans le problème actuel, il existe de nombreuses façons d'implémenter l'opération requise et certaines implémentations nécessitent plus d'espace pour stocker le résultat que d'autres. Si vous ignorez la différence de cette quantité d'espace, je ne vois pas pourquoi vous vous souciez de l'espace de travail dont nous avons besoin.
Tsuyoshi Ito du
Le problème des arbres immuables est différent de celui des arbres mutables. Je comprends la différence, donc je n'avais rien à demander à ce sujet. Maintenant, en zoomant sur l'un des deux problèmes, il y a deux aspects à discuter: la mémoire et le temps. Vous n'avez pas dit combien de mémoire vous utilisez et il ne me semblait pas évident quelle était la réponse, alors j'ai demandé. Je ne vois pas comment cela vous a fait penser que j'ignore la différence entre les deux problèmes.
Radu GRIGore
8

La solution n'est pas d'utiliser des arbres rouge-noir. Dans les arborescences et les arborescences AVL, le code de fractionnement et de jointure est très simple. Je vous renvoie aux URL suivantes avec du code java pour les arbres splay et les arbres AVL qui prennent en charge cela. Accédez à l'URL suivante et consultez Set.java (arbres avl) et SplayTree.java (arbres splay).

ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/

--- Danny Sleator

Danny Sleator
la source
5
Bienvenue sur le site, Danny!
Suresh Venkat
2
Comment cela aidera-t-il à modifier l'implémentation Scala Red Black pour prendre en charge la sous-organisation en moins de O(n)? Je n'ai pas demandé quel type d'arbres ont des implémentations de sous-gammes simples car ce n'est pas un problème que j'ai. Cette réponse, bien que bien intentionnée, est hors sujet et inutile au problème en question.
Daniel C.Sobral
6

(Ceci est censé être un commentaire mais je suis trop nouveau pour laisser un commentaire.)

Je veux simplement noter que vous pouvez également être intéressé par l'opération "excision", qui renvoie la sous-gamme comme un nouvel arbre et l'arborescence d'entrée sans la sous-gamme comme une autre. Vous devez cependant contrôler la représentation sous-jacente de l'arborescence, car la méthode connue repose sur des liens de niveau. L'excision s'exécute dans le temps logarithmique à la taille du plus petit arbre, bien qu'au sens amorti ("amorti" est iirc, car je n'ai plus accès au papier) Voir:

K. Hoffman, K. Mehlhorn, P. Rosenstiehl et RE Tarjan, Tri des séquences de Jordan en temps linéaire à l'aide d'arbres de recherche liés au niveau, Information and Control, 68 (1986), 170-184

PS La citation ci-dessus est venue de l'écriture de triche de Seidel. Treaps prend également en charge l'excision.

Maverick Woo
la source
Cette méthode suppose que l'on a déjà des pointeurs (ou "doigts") vers les deux frontières.
jbapple
3

nm[une,b] dans un autre arbre rouge-noir.

  1. O(lgn)uneune successeur).
  2. O(m) .
  3. O(m)

O(m+lgn)O(n+mlgm)

o(m)Ω(lgm)klgm

Je n'ai pas travaillé sur les détails, donc je ne sais pas comment la comptabilité supplémentaire affecte le temps d'exécution.

O(1)Ω(lgm)

Radu GRIGore
la source
En y réfléchissant, je pense que je pourrais obtenir un décompte approximatif O(logn), avec lequel je pourrais éviter le tableau temporaire.
Daniel C.Sobral
Vous pouvez obtenir le nombre en O (lg n) en stockant la taille des sous-arbres dans leurs racines.
Radu GRIGore
... mais le stockage des tailles dans les nœuds va à l'encontre de la nécessité de ne pas utiliser d'espace auxiliaire, donc mon observation ne répond pas à votre préoccupation concernant la mémoire.
Radu GRIGore
1
Les arbres binaires peuvent être parfaitement rééquilibrés en utilisant uniquement un espace supplémentaire CONSTANT (en plus de l'arbre lui-même): eecs.umich.edu/~qstout/abs/CACM86.html
Jeffε
O(m+lgn)O(1)