Деревья: бинарные деревья поиска, балансировка, map/set на их основе

Введение

В статьях SQL-цикла упоминала B-tree индексы СУБД — в этой статье разберём похожую по духу, но более общую структуру данных программирования: бинарные деревья поиска, лежащие в основе std::map/std::set (в отличие от хеш-таблиц unordered_map/unordered_set, дающих упорядоченный, а не произвольный порядок элементов).

Концепция

Бинарное дерево поиска (BST) хранит элементы в узлах, организованных так, что для каждого узла все элементы в его левом поддереве меньше значения этого узла, а все элементы в правом поддереве больше — это даёт возможность находить элемент за O(log n) в сбалансированном дереве (на каждом шаге сравнения отсекается примерно половина оставшихся кандидатов, аналогично бинарному поиску), но несбалансированное дерево (например, построенное вставкой уже отсортированных данных подряд, без перебалансировки) может вырождаться практически в связный список с O(n) поиском. Сбалансированные деревья (красно-чёрные деревья, используемые в реализации std::map/std::set большинства стандартных библиотек) автоматически поддерживают примерно одинаковую глубину для всех путей от корня к листьям через перебалансировку при каждой вставке/удалении, гарантируя O(log n) даже в худшем случае, в отличие от обычного, несбалансированного BST.

Пример кода

// std::map — упорядоченная ассоциативная структура на основе сбалансированного дерева
#include <map>

std::map<QString, int> sortedWordCounts;
sortedWordCounts["qt"] = 5;
sortedWordCounts["cmake"] = 2;
sortedWordCounts["c++"] = 10;

for (const auto &[word, count] : sortedWordCounts) {
    qDebug() << word << ":" << count; // вывод ВСЕГДА в алфавитном порядке ключей —
                                        // гарантировано структурой дерева, в отличие от unordered_map
}

// Концептуальная, упрощённая реализация узла BST для иллюстрации принципа
struct TreeNode {
    int value;
    TreeNode *left = nullptr;
    TreeNode *right = nullptr;
};

bool searchBST(TreeNode *node, int target)
{
    if (!node) return false;
    if (node->value == target) return true;
    if (target < node->value) return searchBST(node->left, target);  // идём влево
    return searchBST(node->right, target);                            // идём вправо
    // На каждом шаге — ОДНО сравнение отсекает примерно половину оставшегося поддерева
}

// Демонстрация преимущества std::map для запросов диапазона — недоступного эффективно unordered_map
std::map<int, QString> eventsByTimestamp;
// ... заполнение событиями ...

auto from = eventsByTimestamp.lower_bound(1000); // первый элемент с ключом >= 1000
auto to = eventsByTimestamp.upper_bound(2000);   // первый элемент с ключом > 2000

for (auto it = from; it != to; ++it) {
    qDebug() << "Событие в диапазоне:" << it->first << it->second;
    // unordered_map НЕ предоставляет эффективного способа выполнить такой же запрос диапазона —
    // потребовался бы полный перебор ВСЕХ элементов с проверкой условия для каждого
}

Пояснения к коду

Перебор std::map всегда даёт элементы в порядке возрастания ключей — это прямое следствие структуры дерева (организованного именно по принципу «меньше слева, больше справа») и явно отличает map от unordered_map, не дающего никаких упорядоченных гарантий. searchBST демонстрирует базовый принцип поиска в дереве — на каждом шаге одно сравнение позволяет однозначно выбрать, в какое из двух поддеревьев двигаться дальше, отсекая другое поддерево целиком из рассмотрения, что и даёт логарифмическую сложность для сбалансированного дерева. lower_bound/upper_bound для запроса диапазона значений показывают практическую выгоду упорядоченной структуры map, недоступную эффективно для хеш-таблицы — структура дерева, поддерживающая порядок, естественно поддерживает эффективный поиск границ диапазона, тогда как хеш-таблица, не сохраняющая никакого порядка, может выполнить эквивалентный запрос только полным, неэффективным перебором всех элементов.

Подводные камни

Выбор std::map/std::set «по умолчанию» для задач, где порядок элементов не важен, и единственная реальная потребность — быстрый поиск по ключу — для такого случая unordered_map/unordered_set обычно показывает лучшую практическую производительность (O(1) в среднем случае против O(log n) для дерева), и упорядоченные структуры на основе деревьев стоит выбирать осознанно, именно когда порядок реально нужен (перебор в определённом порядке, эффективные запросы диапазона), а не как универсальный выбор по умолчанию для любой ассоциативной задачи.
Реализация собственного, несбалансированного BST для production-кода вместо использования стандартных, проверенных, сбалансированных реализаций (std::map/std::set) — концептуальный пример searchBST показывает принцип, но реальный, «наивный» BST без балансировки подвержен катастрофическому вырождению в O(n) при неудачном порядке вставки данных (например, уже отсортированные данные, вставленные подряд), и для практического использования стандартные, тщательно реализованные и автоматически балансируемые std::map/std::set почти всегда предпочтительнее самостоятельной реализации.
Игнорирование относительно высокой стоимости операций сбалансированного дерева по сравнению с хеш-таблицей — хотя O(log n) асимптотически хуже O(1), это не означает катастрофической разницы на практике для умеренных объёмов данных, но дерево обычно имеет более высокие константные издержки на операцию (более сложная логика балансировки, менее благоприятная для кеша процессора структура с разбросанными по памяти узлами) — для задач, где порядок действительно не нужен, разница в практической производительности в пользу хеш-таблицы может быть заметна.
Хранение в дереве (map/set) ключей пользовательского типа без корректно определённого оператора сравнения (operator<), необходимого для определения относительного порядка элементов в структуре дерева — в отличие от хеш-таблицы, требующей хеш-функцию и operator== , дереву нужен именно полный, согласованный оператор «меньше», и некорректно определённый (не образующий строгий слабый порядок — например, нарушающий транзитивность) оператор сравнения приводит к неопределённому поведению структуры дерева, включая возможную потерю элементов или бесконечные циклы при операциях.