Applications des arbres rouges-noirs

rouge-noir tree est une implémentation particulière d'un auto-équilibrage arbre de recherche binaire

arbres de recherche binaires 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 sets en utilisant seulement les clés et en ne stockant aucune valeur.

L'équilibrage de l'arbre est nécessaire pour garantir une bonne performance, car sinon, l'arbre pourrait dégénérer en une liste, par exemple, si vous insérez les clés qui sont déjà triés.

l'avantage des arbres de recherche sur les tables de hachage est que vous pouvez traverser l'arbre efficacement dans l'ordre de tri.

AVL-trees sont une autre variante des arbres de recherche binaires équilibrés. Ils étaient populaires avant les arbres rouges-noirs où connu. Ils sont mieux équilibrés, avec une différence maximale d'un entre les hauteurs du subtree gauche et droite (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 rouges et noirs sont certainement un bon choix mais pas le seul pour cette application.

les arbres noirs rouges appartiennent à une classe de TSB d'auto-équilibrage et comme d'autres ont répondu, n'importe quel arbre d'auto-équilibrage peut être utilisé. Je voudrais ajouter que les arbres rouges-noirs sont largement utilisés comme des tables de symboles de système. Par exemple, ils sont utilisés dans la mise en œuvre de la commande suivante:

• Java: java.util.TreeMap, java.util.TreeSet .
• C++ STL: carte, multimap, multiset.
• Linux kernel: completely fair scheduler, linux / rbtree.h

a moins que vous n'ayez des exigences de performance très spécifiques, un arbre R-B pourrait être remplacé par un autre arbre binaire auto-équilibrant, par exemple un arbre AVL. Le choix entre les deux est fondamentalement une optimisation des performances - ils offrent les mêmes opérations de base.

non pas que l'un d'eux soit définitivement "plus rapide" que l'autre, juste qu'ils soient suffisamment différents pour que des utilisations spécifiques d'eux aient tendance à avoir des performances légèrement différentes, tout le reste étant égal. Donc, si vous dessinez vos exigences assez soigneusement, ou juste par hasard, vous pourriez finir par l'un d'eux étant "assez rapide" pour votre usage, et l'autre pas. Le R - B offre une insertion légèrement plus rapide que L'AVL, au prix d'une recherche légèrement plus lente.

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

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

BTW vous pouvez rechercher les différents temps de couture et d'insertion etc requis pour un arbre noir rouge 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)