Пустой узел

Пустой узел — это в теории узлов и теории кос, а также в программировании и вычислительной технике, термин, используемый для обозначения узла, не содержащего данных или не имеющего определённого значения. В зависимости от контекста, понятие может иметь различные трактовки: от математического объекта в теории узлов до элемента структуры данных в информатике.

Математическое определение (теория узлов)

В математике, в частности в теории узлов и теории кос, пустой узел (или тривиальный узел) — это узел, который можно непрерывно деформировать в окружность без самопересечений. Формально, это узел, изотопный стандартной окружности, вложенной в трёхмерное евклидово пространство. Пустой узел является базовым объектом изучения: он представляет собой простейший тип узла, не имеющий зацеплений или переплетений. В терминах теории кос пустой узел соответствует единичной косе, не содержащей переплетений.

Свойства

• Тривиальность: Пустой узел не является зацепленным или переплетённым; его можно развязать без разрыва или разрезания.
• Инварианты: Для пустого узла все инварианты (например, полином Александера, полином Джонса) принимают тривиальные значения. Полином Александера для пустого узла равен 1, полином Джонса — 1.
• Диаграмма: На диаграмме узла пустой узел изображается как простая замкнутая кривая без пересечений (например, окружность или овал).

Примеры

• В трёхмерном пространстве пустой узел может быть представлен как окружность, вложенная в плоскость.
• В теории кос пустой узел соответствует косе, состоящей из одной нити без переплетений.

Применение в программировании и структурах данных

В информатике и программировании пустой узел (или нулевой узел) — это элемент структуры данных (например, связанного списка, дерева, графа), который не содержит данных или ссылается на отсутствие значения. Пустой узел часто используется для обозначения конца списка, отсутствия дочерних элементов в дереве или для представления неопределённого состояния.

В связанных списках

В односвязных и двусвязных списках пустой узел (или null-узел) указывает на конец списка. Например, в реализации односвязного списка на языке C++ или Java, последний узел содержит указатель на nullptr (или null), что означает отсутствие следующего элемента. Пустой узел не хранит полезные данные и служит маркером завершения.

В деревьях

В бинарных деревьях поиска (BST) пустой узел (или null-узел) обозначает отсутствие левого или правого дочернего элемента. При вставке или удалении элементов пустые узлы могут быть заменены новыми узлами с данными. В некоторых реализациях (например, в красно-чёрных деревьях) пустой узел может быть представлен как специальный объект-лист, не содержащий данных.

В графах

В графах пустой узел может означать вершину, не имеющую инцидентных рёбер (изолированную вершину), или вершину, не содержащую данных. В некоторых алгоритмах (например, обход в глубину или ширину) пустые узлы могут быть пропущены.

В базах данных

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

Примеры реализации

• C++: Node* next = nullptr; — пустой узел в связанном списке.
• Python: None используется для обозначения отсутствия узла.
• Java: null в ссылках на объекты узлов.

Пустой узел в теории графов

В теории графов пустой узел (или изолированная вершина) — это вершина графа, не имеющая инцидентных рёбер. Такая вершина не соединена ни с одной другой вершиной графа. Пустые узлы часто рассматриваются как вырожденные случаи и могут быть исключены из анализа, если не требуется учёт изолированных компонент.

Свойства

• Степень: Степень пустого узла равна 0 (нет смежных рёбер).
• Компоненты связности: Пустой узел образует отдельную компоненту связности, состоящую из одной вершины.
• Примеры: В графе социальной сети пустой узел может соответствовать пользователю, не имеющему друзей.

Пустой узел в топологии и физике

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

В теории струн

В теории струн пустой узел может быть аналогом вакуумного состояния, не содержащего струн или других возбуждений. Однако это понятие является скорее метафорическим и не имеет строгого математического определения.

Критика и ограничения

Понятие «пустой узел» в разных областях может вызывать путаницу из-за многозначности термина. В математике пустой узел — это тривиальный объект, который часто игнорируется в исследованиях, так как не представляет интереса для изучения сложных узлов. В программировании пустой узел может приводить к ошибкам, если не обрабатывать его корректно (например, разыменование null-указателя). В базах данных пустой узел (NULL) может вызывать неоднозначность при запросах, так как NULL не равен ни одному значению, включая себя.

Интересные факты

• В теории узлов пустой узел является единственным узлом, который можно развязать без разрезания верёвки.
• В программировании пустой узел часто используется в паттернах проектирования, таких как «Null Object», чтобы избежать проверок на null.
• В графовых базах данных пустые узлы могут быть удалены автоматически для оптимизации хранения.

Источники

• Адамс, К. «Теория узлов: введение» (1994).
• Кормен, Т. и др. «Алгоритмы: построение и анализ» (3-е издание, 2009).
• Грэхем, Р. и др. «Конкретная математика» (1994).
• Статья «Null node» в документации Neo4j (2020).
• Лекции по теории узлов, МГУ им. М. В. Ломоносова (2018).