2.3.2 — от указателя-цепочки к гарантированной высоте O(log n)2.3.2 — from a pointer chain to a guaranteed O(log n) height
Хеш-таблица (2.3.1) даёт O(1) доступ по ключу, но платит за это потерей порядка — нельзя быстро получить "следующий по величине" элемент или диапазон. Дерево поиска хранит элементы так, что порядок сохраняется, а поиск, вставка и удаление идут за время, пропорциональное высоте дерева. Здесь: от наивного бинарного дерева поиска, которое может выродиться в список, — через три способа удержать высоту O(log n) — к n-арным деревьям, оптимизированным под дисковый ввод-вывод, и к структурам, решающим вовсе другую задачу — быстрые агрегаты по диапазону.A hash table (2.3.1) gives O(1) access by key, but pays for it by losing order — there's no fast way to get the "next largest" element or a range. A search tree stores elements so that order is preserved, and search, insertion, and deletion take time proportional to the tree's height. Here: from a naive binary search tree that can degenerate into a list — through three ways to hold height at O(log n) — to n-ary trees optimized for disk I/O, and to structures solving a different problem entirely — fast range aggregates.
В дереве поиска каждая операция — поиск, вставка, удаление — идёт от корня вниз, делая один шаг на уровень. Значит, стоимость операции равна высоте дерева, а не числу хранимых элементов напрямую. Наивное дерево (BST) не следит за высотой вовсе: при неудачном порядке вставки (например, уже отсортированные данные) высота становится равна числу элементов — O(n) на операцию, как в связном списке. AVL, красно-чёрное и splay-деревья — три разных способа удержать высоту около log n, каждый со своим компромиссом между строгостью баланса и стоимостью его поддержания. B-дерево меняет саму единицу "шага": один узел — это не один ключ, а целая страница на диске, поэтому цель — не баланс как таковой, а минимальная высота при большом branching factor. Segment tree и дерево Фенвика вообще не хранят динамический набор ключей для поиска — они превращают массив в дерево агрегатов, чтобы отвечать на запросы по диапазону за O(log n) вместо O(n).In a search tree, every operation — search, insert, delete — walks from the root downward, one step per level. So an operation's cost equals the tree's height, not the number of stored elements directly. A naive tree (BST) doesn't track height at all: with an unlucky insertion order (e.g. already-sorted data), the height becomes equal to the element count — O(n) per operation, just like a linked list. AVL, red-black, and splay trees are three different ways to hold height near log n, each with its own trade-off between strictness of balance and the cost of maintaining it. A B-tree changes the very unit of a "step": one node isn't one key but an entire disk page, so the goal isn't balance per se but minimal height at a large branching factor. Segment trees and Fenwick trees don't store a dynamic key set for searching at all — they turn an array into a tree of aggregates, to answer range queries in O(log n) instead of O(n).
одна и та же цель — минимизировать число шагов от корня до листа — три разных источника цены: указатели, баланс, размер страницыthe same goal — minimize the number of steps from root to leaf — three different cost sources: pointers, balance, page size
Порядок карточек — от наивной идеи к трём способам её сбалансировать, затем к дереву, оптимизированному под диск, и наконец к двум структурам для запросов по диапазону, а не по ключу. Полный разбор — на отдельной странице по ссылке в названии.The card order goes from the naive idea to three ways of balancing it, then to a disk-optimized tree, and finally to two structures for range queries rather than key lookup. The full writeup is on its own page via the name link.
Первая карточка — наивный BST, база и повод для остальных трёх балансировок. Следующие три — AVL, красно-чёрное и splay-дерево — решают одну и ту же задачу (поддержать высоту около log n при вставках/удалениях), но с разными компромиссами: AVL строже всего и быстрее всего на чтении, красно-чёрное — дешевле на записи, splay вообще не хранит явный инвариант, полагаясь на структуру самих обращений. Пятая карточка — B-дерево — меняет саму модель стоимости: не число сравнений, а число обращений к странице памяти/диска. Последние две — segment tree и дерево Фенвика — решают другую задачу: не хранение множества ключей, а быстрый агрегат по диапазону массива.The first card is the naive BST, the baseline and the reason for the next three balancing acts. The next three — AVL, red-black, and splay tree — solve the same problem (holding height near log n under insertions/deletions), but with different trade-offs: AVL is strictest and fastest on reads, red-black is cheaper on writes, splay stores no explicit invariant at all, relying instead on the structure of the accesses themselves. The fifth card — B-tree — changes the cost model itself: not the number of comparisons, but the number of memory-page/disk accesses. The last two — segment tree and Fenwick tree — solve a different problem: not storing a key set, but a fast aggregate over an array range.
C++ std::map, Java TreeMap и планировщик Completely Fair Scheduler в ядре Linux используют красно-чёрные деревья именно потому, что вставка и удаление в них дешевле в среднем, чем в AVL, — а эти структуры подвергаются частым мутациям (новый процесс, завершение процесса) намного чаще, чем требуют идеально сбалансированного чтения.C++ std::map, Java's TreeMap, and the Linux kernel's Completely Fair Scheduler use red-black trees precisely because insertion and deletion are cheaper in them on average than in AVL — and these structures undergo frequent mutation (a new process, a process finishing) far more often than they need perfectly balanced reads.
Индексы InnoDB (MySQL) и стандартный B-tree-индекс PostgreSQL хранятся как B+Tree: высокий fanout укладывает всё дерево в 3-4 уровня даже для миллиардов строк, а связанные между собой листья дают эффективное последовательное сканирование диапазона — то, что не умеет ни хеш-индекс, ни обычное дерево поиска.InnoDB's (MySQL) indexes and PostgreSQL's default B-tree index are stored as a B+Tree: high fanout fits the whole tree into 3-4 levels even for billions of rows, and linked leaves give efficient sequential range scans — something neither a hash index nor an ordinary search tree can do.
Там, где нужна только сумма по префиксу/диапазону с точечными обновлениями, дерево Фенвика почти всегда предпочитают segment tree из-за втрое-вчетверо меньшего объёма кода и памяти — классическая находка для задач с ограничением по времени написания решения.Wherever only a prefix/range sum with point updates is needed, a Fenwick tree is almost always preferred over a segment tree for its three-to-four-times smaller code and memory footprint — a classic pick for time-constrained problem solving.
Системы бронирования переговорных, планировщики задач по времени и движки геометрических пересечений интервалов используют дерево отрезков для быстрого ответа "какой максимум занятости на этом отрезке времени" — обновление одного интервала и запрос по диапазону работают за O(log n) без пересчёта всей структуры.Meeting-room booking systems, time-based task schedulers, and interval-intersection geometry engines use segment trees to quickly answer "what's the peak occupancy over this time window" — updating one interval and querying a range both run in O(log n) without recomputing the whole structure.
До перехода на красно-чёрные деревья ядро Linux использовало splay-дерево для дерева областей виртуальной памяти процесса (VMA) — обращения к памяти обладают выраженной временной локальностью, и splay-дерево дёшево обслуживает именно недавно/часто используемые области. Похожая идея используется в некоторых сетевых ограничителях скорости, где активные потоки должны находиться дешевле неактивных.Before switching to red-black trees, the Linux kernel used a splay tree for a process's virtual-memory-area (VMA) tree — memory accesses have pronounced temporal locality, and a splay tree cheaply serves exactly the recently/frequently used regions. A similar idea shows up in some network rate limiters, where active flows must be found more cheaply than inactive ones.
Если ключи вставляются в уже отсортированном (или обратно отсортированном) порядке, наивное дерево поиска вырождается в связный список — каждый новый узел становится либо самым правым, либо самым левым потомком, высота становится равна n. Это не крайний теоретический случай: отсортированный ввод — обычное дело для логов, временных рядов и повторного построения индекса из выгрузки.If keys are inserted in already-sorted (or reverse-sorted) order, a naive search tree degenerates into a linked list — every new node becomes either the rightmost or leftmost child, and the height becomes equal to n. This isn't an edge theoretical case: sorted input is common for logs, time series, and rebuilding an index from a dump.
AVL держит более строгий баланс (высота ~1.44 log n против ~2 log n у красно-чёрного), поэтому выигрывает там, где чтения доминируют и происходят намного чаще записи, — например, статический или почти статический индекс. Красно-чёрное дерево требует в среднем меньше ротаций на вставку/удаление, поэтому предпочтительно там, где мутации часты, — std::map, планировщики, структуры с постоянным churn. Выбор не в "какое дерево лучше вообще", а в соотношении чтений и записей в конкретной нагрузке.AVL holds a stricter balance (height ~1.44 log n vs. ~2 log n for red-black), so it wins where reads dominate and happen far more often than writes — e.g. a static or near-static index. A red-black tree needs fewer rotations on average per insert/delete, so it's preferable where mutations are frequent — std::map, schedulers, structures under constant churn. The choice isn't "which tree is better overall" but the read/write ratio of the specific workload.
Дерево Фенвика выводит sum по диапазону как prefix(r) - prefix(l-1) — это работает только потому, что сложение обратимо (есть вычитание). Min и max необратимы: зная min на [1, r] и min на [1, l-1], невозможно восстановить min на [l, r] в общем случае. Для min/max по диапазону нужен segment tree (или sparse table для статичных данных), а не BIT.A Fenwick tree derives a range sum as prefix(r) - prefix(l-1) — this only works because addition is invertible (subtraction exists). Min and max are not invertible: knowing the min on [1, r] and the min on [1, l-1] does not let you recover the min on [l, r] in general. Range min/max needs a segment tree (or a sparse table for static data), not a BIT.