Деревья, кучи и графы — Примеры

Пример 1 — Дерево поиска, ставшее списком

Записи приходят уже отсортированными по id и вставляются в этом же порядке в простое двоичное дерево поиска, без перебалансировки; как выглядят первые четыре вставки, показывает трассировка. Скажите, какую форму дадут десять записей и чего будет стоить один поиск, а затем — что здесь изменить.

вставка 10 -> корень
вставка 20 -> 20 > 10, правый потомок 10
вставка 30 -> 30 > 10 -> вправо -> 30 > 20 -> правый потомок 20
вставка 40 -> 40 > 10, 20, 30 -> правый потомок 30

        10
          \
           20
             \
              30
                \
                 40

Решение

форма: у каждого узла есть правый потомок и нет левого — путь
поиск десятой записи: 10 сравнений, по одному на узел
исправление: самобалансирующееся дерево или перемешать вход перед вставкой

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

Пример 2 — Обход, который никогда не завершается

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

граф: A -> B, B -> C, C -> A   (цикл),  A -> D
старт: A

queue = [A]
while queue not empty:
    node = queue.pop front
    if node in visited: continue
    visited.add(node)
    queue.extend(node.neighbours)

Решение

цикл заново ставит A, B и C в очередь вечно: каждый узел попадает
в очередь по разу на каждого соседа, который до него доходит, а
проверка происходит только при выходе из очереди.

queue = [start]
visited = {start}
while queue not empty:
    node = queue.pop front
    for n in node.neighbours:
        if n not in visited:
            visited.add(n)
            queue.append(n)

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