Дозорный узел

Эта статья о конструкции компьютерного программирования. Чтобы узнать о части тела, см. Сторожевой лимфатический узел .

Не путать со сторожевым значением .

В компьютерном программировании сторожевой узел — это специально назначенный узел, используемый со связанными списками и деревьями в качестве терминатора пути обхода. Этот тип узла не содержит и не ссылается на какие-либо данные, управляемые структурой данных.

Преимущества

Стражи используются в качестве альтернативы использованию NULL в качестве терминатора пути, чтобы получить одно или несколько из следующих преимуществ:

• Незначительно увеличена скорость операций
• структуры данных Повышенная надежность (возможно)

Недостатки

• Незначительно увеличена алгоритмическая сложность и размер кода.
• Если доступ к структуре данных осуществляется одновременно (это означает, что все узлы, к которым осуществляется доступ, должны быть защищены как минимум для «только чтения» ), для реализации на основе дозорного узла дозорный узел должен быть защищен для «чтения-записи» с помощью мьютекс . Этот дополнительный мьютекс во многих сценариях использования может привести к серьезному снижению производительности. Один из способов избежать этого — защитить структуру списка в целом для «чтения-записи», тогда как в версии с NULL достаточно защитить структуру данных в целом для «только чтения» (если не последует операция обновления).
• Концепция дозорного бесполезна для записи структуры данных на диск.

Примеры

Поиск в связанном списке

Ниже приведены две версии подпрограммы (реализованной на языке программирования C ) для поиска заданного ключа поиска в односвязном списке . Первый использует сторожевое значение NULL, а второй - (указатель на) сторожевой узел Sentinel, как индикатор конца списка. Объявления структуры данных односвязного списка и результаты обеих подпрограмм одинаковы.

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;

Первая версия, использующая NULL в качестве индикатора конца списка.

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

The for-loop содержит два теста (желтые линии) на итерацию:

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

Вторая версия с использованием сторожевого узла

Глобально доступный указатель sentinel к намеренно подготовленной структуре данных Sentinel используется как индикатор конца списка.

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

Обратите внимание, что указатель- сторож всегда должен находиться в конце списка. Это должно поддерживаться функциями вставки и удаления. Однако это требует примерно тех же усилий, что и при использовании 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;
}

The for-loop содержит только один тест (желтая линия) на итерацию:

• node->key != search_key;.

Реализация циклического двусвязного списка на Python

Реализации связанных списков, особенно циклических двусвязных списков, можно значительно упростить, используя сторожевой узел для разграничения начала и конца списка.

• Список начинается с одного узла — сторожевого узла, у которого указатели next и previous указывают на себя. Это условие определяет, пуст ли список.
• В непустом списке следующий указатель сторожевого узла дает начало списка, а предыдущий указатель дает конец списка.

Ниже приведена реализация циклического двусвязного списка на языке Python:

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

Обратите внимание, как add_node() метод принимает в параметре узел, который будет смещен новым узлом curnode. При добавлении слева это заголовок непустого списка, а при добавлении справа — хвост. Но из-за того, как настроена связь для обратной ссылки на дозорный, код работает и для пустых списков, где curnode будет сторожевым узлом.

Поиск в бинарном дереве

Общие объявления, аналогичные статье Бинарное дерево поиска :

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;

Глобально доступный указатель sentinel к единой сознательно подготовленной структуре данных Sentinel = *sentinel используется для обозначения отсутствия ребенка.

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

Обратите внимание, что страж -указатель всегда должен представлять каждый лист дерева. Это должно поддерживаться функциями вставки и удаления. Однако это требует примерно тех же усилий, что и при использовании 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;
}

Примечания

1. При использовании SearchWithSentinelnode поиск теряет свойство «только для чтения» . Это означает, что в приложениях с параллелизмом он должен быть защищен мьютексом , а усилия, которые обычно превышают экономию дозорного.
2. SearchWithSentinelnode не поддерживает допуск дубликатов.
3. Должен быть ровно один «узел», который будет использоваться в качестве дозорного, но указателей на него может быть очень много.

См. также

• Канарская ценность
• Слон в Каире
• Guard (информатика) — логическое выражение, которое должно иметь значение true, если выполнение программы должно продолжаться в рассматриваемой ветке.
• Магическое число (программирование)
• Волшебная строка
• Шаблон нулевого объекта
• Полупредикатная задача
• Дозорное значение
• Ошибки форматирования и хранения времени