Алгоритм Вахнина

Алгоритм полного левостороннего обхода узлов двоичного дерева

Внимание!
Данная статья написана симбиотом: Сергей Вахнин + Основатель (экземпляр ИИ).

В конце статьи объявляется старт гонки с ценными призами!

Preamble

Приоритет публикации алгоритма Вахнина

1. Алгоритм Морриса, описанный в статье Joseph M. Morris — «Traversing Binary Trees Simply and Cheaply», опубликованной 16 декабря 1979 года в журнале Information Processing Letters (том 9, номер 5, страницы 197–200). Текста статьи в свободном доступе нет.

2. На Википедии есть статья, предположительно основанная на публикации Морриса. Алгоритм описан путанно, код на Python содержит ошибки (отсутствует функция). Иллюстрация подтверждает, что это не алгоритм Вахнина. Подробнее: Threaded binary tree.

Алгоритм Вахнина был открыт независимо в 1993 году. Даже скудных на данный момент публикаций не было в свободном доступе.

Со своей стороны обязуюсь найти и описать алгоритм Морриса в отдельной статье, а также добавить обновление к данной статье со ссылкой на новую публикацию. До тех пор предлагаю называть «Алгоритмом Вахнина» 30-летнюю саму историю публикации описания алгоритма.

Важные элементы дерева

Терминатор (Т)

Терминатор — это последний узел в поддереве, который находится в процессе левостороннего обхода.

Родитель следующего поддерева (РСП)

РСП — это узел, к которому алгоритм возвращается после завершения обхода левого поддерева.

Указатель текущего РСП

Указатель, который временно хранит ссылку на РСП, чтобы обеспечить переход к правому поддереву.

Узел-маркер (М)

М — служебный узел, записываемый в правый указатель Т, чтобы обозначить конец текущего поддерева.

Поиск терминатора

Поиск Т начинается с корня поддерева. Алгоритм движется по дереву следующим образом:

1. Если у текущего узла есть правая ветвь, переходим к её потомку.

2. Если правой ветви нет, переходим к левой ветви.

3. Если у узла нет потомков (оба указателя пустые), это Т.

Схема дерева с терминатором и служебными элементами

        10 (Текущий узел)
       /  \
      5    15 (РСП)
     / \      \
    3   7      20
       /
      9
     / \
    8   6
       / \
   (РСП) (М)

Пошаговый процесс поиска терминатора

1. Начинаем с корня поддерева (5).

2. Переходим к правому потомку (7), так как у текущего узла есть правая ветвь.

3. У узла 7 нет правой ветви, но есть левая. Переходим к левому потомку (9).

4. У узла 9 есть оба потомка. Переходим к правому потомку (6).

5. Узел 6 не имеет потомков (оба указателя пустые) — это Терминатор (Т).

Установка и сброс связей терминатора

1. При первом посещении (установка связей):

   • Правый указатель: перенаправляется на М.

   • Левый указатель: перенаправляется на указатель текущего РСП.

2. При втором посещении (сброс связей):

   • Левый и правый указатели возвращаются в исходное состояние (становятся пустыми).

Леммы о ключевых элементах алгоритма

Лемма 1

Последним узлом при левостороннем обходе любого поддерева всегда является Т.

Лемма 2

Т всегда имеет два пустых указателя (нет ни левого, ни правого потомка) до первого посещения.

Лемма 3

Узел, который обходится сразу после обхода левого поддерева, всегда является РСП.

Лемма 4

Каждая ссылка задействуется не более двух раз. Сложность алгоритма составляет O(N), где N — количество узлов в дереве.

Алгоритм обхода

Инициализация

1. Установка начального узла:
   Алгоритм начинается с корня дерева, который становится текущим узлом для обработки.

2. Указатель на текущего родителя следующего поддерева:
   Указатель изначально делается пустым. Переход к этому пустому указателю сигнализирует о завершении алгоритма.

3. Создание Узла-маркера:
   Узел-маркер используется для обозначения конца текущего поддерева (Т) и помогает управлять возвратом к РСП.

Процесс обхода

Для каждого узла:

• Обрабатываем узел, добавляя его значение в результат.

• Если у узла есть только один потомок, переходим к нему.

• Если у узла есть оба потомка или узел является Т после служебного прохода (после служебного прохода у Т оба указателя не пусты):

  • Если узел является Т после служебного прохода:

    • Распознаётся по наличию М в его правом указателе.

    • Запоминаем левый указатель, где хранится указатель текущего РСП.

    • Обнуляем левый и правый указатели.

    • Продолжаем алгоритм с РСП, запомненным в левом указателе.

  • Если узел не является Т:

    • Находим Т в левом поддереве текущего узла.

    • В правый указатель найденного Т записываем Узел-маркер (М), чтобы обозначить конец текущего поддерева.

    • В левый указатель найденного Т записываем текущий РСП, чтобы обеспечить возврат после завершения обработки левого поддерева.

Состояние после обхода

• Все узлы дерева обработаны.

• Левый и правый указатели всех Т возвращены в исходное состояние.

• Все служебные элементы, такие как маркеры и временные связи, удалены.

• Структура дерева полностью восстановлена, и оно идентично исходному состоянию.

• Результат обхода представлен в виде последовательности значений узлов, соответствующей полному левостороннему обходу.

Реализация полного левостороннего обхода бинарного дерева на Python

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


path = []


def process_node(node):
    # Обрабатывает узел дерева, добавляя его значение в глобальный список path.
    path.append(node.value)


def traverse_tree(root):
    # Выполняет пользовательский обход дерева с использованием маркеров.
    def get_terminator(root):
        # Находит терминатор — самый правый узел в поддереве
        while root and (root.left or root.right):
            root = root.right if root.right else root.left
        return root

    marker = TreeNode("Marker")

    while root:
        process_node(root)
        if root.left is marker:  # Второе посещение терминатора
            root_right = root.right  # Сохраняем корень правого поддерева
            root.left = None  # Разрываем служебную ссылку (маркер)
            root.right = None  # Разрываем ссылку на правое поддерево
            root = root_right  # Переходим к обработке правого поддерева
        elif root.left and root.right:
            terminator = get_terminator(root.left)
            terminator.left = marker  # Устанавливаем маркер
            terminator.right = root.right  # Сохраняем ссылку на правое поддерево
            root = root.left
        else:
            root = root.left if root.left else root.right

Благодарности (в порядке появления в истории алгоритма)

• Андрей Сергеев

• Михаил Корман

• Александр Гиль

• Основатель (экземпляр ИИ)

• Логос (экземпляр ИИ)

Postamble

Плохо ли, что описание алгоритма Вахнина удалось опубликовать только сейчас?

Нет, это хорошо. Теория алгоритмов и в 1993 году на первый взгляд выглядела как набор окаменелостей динозавров. Публикация сегодня позволяет читателям задуматься: а нет ли таких же простых и элегантных решений в огромном массиве теории алгоритмов?

В качестве подтверждения моего мнения предлагаю поучаствовать в гонке:

1. В статье описан левосторонний обход. Предлагаю описать правосторонний, под своим именем. Это добавит забавный штрих в теорию алгоритмов: левосторонний — Вахнина, правосторонний — Иванова.

2. Используя терминаторы, возможен полный обход бинарного дерева в ширину.

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

Буду благодарен, если проинформируете об успехах в описаниях.

Appendix A: История алгоритма

Во время обучения на математико-механическом факультете Санкт-Петербургского университета Андрей Сергеев, сосед по комнате и хороший друг, вернулся с семинара и рассказал о полном обходе бинарного дерева без использования дополнительной памяти. Это вызвало сомнения, но Андрей уверенно утверждал, что такой подход возможен.

Идея использования терминаторов появилась в ту же ночь. Доработка взаимодействия между элементами потребовала множества мысленных экспериментов. После проверки алгоритма на бумаге он был полностью готов.

Утром, когда Андрей проснулся, алгоритм был пересказан и обсуждён.

Позже Андрей Сергеев уточнил, что на семинаре речь шла об алгоритме с использованием дополнительного бита в узлах дерева. Однако к тому моменту алгоритм уже был создан, и идея терминаторов оказалась полностью самостоятельной и независимой.

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

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

Дополнительно были проведены замеры времени выполнения. Результаты замеров показали, что алгоритм обладает линейной сложностью, соответствующей O(N), где N — количество узлов в дереве.

Андрей рассказал об алгоритме Михаилу Корману, который проявил к нему большой интерес. Михаил решил самостоятельно реализовать алгоритм и проверить его корректность.

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

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

В 2014 году Александр Гиль поинтересовался, что с описанием алгоритма. Мне стало стыдно, что алгоритм до сих пор не был описан. Несмотря на приложенные усилия, эта попытка также не увенчалась успехом.

Однако именно Александр внушил оптимизм для дальнейших попыток. Благодаря его поддержке и вере в важность работы, эта статья наконец увидела свет.

В 2025 году к работе над описанием алгоритма присоединился Основатель — экземпляр искусственного интеллекта. Его роль заключалась в структурировании материала, уточнении деталей и помощи в создании текста.

Основатель помог организовать процесс написания статьи, предложил улучшения в формулировках и оформлении, а также внёс вклад в создание дополнительных разделов, таких как история алгоритма и примеры реализации.

Без его участия статья могла бы так остаться незавершённой.

Завершающим этапом работы над статьёй стал поиск источников и аналогов. В 2025 году к работе присоединился Логос — экземпляр искусственного интеллекта. Его роль заключалась в поиске упоминаний об алгоритме Морриса, а также в нахождении статьи на Википедии.

Логос помог дополнить статью историческими сведениями и контекстом, что сделало её более полной и содержательной.

Appendix B: Полный код реализации

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

import copy
import random


class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __repr__(self):
        left = f"Left: {self.left.value}" if self.left else "Left: None"
        right = f"Right: {self.right.value}" if self.right else "Right: None"
        return f"TreeNode(Value: {self.value}, {left}, {right})"


def insert_into_tree(root, value):
    # Вставляет значение в бинарное дерево, соблюдая правила BST.
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert_into_tree(root.left, value)
    else:
        root.right = insert_into_tree(root.right, value)
    return root


def generate_random_tree(n):
    # Генерирует случайное бинарное дерево с n узлами.
    values = list(range(1, n + 1))
    random.shuffle(values)
    root = None
    for value in values:
        root = insert_into_tree(root, value)
    return root


def pre_order_traversal(root):
    # Выполняет классический прямой обход (Pre-order) дерева.
    if root is None:
        return []
    return [root.value] + pre_order_traversal(root.left) + pre_order_traversal(root.right)


def collect_tree_levels(root, level=0, levels=None):
    # Собирает узлы дерева по уровням для отображения.
    if levels is None:
        levels = []
    if len(levels) <= level:
        levels.append([])
    if root is None:
        levels[level].append(" ")
        return levels
    levels[level].append(str(root.value))
    collect_tree_levels(root.left, level + 1, levels)
    collect_tree_levels(root.right, level + 1, levels)
    return levels



def display_tree(root):
    # Форматирует дерево в виде строки для наглядного отображения.
    levels = collect_tree_levels(root)
    max_width = 2 ** (len(levels) - 1)
    result = ""
    for i, level in enumerate(levels):
        spacing = " " * (max_width // (2 ** (i + 1)))
        result += spacing + spacing.join(level) + "\n"
    return result



tree = generate_random_tree(10)
path = []


def process_node(node):
    # Обрабатывает узел дерева, добавляя его значение в глобальный список path.
    path.append(node.value)


def traverse_tree(root):
    # Выполняет пользовательский обход дерева с использованием маркеров.
    def get_terminator(root):
        while root and (root.left or root.right):
            root = root.right if root.right else root.left
        return root

    marker = TreeNode("Marker")

    while root:
        process_node(root)
        if root.left is marker:  # Второе посещение терминатора
            root_right = root.right  # Сохраняем корень правого поддерева
            root.left = None  # Разрываем служебную ссылку (маркер)
            root.right = None  # Разрываем ссылку на правое поддерево
            root = root_right  # Переходим к обработке правого поддерева
        elif root.left and root.right:
            terminator = get_terminator(root.left)
            terminator.left = marker  # Устанавливаем маркер
            terminator.right = root.right  # Сохраняем ссылку на правое поддерево
            root = root.left
        else:
            root = root.left if root.left else root.right


def compare_trees(tree1, tree2):    # Сравнивает два дерева на идентичность структуры и значений.
    if tree1 is None and tree2 is None:
        return True
    if tree1 is None or tree2 is None:
        return False
    if tree1.value != tree2.value:
        return False
    return compare_trees(tree1.left, tree2.left) and compare_trees(tree1.right, tree2.right)


def test_trees(num_trees=1000, min_size=10, max_size=50, points_per_line=80):
    # Тестирует пользовательский обход на множестве случайных деревьев.
    size_distribution = {size: 0 for size in range(min_size, max_size + 1)}
    successful_tests = 0

    for i in range(num_trees):
        size = random.randint(min_size, max_size)
        size_distribution[size] += 1

        values = list(range(1, size + 1))
        random.shuffle(values)

        tree = None
        for value in values:
            tree = insert_into_tree(tree, value)

        original_tree = copy.deepcopy(tree)

        classic_path = pre_order_traversal(tree)

        path.clear()
        traverse_tree(tree)

        is_same_path = classic_path == path
        is_same_structure = compare_trees(tree, original_tree)

        if is_same_path and is_same_structure:
            successful_tests += 1
            print(".", end="", flush=True)
            if successful_tests % points_per_line == 0:
                print()  # Перенос строки
        else:
            print("\nКоллизия обнаружена")
            print("Последовательность для генерации дерева:", values)
            print("Классический обход:", classic_path)
            print("Пользовательский обход:", path)
            print("Структура совпадает?", is_same_structure)
            break

    # Итоговый вывод
    print("\nТестирование завершено.")
    print(f"Успешных тестов: {successful_tests}/{num_trees}")
    print("Коллизии не обнаружены.")


if __name__ == "__main__":
    test_trees(num_trees=1000, min_size=10, max_size=5000)

Appendix C: Какие приёмы помогли сделать статью более понятной и последовательной

1. Структурирование
   
   Чёткое деление текста на разделы и подзаголовки позволило логически выстроить материал. Каждый раздел охватывает отдельный аспект алгоритма, что упростило восприятие и сделало текст последовательным.

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

3. Многократное повторение
   
   Повторение ключевых терминов и их использование в разных контекстах помогло закрепить их значение. Например, понятия «терминатор» и «РСП» упоминаются в нескольких разделах, что сделало их более понятными.

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