Деревья

В массиве, связном списке, стеке и очереди элементы выстроены друг за другом. Однако файловая система на диске, структура HDF5-файла с результатами измерений, иерархия объёмов детектора в Geant4, дерево вызовов, собранное профилировщиком, устроены как иерархии. Для их описания существует отдельная структура данных — дерево.

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

Понятие дерева

Деревом называют набор узлов (вершин), соединённых рёбрами, в котором выполнены три условия:

есть один выделенный узел, корень (англ. root);
у каждого узла, кроме корня, в точности один родитель (англ. parent);
от корня до любого узла можно дойти по рёбрам, причём единственным способом, ведущим туда.

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

Основная терминология:

потомками (детьми) узла называют узлы, которым он приходится родителем;
листом (англ. leaf) называется узел без потомков;
внутренний узел имеет хотя бы одного потомка;
поддерево составляют узел вместе со всеми его потомками, потомками потомков и так далее; каждый узел можно считать корнем собственного поддерева, подвешенного под ним;
глубина узла равна числу рёбер, пройденных на пути от корня до узла (у корня глубина 0);
уровень объединяет узлы одной глубины;
высота дерева равна наибольшей глубине, найденной среди всех узлов.

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

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

Двоичные деревья и класс Node

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

В Python узел дерева описывается классом со ссылками на потомков, как элемент связного списка, только ссылок теперь две:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value  # данные, хранящиеся в узле
        self.left = left    # ссылка на левого потомка (или None)
        self.right = right  # ссылка на правого потомка (или None)

Соберём дерево из пяти узлов:

root = Node(5, Node(3, Node(1), Node(4)), Node(8))

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

Обходы дерева

Обойти дерево значит побывать в каждом узле по одному разу. В отличие от массива, у дерева есть несколько естественных порядков обхода. Они делятся на два семейства: обходы в глубину (DFS, англ. depth-first search), уходящие вниз по ветви, и обход в ширину (BFS, англ. breadth-first search), идущий по уровням.

Обходы в глубину

Обход в глубину сначала уходит по ветви до самого низа и только потом возвращается. Рекурсивная реализация тривиальна, а три классических варианта отличаются лишь моментом обработки самого узла относительно его поддеревьев:

def preorder(root):        # корень -> левое -> правое
    if root is None:
        return
    print(root.value)      # обрабатываем узел до потомков
    preorder(root.left)
    preorder(root.right)


def inorder(root):         # левое -> корень -> правое
    if root is None:
        return
    inorder(root.left)
    print(root.value)      # обрабатываем узел между потомками
    inorder(root.right)


def postorder(root):       # левое -> правое -> корень
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.value)      # обрабатываем узел после потомков

Для дерева, изображённого выше, preorder выведет 5 3 1 4 8, inorder выдаст 1 3 4 5 8, а postorder даст порядок 1 4 3 8 5.

Pre-order подходит для копирования и сериализации сверху вниз: сначала создаётся узел, затем его потомки. Post-order применяется для удаления и для вычислений снизу вверх, когда результат в узле зависит от значений, вычисленных в поддеревьях; так находят высоту, размер поддеревьев, значение арифметического выражения, разобранного в дерево. In-order выдаёт элементы дерева поиска в отсортированном порядке.

Обход в ширину

Обход в ширину идёт по уровням: сначала корень, затем все узлы глубины 1, затем глубины 2 и так далее. Рекурсией здесь не обойтись: требуется очередь из главы о базовых структурах:

from collections import deque


def level_order(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()      # берём узел из начала очереди
        print(node.value)
        if node.left:               # и ставим его потомков в конец
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Для того же дерева получится 5 3 8 1 4, по уровням. Любой обход посещает каждый узел по одному разу (обход в глубину вдобавок проходит по каждому ребру дважды, вниз и обратно), поэтому все они работают за \( O(n) \), где \( n \) — число узлов. Дополнительной памяти требуется \( O(h) \) на стек рекурсии у DFS (где \( h \) — высота дерева) и до \( O(n) \) на очередь у BFS, вмещающую самый широкий уровень.

Двоичное дерево поиска

Двоичным деревом поиска (англ. binary search tree, BST) называют двоичное дерево, в каждом узле которого выполняется свойство порядка: все значения в левом поддереве строго меньше значения узла, а все значения в правом строго больше.

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

def find(root, key):
    while root is not None and root.value != key:
        root = root.left if key < root.value else root.right
    return root  # узел с ключом key или None, если ключа нет

При вставке спуск выполняется так же, как при поиске, а новый узел подвешивается там, где спуск достиг None:

def insert(root, key):
    if root is None:
        return Node(key)          # нашли свободное место
    if key < root.value:
        root.left = insert(root.left, key)
    elif key > root.value:
        root.right = insert(root.right, key)
    return root                   # ключ уже есть — ничего не меняем

Поиск, вставка и удаление стоят \( O(h) \), поскольку проходят один путь от корня вниз. In-order-обход дерева поиска выдаёт ключи по возрастанию: сначала всё меньшее (левое поддерево), затем узел, затем всё большее. Получается структура, обеспечивающая одновременно быстрый поиск, вставку, удаление и перебор по порядку. Ни отсортированный массив с его медленной вставкой, ни хеш-таблица, лишённая порядка, этого не обеспечивают.

Сбалансированность

Эффективность BST определяется высотой \( h \), задающей цену любой операции. Если вставлять ключи в случайном порядке, \( h \approx \log_2 n \). Но если вставить ключи 1, 2, 3, ..., n по порядку, каждый новый узел уйдёт направо, и дерево выродится в связный список высоты \( n \). Все операции станут линейными.

Дерево называется сбалансированным, если у каждого узла высоты левого и правого поддеревьев отличаются не больше чем на единицу. У такого дерева \( h = O(\log n) \), а значит, все операции работают за \( O(\log n) \).

Сохранять сбалансированность при любых вставках и удалениях позволяют самобалансирующиеся деревья (АВЛ-дерево, красно-чёрное дерево), выполняющие после каждой операции небольшие локальные перестройки, называемые поворотами. Именно они стоят за std::map в C++ и TreeMap в Java, упомянутыми в главе про хеш-таблицы. В стандартной библиотеке Python дерева поиска нет, поскольку обычно достаточно dict, set и модуля bisect для отсортированного списка.

Куча

Куча (англ. heap) представляет собой структуру данных для задач, в которых требуется быстро находить максимум (или минимум) в наборе элементов, меняющемся в процессе работы. В невозрастающей куче (max-heap) выполняется основное свойство кучи: значение любого узла не меньше значений его потомков. Следовательно, в корне всегда находится максимум. В min-heap наоборот, в корне минимум.

В отличие от дерева поиска, куча не упорядочивает элементы полностью: между левым и правым поддеревьями никакого порядка нет. Взамен куча всегда остаётся почти полным двоичным деревом. Все уровни, кроме последнего, заполнены целиком, а последний заполняется слева направо по мере роста. Такое дерево не бывает вырожденным, и его высота всегда \( O(\log n) \).

Куча в массиве

Почти полное дерево хранится без ссылок, в обычном массиве, с узлами, выписанными по уровням:

Куча:                Массив:

      9              [9, 7, 8, 3, 1, 4]
     / \              0  1  2  3  4  5
    7   8
   / \  /
  3  1 4

У узла с индексом \( i \) потомки лежат в ячейках \( 2i + 1 \) и \( 2i + 2 \), а родитель в ячейке \( \lfloor (i-1)/2 \rfloor \). Классы и указатели не требуются: любой массив чисел уже представляет собой дерево, разложенное по уровням.

Куча основана на двух операциях, называемых просеиванием:

просеивание вверх (sift up): элемент, дописанный в конец массива, меняется местами с родителем, пока он больше родителя;
просеивание вниз (sift down): корень, ставший меньше потомков, меняется местами с бóльшим из них и опускается, пока свойство кучи не восстановится.

Оба просеивания проходят не больше одного пути от корня до листа, то есть стоят \( O(\log n) \). На них строится приоритетная очередь: добавление элемента за \( O(\log n) \), просмотр максимума за \( O(1) \), извлечение максимума (последний элемент переставляется в корень и просеивается вниз) за \( O(\log n) \).

В Python куча реализована модулем heapq как min-heap над обычным списком, передаваемым в функции модуля:

import heapq

distances = [5.2, 1.1, 3.7, 0.4]
heapq.heapify(distances)          # превращает список в кучу за O(n)
heapq.heappush(distances, 2.6)    # добавление за O(log n)
print(heapq.heappop(distances))   # 0.4 — минимум, за O(log n)

Если требуется max-heap, в куче хранят элементы с обратным знаком. Этот приём применяется в следующей главе, в алгоритме, строящем остовное дерево.

Пирамидальная сортировка

Куча даёт ещё один способ сортировать за \( O(n \log n) \), пирамидальную сортировку (англ. heap sort). Она состоит из двух этапов:

Превратить массив в max-heap, просеяв вниз все внутренние узлы, начиная с последнего и заканчивая корнем.
Повторять \( n - 1 \) раз: обменять корень (текущий максимум) с последним элементом ещё не отсортированной части и просеять новый корень вниз. Снятые максимумы один за другим встают в конец массива на окончательные места.

Дополнительной памяти heap sort, в отличие от сортировки слиянием, не требует: всё происходит в исходном массиве. Неудачных входов у него, в отличие от быстрой сортировки, не бывает: любой массив обрабатывается за \( O(n \log n) \). Платой являются неустойчивость и несколько большая константа, из-за которой на практике heap sort обычно немного медленнее quick sort. Полная реализация рассматривается ниже в задачах.

Деревья в физических задачах

Ниже приведены три типичных сюжета из вычислительной физики.

Поиск соседей и k-d деревья. В молекулярной динамике, методе SPH или при кластеризации точек, измеренных в эксперименте, постоянно требуется выяснять, какие частицы находятся рядом с выбранной. Перебор всех пар стоит \( O(N^2) \). k-d дерево (k-dimensional tree) рекурсивно делит пространство плоскостями пополам, и запрос ближайших соседей точки выполняется в среднем за \( O(\log N) \). В SciPy оно уже реализовано:

import numpy as np
from scipy.spatial import KDTree

points = np.random.rand(100_000, 3)      # частицы в единичном кубе
tree = KDTree(points)                    # построение за O(N log N)

dist, idx = tree.query(points[0], k=10)          # 10 ближайших соседей
neighbors = tree.query_ball_point(points[0], r=0.05)  # все соседи в радиусе

Гравитационная задача N тел и октодеревья. Прямое суммирование сил между \( N \) телами требует \( O(N^2) \) операций на шаг, что для галактики из миллиардов звёзд неприемлемо. Алгоритм Барнса — Хата строит октодерево (англ. octree): куб пространства, вмещающий всю систему, рекурсивно делится на 8 октантов, пока в каждом листе не останется по частице. Для далёкой группы частиц незачем суммировать вклады по одной, достаточно слагаемого от её суммарной массы, приложенной в центре масс и записанной в узле дерева. Критерий: если угловой размер ячейки \( s/d \) меньше порога \( \theta \), ячейка не раскрывается. Сложность снижается до \( O(N \log N) \), и такие деревья вместе с более сложным быстрым мультипольным методом работают внутри современных астрофизических кодов наподобие GADGET.

Иерархические данные. Формат HDF5, стандарт де-факто для больших численных данных, устроен как дерево: группы содержат подгруппы и датасеты, как каталоги и файлы. Деревом являются и геометрия детектора в Geant4 из объёмов, вложенных в объёмы, и символьное выражение в SymPy, где узлами служат операции, а листьями — переменные и константы. Иерархия почти наверняка означает, что в основе лежат дерево и рекурсивные обходы.

Разбор задач

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

Задача 1. Максимальная глубина

Условие. Дан корень двоичного дерева. Требуется найти его максимальную глубину, то есть наибольшее число узлов, лежащих на пути от корня до листа (включая корень и лист).

Идея решения. Глубина дерева равна глубине более глубокого из поддеревьев плюс единица за сам корень. Базовый случай — пустое дерево глубины 0.

def max_depth(root):
    # Базовый случай: пустое дерево не добавляет к глубине ничего
    if root is None:
        return 0
    # Более глубокое из поддеревьев плюс сам корень
    return 1 + max(max_depth(root.left), max_depth(root.right))

Сложность. По времени \( O(n) \), так как каждый узел посещается один раз. По памяти \( O(h) \) на стек рекурсии, где \( h \) — высота дерева.

Задача 2. Сбалансированное дерево

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

Идея решения. Прямолинейное решение: в каждом узле сравнивать высоты поддеревьев, вычисленные функцией из предыдущей задачи. Но тогда высота каждого узла будет вычисляться заново на каждом уровне выше него, и в худшем случае получится \( O(n^2) \).

Лучше совместить оба вычисления в одном обходе. Пусть функция возвращает высоту поддерева, а для несбалансированного поддерева значение-сигнал -1, немедленно передаваемое наверх без дальнейших проверок.

def check_height(root):
    """Высота поддерева или -1, если оно несбалансировано."""
    if root is None:
        return 0

    left = check_height(root.left)
    if left == -1:                 # слева уже нашли дисбаланс
        return -1

    right = check_height(root.right)
    if right == -1:                # справа уже нашли дисбаланс
        return -1

    if abs(left - right) > 1:      # дисбаланс в текущем узле
        return -1

    return 1 + max(left, right)


def is_balanced(root):
    return check_height(root) != -1

Сложность. По времени \( O(n) \): один post-order-обход, высота каждого узла вычисляется однократно. По памяти \( O(h) \) на стек рекурсии.

Задача 3. Дерево поиска

Условие. Требуется проверить, является ли двоичное дерево деревом поиска: значения, лежащие в левом поддереве каждого узла, строго меньше значения узла, а в правом строго больше.

Идея решения. Частая ошибка — проверять только соседние узлы: left.value < node.value < right.value. Этого недостаточно:

Дерево поиска:        Не дерево поиска:
      5                     5
     / \                   / \
    3   8                 3   8
   / \                   / \
  1   4                 1   6

В правом дереве узел 6 больше своего родителя 3, и локально условие выполнено. Однако 6 находится в левом поддереве корня 5, а значит, обязан быть меньше 5. Условие является глобальным: каждый узел ограничен всеми своими предками.

Будем спускаться по дереву и передавать вниз интервал разрешённых узлу значений \( (\text{low}, \text{high}) \). При переходе налево ужесточается верхняя граница значением узла, при переходе направо — нижняя.

def is_bst(root, low=float('-inf'), high=float('inf')):
    if root is None:
        return True
    # Значение узла обязано лежать строго внутри интервала предков
    if not (low < root.value < high):
        return False
    return (is_bst(root.left, low, root.value)      # слева всё < root.value
            and is_bst(root.right, root.value, high))  # справа всё > root.value

Альтернатива: выполнить in-order-обход и проверить, что выданные им значения идут строго по возрастанию. Для дерева поиска это является критерием.

Сложность. По времени \( O(n) \), по памяти \( O(h) \) на стек рекурсии.

Задача 4. Сколько существует деревьев поиска

Условие. Требуется определить, сколько различных двоичных деревьев поиска можно построить из всех чисел от 1 до \( n \). Число \( n \) не превосходит 20.

Идея решения. Выберем корнем число \( k \). Тогда числа \( 1, \dots, k-1 \) обязаны попасть в левое поддерево, а \( k+1, \dots, n \) в правое, причём каждое из поддеревьев само является деревом поиска. Число деревьев из \( m \) последовательных чисел зависит только от \( m \), поэтому получаем рекуррентность

\[ C_n = \sum_{k=1}^{n} C_{k-1} , C_{n-k}, \qquad C_0 = 1. \]

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

\[ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n! , (n+1)!}. \]

from math import comb


def count_bst(n):
    # Число Каталана: C(2n, n) / (n + 1), деление всегда нацело
    return comb(2 * n, n) // (n + 1)

Если формула неизвестна, ответ вычисляется по рекуррентности динамическим программированием:

def count_bst_dp(n):
    counts = [1] + [0] * n           # counts[0] = 1: пустое дерево одно
    for size in range(1, n + 1):
        for root in range(1, size + 1):
            # root - 1 чисел уходит налево, size - root — направо
            counts[size] += counts[root - 1] * counts[size - root]
    return counts[n]

Вычисления необходимо вести в целых числах. Наивное fac(2*n) / (fac(n) * fac(n+1)) считает через float с примерно 16 значащими цифрами, а промежуточный \( 40! \approx 8{,}16 \cdot 10^{47} \) точно в нём не представим. До \( n = 30 \) ответ всё же получается верным: ошибки в числителе и знаменателе компенсируют друг друга при делении. А \( C_{31} \) наивная формула уже занижает на единицу. Целочисленный вариант ничем не сложнее.

Сложность. Формула с биномиальным коэффициентом требует \( O(n) \) умножений; вариант с динамическим программированием обходится в \( O(n^2) \) операций и \( O(n) \) памяти.

Задача 5. Удаление узла из дерева поиска

Условие. Дано дерево поиска с уникальными целыми ключами. Требуется удалить узел с заданным ключом так, чтобы дерево осталось корректным деревом поиска, и вернуть корень изменённого дерева. Если ключа нет, дерево возвращается нетронутым. Создавать новые узлы нельзя, сложность должна быть \( O(h) \).

Идея решения. Спускаемся к удаляемому узлу, как при обычном поиске. Далее возможны три случая:

Если у узла нет потомков, он убирается, и родитель начинает ссылаться на None.
При одном потомке он подвешивается на место удаляемого узла.
При двух потомках находится преемник, минимальный узел правого поддерева (переход направо, затем налево до упора). Преемник больше всего левого поддерева и меньше остального правого, поэтому может встать на освободившееся место. Он вырезается со старого места, где у него нет левого потомка и работает случай 1 или 2, и переставляется наверх.

def remove(root, key):
    if root is None:                     # ключа в дереве нет
        return None

    if key < root.value:                 # ищем слева
        root.left = remove(root.left, key)
    elif key > root.value:               # ищем справа
        root.right = remove(root.right, key)
    else:                                # нашли узел с ключом key
        if root.left is None:            # случаи 1 и 2: нет левого потомка
            return root.right
        if root.right is None:           # случай 2: нет правого потомка
            return root.left

        # Случай 3: ищем преемника — минимум правого поддерева
        parent, succ = root, root.right
        while succ.left is not None:
            parent, succ = succ, succ.left

        # Вырезаем преемника со старого места...
        if parent.left is succ:
            parent.left = succ.right
        else:
            parent.right = succ.right

        # ...и ставим его на место удаляемого узла
        succ.left = root.left
        succ.right = root.right
        return succ

    return root

Сложность. По времени \( O(h) \), поскольку спуск к узлу и спуск к преемнику вместе образуют один путь от корня вниз. По памяти \( O(h) \) на рекурсию поиска (её несложно переписать циклом до \( O(1) \)).

Задача 6. Пирамидальная сортировка

Условие. По результатам соревнования дан список участников: логин, число решённых задач \( P \) и штраф \( F \). Требуется отсортировать таблицу: выше стоит участник, у которого больше решённых задач; при равенстве тот, у кого меньше штраф; если и штрафы равны, тот, чей логин идёт раньше по алфавиту. Кучу необходимо реализовать самостоятельно, встроенными сортировками и heapq пользоваться нельзя.

Ввод:                  Вывод:
5                      gena
alla 4 100             timofey
gena 6 1000            alla
gosha 2 90             gosha
rita 2 90              rita
timofey 4 80

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

def sort_key(user):
    login, solved, penalty = user
    return (-solved, penalty, login)

Остаётся отсортировать массив по этому ключу пирамидальной сортировкой. Строим max-heap в исходном массиве, затем раз за разом переставляем максимум, то есть худшего из оставшихся участников, в конец неотсортированной части:

def sift_down(items, start, end):
    """Просеивает элемент start вниз внутри items[start:end + 1]."""
    root = start
    while True:
        child = 2 * root + 1               # левый потомок
        if child > end:                    # потомков нет — дно кучи
            break
        # Из двух потомков выбираем большего
        if child + 1 <= end and sort_key(items[child]) < sort_key(items[child + 1]):
            child += 1
        if sort_key(items[root]) < sort_key(items[child]):
            items[root], items[child] = items[child], items[root]
            root = child                   # спускаемся за элементом дальше
        else:
            break                          # свойство кучи восстановлено


def heap_sort(items):
    n = len(items)
    # Этап 1: строим кучу — просеиваем все внутренние узлы справа налево
    for start in range((n - 2) // 2, -1, -1):
        sift_down(items, start, n - 1)
    # Этап 2: снимаем максимум с вершины кучи в конец массива
    for end in range(n - 1, 0, -1):
        items[0], items[end] = items[end], items[0]
        sift_down(items, 0, end - 1)


def main():
    n = int(input())
    users = []
    for _ in range(n):
        login, solved, penalty = input().split()
        users.append((login, int(solved), int(penalty)))

    heap_sort(users)

    print('\n'.join(user[0] for user in users))


if __name__ == '__main__':
    main()

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

Сложность. Построение кучи занимает \( O(n) \), поскольку низкие узлы просеиваются на малую глубину, а затем выполняются \( n - 1 \) просеиваний по \( O(\log n) \). Итого \( O(n \log n) \) по времени в худшем случае и \( O(1) \) дополнительной памяти: сортировка выполняется на месте. В рабочем коде достаточно sorted(users, key=sort_key).

Резюме

Дерево является рекурсивной структурой из корня и поддеревьев, каждое из которых само дерево. Базовый случай алгоритмов для него — пустое дерево None.
Обходы в глубину (pre-, in-, post-order) записываются рекурсией, обход в ширину — очередью, хранящей текущий уровень; все стоят \( O(n) \).
Дерево поиска обеспечивает поиск, вставку и удаление за \( O(h) \); чтобы высота \( h \) была \( O(\log n) \), дерево должно быть сбалансированным.
Куча укладывается в массив как почти полное дерево, отдаёт максимум за \( O(1) \), вставку и извлечение за \( O(\log n) \); на ней построены приоритетная очередь и heap sort.
В физических расчётах деревья ускоряют поиск соседей (k-d деревья), задачу N тел (октодеревья Барнса — Хата) и хранят иерархические данные в HDF5.

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

Разработка и применение программного обеспечения в физических исследованиях