Applications d'arbres rouge-noir

Question

Quelles sont les applications des arbres rouge-noir? Existe-t-il une application où seuls les arbres RB peuvent être utilisés et aucune autre structure de données?

Answer 1

À moins d'avoir des exigences de performance très spécifiques, un arbre R-B pourrait être remplacé par un autre arbre binaire auto-équilibré, par exemple un arbre AVL. Choisir entre les deux est essentiellement une optimisation des performances - ils offrent les mêmes opérations de base. Non pas que l'un d'entre eux soit définitivement "plus rapide" que l'autre, mais qu'ils sont suffisamment différents pour que leurs utilisations aient tendance à avoir des performances légèrement différentes, toutes choses étant égales par ailleurs. Donc, si vous dessinez vos exigences avec soin, ou juste par hasard, vous pourriez vous retrouver avec l'un d'entre eux étant «assez rapide» pour votre usage, et l'autre non. R-B offre une insertion légèrement plus rapide que AVL, au prix d'une recherche légèrement plus lente.

Answer 2

Un red-black tree est une implémentation particulière d'un self-balancing binary search tree, et aujourd'hui il semble être le choix d'implémentation le plus populaire.

Binary search trees sont utilisés pour implémenter des cartes finies, où vous stockez un ensemble de clés avec des valeurs associées. Vous pouvez également implémenter des ensembles en utilisant uniquement les clés et en ne stockant aucune valeur.

L'équilibrage de l'arborescence est nécessaire pour garantir de bonnes performances, sinon l'arborescence risque de dégénérer en une liste, par exemple si vous insérez des clés déjà triées. L'avantage des arborescences de recherche sur les tables de hachage est que vous pouvez parcourir l'arborescence efficacement dans l'ordre de tri.

AVL-trees sont une autre variante des arbres de recherche binaires équilibrés. Ils étaient populaires avant que les arbres rouges-noirs soient connus. Ils sont plus soigneusement équilibrés, avec une différence maximale de un entre les hauteurs des sous-arbres gauche et droit (les arbres RB garantissent au maximum un facteur de deux). Leur principal inconvénient est que le rééquilibrage demande plus d'efforts.

Donc, les arbres rouge-noir sont certainement un bon choix mais pas le seul pour cette application.

Answer 3

Il n'y a pas une telle règle comme le rouge ne peut être utilisé que dans un cas particulier cela dépend de l'application dans les cas comme lorsque Vous ne devez construire l'arbre qu'une seule fois et vous devez l'interroger plusieurs fois alors vous pouvez aller pour un arbre AVL car dans l'arbre AVL la recherche est assez rapide .. Mais il est strictement équilibré donc l'insertion et la suppression peuvent prendre du temps L'arbre AVl peut être utilisé pour la diction de langue où Vous devez construire la structure de données juste une fois et le rouge arbre noir est utilisé dans le planificateur complètement équitable utilisé dans les noyaux Linux actuels maintenant un jour ..

les contraintes appliquées sur l'arbre noir rouge également appliquer le point que le chemin de la racine à la feuille la plus éloignée n'est pas plus de deux fois plus longue que le chemin de la racine à la feuille la plus proche.

BTW vous pouvez rechercher les différents Seach et insérer etc temps nécessaire pour un arbre rouge noir ici

 Average  Worst case 

Space O(n)  O(n) 

Search O(log n) O(log n) 

Insert O(log n) O(log n) 

Delete O(log n) O(log n) 

Answer 4

Rouge Noir Les arbres sont d'une classe d'auto équilibrage BSTS et comme une réponse par d'autres, une telle l'arbre d'équilibrage automatique peut être utilisé. Je voudrais ajouter que les arbres rouge-noir sont largement utilisés comme tables de symboles système.Par exemple, ils sont utilisés dans l'implémentation de ce qui suit:

• Java: java.util.TreeMap, java.util.TreeSet.
• C++ STL: carte, multimap, multiset.
• noyau Linux: planificateur complètement juste, linux/rbtree.h

Answer 5

Le planificateur de processus Linux utilise des arbres Noir Rouge. Les arbres noirs rouges sont un remplacement pour les files d'attente d'exécution qui avaient des priorités pour les processus dans la file d'attente pour le planificateur à partir de. Le Completely Fair Scheduler (C.F.S) est le nom d'un planificateur de processus qui a été fusionné dans la version 2.6.23 du noyau Linux. Il gère l'allocation des ressources du processeur pour l'exécution des processus et vise à optimiser l'utilisation globale du processeur tout en maximisant les performances interactives.