Nœud sentinelle - Sentinel node

Cet article concerne la construction de programmation informatique. Pour la partie du corps, voir Ganglion sentinelle .
À ne pas confondre avec la valeur sentinelle .

Dans la programmation informatique, un ganglion sentinelle est un spécifiquement désigné nœud utilisé avec les listes chaînées et arbres comme une terminaison de parcours de chemin. Ce type de nœud ne contient ni ne fait référence à aucune donnée gérée par la structure de données.

Avantages

Les sentinelles sont utilisées comme une alternative à l'utilisation NULL comme terminateur de chemin afin d'obtenir un ou plusieurs des avantages suivants:

  • Vitesse des opérations légèrement accrue
  • Augmentation de la robustesse de la structure des données (sans doute)

Désavantages

  • Complexité algorithmique et taille de code légèrement augmentées.
  • Si l'accès à la structure de données est simultané (ce qui signifie que tous les nœuds auxquels on accède doivent être protégés au moins pour «lecture seule» ), pour une implémentation basée sur la sentinelle, le nœud sentinelle doit être protégé pour la «lecture-écriture» par un mutex . Ce mutex supplémentaire dans de nombreux scénarios d'utilisation peut entraîner une grave dégradation des performances. Une façon de l'éviter est de protéger la structure de la liste dans son ensemble pour «lecture-écriture», alors que dans la version avec NULL elle suffit de protéger la structure de données dans son ensemble pour «lecture seule» (si une opération de mise à jour ne suit pas ).
  • Le concept sentinelle n'est pas utile pour l'enregistrement de la structure de données sur disque.

Exemples

Rechercher dans une liste liée

Vous trouverez ci-dessous deux versions d'un sous-programme (implémenté dans le langage de programmation C ) pour rechercher une clé de recherche donnée dans une liste liée individuellement . Le premier utilise la valeur sentinelle NULL , et le second un (pointeur vers le) nœud sentinelle Sentinel , comme indicateur de fin de liste. Les déclarations de la structure de données de la liste chaînée unique et les résultats des deux sous-programmes sont les mêmes. 

struct sll_node {                          // one node of the singly linked list
    struct sll_node *next;                 // end-of-list indicator or -> next node
    int key;
} sll, *first;

Première version utilisant NULL comme indicateur de fin de liste 

// global initialization
first = NULL;                              // before the first insertion (not shown)

struct sll_node *Search(struct sll_node *first, int search_key) {
    struct sll_node *node;
    for (node = first; 
        node != NULL; 
        node = node->next)
    {
        if (node->key == search_key)
            return node;                   // found
    }
    // search_key is not contained in the list:
    return NULL;
}

Le for -loop contient deux tests (lignes jaunes) par itération:

  • node != NULL;
  • if (node->key == search_key) .

Deuxième version utilisant un nœud sentinelle

Le pointeur disponible dans le monde entier sentinel vers la structure de données délibérément préparée Sentinel est utilisé comme indicateur de fin de liste. 

// global variable
sll_node Sentinel, *sentinel = &Sentinel;
// global initialization
sentinel->next = sentinel;
first = sentinel;                          // before the first insertion (not shown)

Notez que le pointeur sentinelle doit toujours être conservé à la fin de la liste. Ceci doit être maintenu par les fonctions d'insertion et de suppression. Il s'agit cependant du même effort que lors de l'utilisation d'un pointeur NULL. 

struct sll_node *SearchWithSentinelnode(struct sll_node *first, int search_key) {
    struct sll_node *node;
    // Prepare the “node” Sentinel for the search:
    sentinel->key = search_key;
    for (node = first; 
        node->key != search_key; 
        node = node->next)
    {}
 
    // Post-processing:
    if (node != sentinel)
        return node;                       // found
    // search_key is not contained in the list:
    return NULL;
}

Le for -loop ne contient qu'un seul test (ligne jaune) par itération:

  • node->key != search_key; .

Implémentation Python d'une liste circulaire à double lien

Les implémentations de listes liées, en particulier celles d'une liste circulaire à double lien, peuvent être remarquablement simplifiées en utilisant un nœud sentinelle pour délimiter le début et la fin de la liste.

  • La liste commence par un seul nœud, le nœud sentinelle qui a les pointeurs suivant et précédent pointent vers lui-même. Cette condition détermine si la liste est vide.
  • Dans une liste non vide, le pointeur suivant du nœud sentinelle donne la tête de la liste et le pointeur précédent donne la queue de la liste.

Voici une implémentation Python d'une liste circulaire à double lien: 

class Node:
    def __init__(self, data, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev

    def __repr__(self) -> str:
        return f'Node(data={self.data})'

class LinkedList:
    def __init__(self):
        self._sentinel = Node(data=None)
        self._sentinel.next = self._sentinel
        self._sentinel.prev = self._sentinel

    def pop_left(self) -> Node:
        return self.remove_by_ref(self._sentinel.next)

    def pop(self) -> Node:
        return self.remove_by_ref(self._sentinel.prev)

    def append_nodeleft(self, node):
        self.add_node(self._sentinel, node)

    def append_node(self, node):
        self.add_node(self._sentinel.prev, node)

    def append_left(self, data):
        node = Node(data=data)
        self.append_nodeleft(node)

    def append(self, data):
        node = Node(data=data)
        self.append_node(node)

    def remove_by_ref(self, node) -> Node:
        if node is self._sentinel:
            raise Exception('Can never remove sentinel.')
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node

    def add_node(self, curnode, newnode):
        newnode.next = curnode.next
        newnode.prev = curnode
        curnode.next.prev = newnode
        curnode.next = newnode

    def search(self, value):
        self._sentinel.data = value
        node = self._sentinel.next
        while node.data != value:
            node = node.next
        self._sentinel.data = None
        if node is self._sentinel:
            return None
        return node

    def __iter__(self):
        node = self._sentinel.next
        while node is not self._sentinel:
            yield node.data
            node = node.next

    def reviter(self):
        node = self._sentinel.prev
        while node is not self._sentinel:
            yield node.data
            node = node.prev

Remarquez comment la add_node() méthode prend le nœud qui sera déplacé par le nouveau nœud dans le paramètre curnode . Pour l'ajout à gauche, c'est la tête d'une liste non vide, tandis que pour l'ajout à droite, c'est la queue. Mais à cause de la façon dont le lien est configuré pour renvoyer à la sentinelle, le code fonctionne également uniquement pour les listes vides, où curnode sera le nœud sentinelle.

Rechercher dans un arbre binaire

Déclarations générales, similaires à l'article Arbre de recherche binaire : 

struct bst_node {                     // one node of the binary search tree
    struct bst_node *child[2];        // each: ->node  or  end-of-path indicator
    int key;
} ;

struct bst {                          // binary search tree
    struct bst_node *root;            // ->node  or  end-of-path indicator
} *BST;

Le pointeur globalement disponible sentinel vers la structure de données unique délibérément préparée Sentinel = *sentinel est utilisé pour indiquer l'absence d'un enfant. 

// global variable
bst_node Sentinel, *sentinel = &Sentinel;
// global initialization
Sentinel.child[0] = Sentinel.child[1] = sentinel;

BST->root = sentinel;                 // before the first insertion (not shown)

Notez que le pointeur sentinelle doit toujours représenter chaque feuille de l'arbre. Ceci doit être maintenu par les fonctions d'insertion et de suppression. Il s'agit cependant du même effort que lors de l'utilisation d'un pointeur NULL. 

struct bst_node *SearchWithSentinelnode(struct bst *bst, int search_key) {
    struct bst_node *node;
    // Prepare the “node” Sentinel for the search:
    sentinel->key = search_key;
 
    for (node = bst->root;;) {
        if (search_key == node->key)
            break;
        if search_key < node->key:
            node = node->child[0];    // go left
        else
            node = node->child[1];    // go right
    }
 
    // Post-processing:
    if (node != sentinel)
        return node;                  // found
    // search_key is not contained in the tree:
    return NULL;
}
Remarques
  1. Avec l'utilisation de SearchWithSentinelnode, la recherche perd la propriété R / O. Cela signifie que dans les applications avec concurrence, il doit être protégé par un mutex , un effort qui dépasse normalement les économies de la sentinelle.
  2. SearchWithSentinelnode ne prend pas en charge la tolérance des doublons.
  3. Il doit y avoir exactement un «nœud» pour être utilisé comme sentinelle, mais il peut y avoir extrêmement de pointeurs vers celui-ci.

Voir également

Les références

  1. ^ Ignatchenko, Sergey (1998), "Implémentations STL et sécurité des threads", rapport C ++