Sentinel node - Sentinel node

I computerprogrammering er en sentinel node en specifikt udpeget node, der bruges sammen med sammenkædede lister og træer som en traversal path terminator. Denne type knude indeholder eller henviser ikke til data, der administreres af datastrukturen.

Fordele

Sentinels bruges som et alternativ til at bruge NULL som sti-terminator for at få en eller flere af følgende fordele:

• Marginalt øget hastighed
• Øget robusthed i datastrukturen (uden tvivl)

Ulemper

• Marginalt øget algoritmisk kompleksitet og kodestørrelse.
• Hvis der er adgang til datastrukturen samtidigt (hvilket betyder, at alle noder, der er adgang til, skal beskyttes mindst for "skrivebeskyttet" ), for en sentinelbaseret implementering skal sentinel-noden beskyttes for "read-skriv" af en mutex . Denne ekstra mutex i ganske få brugsscenarier kan forårsage alvorlig ydelsesforringelse. En måde at undgå det på er at beskytte listestrukturen som helhed for "read-write", mens der i versionen med NULL den er tilstrækkelig til at beskytte datastrukturen som helhed for "read-only" (hvis en opdateringshandling ikke følger ).
• Sentinel-konceptet er ikke nyttigt til registrering af datastrukturen på disken.

Eksempler

Søg på en linket liste

Nedenfor er to versioner af en underrutine (implementeret i C-programmeringssprog ) til at slå en given søgetast op på en enkelt linket liste . Den første bruger sentinelværdien NULL , og den anden en (markør til) sentinel-noden Sentinel , som indikator for slutningen af ​​listen. Erklæringerne om den enkeltstående link datastruktur og resultatet af begge underrutiner er de samme.

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;

Første version med NULL som en indikator for slutningen af ​​listen

// 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;
}

Den for løkke indeholder to prøver (gule linjer) pr iteration:

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

Anden version ved hjælp af en sentinel node

Den globalt tilgængelige markør sentinel til den bevidst forberedte datastruktur Sentinel bruges som indikator for slutningen af ​​listen.

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

Bemærk, at markøren sentinel altid skal holdes i slutningen af ​​listen. Dette skal opretholdes af indsætnings- og sletningsfunktionerne. Det handler dog om den samme indsats, som når du bruger en NULL-markør.

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;
}

Den for løkke indeholder kun én test (gul linje) pr iteration:

• node->key != search_key; .

Python-implementering af en cirkulær dobbeltkoblet liste

Implementeringer af sammenkædede lister, især en af ​​en cirkulær, dobbeltkoblet liste, kan forenkles bemærkelsesværdigt ved hjælp af en sentinelknude til at afgrænse begyndelsen og slutningen af ​​listen.

• Listen starter med en enkelt knude, hvor sentinelknuden, der har den næste og forrige markør, peger på sig selv. Denne betingelse bestemmer, om listen er tom.
• På en ikke-tom liste angiver Sentinel-knudens næste markør hovedet på listen, og den forrige markør giver halen på listen.

Følgende er en Python-implementering af en cirkulær dobbeltkoblet liste:

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

Læg mærke til, hvordan add_node() metoden tager den node, der vil blive forskudt af den nye node i parameteren curnode . For at tilføje til venstre er dette hovedet på en ikke-tom liste, mens det for at tilføje til højre er halen. Men på grund af hvordan koblingen er indstillet til at henvise til sentinel, fungerer koden bare også for tomme lister, hvor curnode sentinelnoden vil være.

Søg i et binært træ

Generelle erklæringer svarende til artiklen Binært søgetræ :

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;

Den globalt tilgængelige markør sentinel til den enkelt bevidst forberedte datastruktur Sentinel = *sentinel bruges til at indikere fraværet af et barn.

// 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)

Bemærk, at markøren sentinel altid skal repræsentere hvert blad i træet. Dette skal opretholdes af indsætnings- og sletningsfunktionerne. Det handler dog om den samme indsats, som når du bruger en NULL-markør.

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;
}

Bemærkninger

1. Ved brug af SearchWithSentinelnode-søgning mister R / O- ejendommen. Dette betyder, at det i applikationer med samtidighed skal beskyttes af en mutex , en indsats, der normalt overstiger sentinelens besparelser.
2. SearchWithSentinelnode understøtter ikke tolerance for duplikater.
3. Der skal være nøjagtigt en "node", der skal bruges som sentinel, men der kan være ekstremt mange henvisninger til den.

Se også

• Sentinel værdi
• Magisk nummer (programmering)
• Magisk streng
• Nul objekt mønster
• Tidsformatering og opbevaring af fejl
• Elefant i Kairo
• Kanariske værdi
• Semipredikatproblem

Referencer