Дополненное дерево: размер поддерева даёт ранг

Если ты понимаешь, как поле «размер поддерева» даёт select (k-й по порядку) и rank за O(log n), и почему поле должно восстанавливаться из детей за O(1), чтобы пережить вращения, листай до «Теперь сам».

Как думаешь, как узнать «пятый по величине», имея дерево поиска

Обычное дерево поиска отвечает на «есть ли ключ x» и «что больше/меньше x». Но частый вопрос другой: «какой элемент СТОИТ НА 5-м месте по порядку?» или «сколько элементов МЕНЬШЕ x?». Отсортированный массив ответил бы мгновенно (a[4]), но он статичен - вставка O(n). Дерево динамично, да только не знает про «места»: спускаясь по нему, мы не понимаем, сколько элементов осталось слева. А что если КАЖДЫЙ узел будет помнить, сколько всего узлов в его поддереве? Тогда, стоя в узле, мы точно знаем: слева от него размер левого элементов, значит сам он - (размер левого + 1)-й по порядку в своём поддереве. Этого достаточно, чтобы спускаться прямо к нужному месту. Одно поле - и дерево научилось порядковым запросам.

На что это похоже

Многоэтажное здание, где на каждой площадке висит табличка «в этом крыле ниже - столько-то квартир». Ищешь квартиру №247 по порядку: на площадке видишь «в левом крыле 200 квартир» - значит 247-я не там, она правее; вычитаешь 200 (и текущую) и идёшь в правое крыло искать уже (247−201)-ю. Таблички-счётчики позволяют шагать прямо к нужному номеру, не обходя все квартиры. Дополненное дерево - такое здание: «размер поддерева» в узле - это табличка, по которой находишь k-й элемент за спуск, а не за перебор.

Механизм: поле size и операции select/rank

В каждый узел добавляем поле size - число узлов в его поддереве:

size(узел) = 1 + size(узел.лево) + size(узел.право)     (пустое поддерево: size = 0)

select(k) - найти k-й по порядку (по возрастанию) элемент:

select(узел, k):
    L = size(узел.лево)          # столько элементов меньше узла
    если k == L + 1:  вернуть узел          # узел и есть k-й
    если k <= L:      select(узел.лево, k)   # k-й в левом поддереве
    иначе:            select(узел.право, k − L − 1)  # в правом, с поправкой на отброшенные

rank(x) - сколько элементов ≤ x (место ключа): спускаясь от корня, складываем size(лево) + 1 ТОЛЬКО в тех узлах, из которых уходим ВПРАВО (они сами и всё их левое поддерево меньше x), и в найденном узле добавляем size(лево) + 1. Узлы, из которых мы ушли влево, больше x и в счёт не идут. Обе операции - спуск по одному пути, O(log n) в сбалансированном дереве.

Главное - ПОДДЕРЖКА поля. При вставке/удалении на пути от корня к листу размеры меняются - их пересчитывают снизу вверх. При ВРАЩЕНИИ (балансировка) размеры двух затронутых узлов пересчитывают по формуле - это O(1), поэтому балансировка АВЛ/красно-чёрного продолжает работать, просто дополнительно обновляя size.

Правило

Дополнение дерева - добавить в узел поле, ВОССТАНАВЛИВАЕМОЕ из полей детей за O(1), и получить новую операцию, не ломая старые. Поле size (размер поддерева, 1 + size(лево) + size(право)) даёт SELECT (k-й по порядку) и RANK (место ключа) за O(log n): стоя в узле, знаем, что слева от него size(лево) меньших элементов, и спускаемся прямо к цели. Поле обновляют при вставке/удалении на пути и при вращениях (O(1) на узел), поэтому балансировка сохраняется. Так дерево совмещает динамичность (дешёвые вставки) и порядковые запросы (как у массива).

Разбор: почему поле обязано восстанавливаться из детей за O(1)

Это условие, которое делает дополнение вообще работоспособным. Дерево постоянно меняет форму: вставки, удаления и особенно ВРАЩЕНИЯ при балансировке переставляют узлы. Если бы поле нельзя было быстро пересчитать, каждое вращение (а их O(log n) на операцию) требовало бы обойти целое поддерево, чтобы обновить поле, - и O(1)-вращение превратилось бы в O(n), убив балансировку. Спасает то, что size узла выражается ТОЛЬКО через size его непосредственных детей и его самого: 1 + size(лево) + size(право). Значит после вращения достаточно пересчитать поле у двух переставленных узлов (по формуле, за O(1) каждый) - остальные поддеревья не тронуты, их поля верны. Это общее правило дополнения: годится ЛЮБОЕ поле, которое ЛОКАЛЬНО восстанавливается из детей (размер, сумма, минимум, максимум поддерева), и НЕ годится то, что требует глобального пересчёта. Локальность поля = совместимость с балансировкой.

Разбор: почему select спускается за O(log n), а не считает заново

Наивно «найти k-й элемент» можно обходом (inorder) с подсчётом до k-го - но это O(k), до O(n). Поле size превращает это в спуск. В каждом узле мы за O(1) знаем, СКОЛЬКО элементов в левом поддереве (size(лево)), а значит знаем ранг самого узла в его поддереве: он (size(лево)+1)-й. Сравнив с k, мы сразу решаем, куда идти: k меньше - в левое поддерево (там ранги 1..size(лево)), k равно - нашли, k больше - в правое, уменьшив k на число отброшенных слева (size(лево)+1). Каждый шаг спускает на уровень и отбрасывает целое поддерево - как обычный поиск по ключу, только «ключ» тут - позиция k. Поэтому select - это O(высоты) = O(log n), а не обход. Та же логика у rank, только идём по ключу и суммируем отброшенные СЛЕВА поддеревья вместе с их узлами. Поле-счётчик превращает «пересчитать» в «дойти».

Что ломается без этого

Первая ошибка - взять поле, которое НЕ восстанавливается из детей локально (например, «глубина узла от корня» или «индекс в глобальном порядке» как число): при вращении его пришлось бы пересчитывать по всему дереву, O(1)-балансировка сломается. Дополняют полем, зависящим только от детей. Вторая - забыть обновлять поле при ВРАЩЕНИЯХ (обновлять только при вставке/удалении): после балансировки размеры двух узлов станут неверными, и select/rank начнут врать. Пересчёт при вращении обязателен. Третья - путать size (число узлов) с высотой: для порядковых запросов нужен именно размер поддерева. Четвёртая - в select ошибиться с поправкой при уходе вправо: надо вычесть size(лево) + 1 (левое поддерево И сам узел), а не только size(лево).

Зачем это в работе

Дополненные деревья дают то, чего не может ни хеш-таблица (нет порядка), ни обычное дерево (нет рангов), ни массив (дорогая вставка): ДИНАМИЧЕСКИЕ порядковые запросы. «Медиана потока чисел в любой момент», «сколько значений меньше x среди уже вставленных», «элемент на k-м месте рейтинга, который постоянно меняется», «ранг игрока в живой турнирной таблице» - всё это select/ rank за O(log n) на дереве с полем size. В C++ есть готовое order statistics tree (в расширениях GNU), в базах данных ранжирующие запросы по индексу стоят на той же идее. Но главное - дополнение это ОБЩИЙ приём, а не один трюк: добавь в узел локально-восстановимое поле - получишь новую операцию бесплатно (в смысле сохранения O(log n) и балансировки). Следующий урок - другое поле (максимум конца отрезка) и другая операция (пересечение интервалов); а сумма поддерева даст диапазонные суммы. Умение «дополнить структуру полем под нужный запрос» - мощный и часто недооценённый инструмент.

Теперь сам

В дереве с полем size (см. схему: корень 15 size=5, слева 8 size=2 с ребёнком 3, справа 22 size=2 с ребёнком 30) вызвали select(5) - найти 5-й по возрастанию элемент. Проследи спуск.