Avantage d'un nœud sentinelle dans un arbre noir rouge?

Question

J'ai créé une liste à double liaison, et les avantages d'un noeud sentinelle étaient clairs - pas de vérifications nuls ou de cas spéciaux aux limites de la liste. Maintenant, j'écris un arbre noir rouge, et j'essaie de comprendre s'il y a un avantage à un tel concept.

Ma mise en œuvre est basée sur les deux dernières fonctions this article (haut en bas d'insertion/suppression). L'auteur utilise une "racine d'arbre factice" ou "tête" pour éviter les cas spéciaux à la racine pour ses algorithmes d'insertion/suppression. Le noeud principal de l'auteur est limité aux fonctions elles-mêmes - apparemment en raison de son utilité limitée.

Un autre article que j'ai rencontré mentionnait l'utilisation d'une racine permanente au-dessus de la tête comme une «fin» pour l'itération. Cela semble intéressant, mais je l'ai essayé et ne voyais aucun avantage réel à utiliser NULL comme un itérateur de fin. J'ai également trouvé plusieurs articles qui utilisaient une sentinelle partagée pour représenter tous les nœuds de feuille vides, mais cela semble encore plus inutile que le premier cas. Est-ce que quelqu'un peut expliquer comment un nœud sentinelle serait utile dans un arbre noir rouge?

Answer 1

Les implémentations d'arbre rouge-noir utilisent presque toujours une sentinelle noire pour toutes les feuilles.

Il enregistre beaucoup de vérifications nuls lorsque vous pouvez vérifier la couleur sans vérifier d'abord null.

Cela ne fonctionne pas dans les implémentations qui utilisent des pointeurs parents, bien sûr. Dans ces implémentations, les sentinelles ne sont généralement pas utilisées car vous devez allouer une sentinelle différente pour chaque position de feuille, ce qui représente une perte de mémoire.