Конспект: дополненные деревья

Понятия

Дополнение дерева - приём: добавить в узел ПОЛЕ, восстановимое из полей детей за O(1), и получить новую операцию, НЕ ломая старые (поиск, вставку, удаление, баланс). Поле обновляют на пути вставки/удаления и при ВРАЩЕНИЯХ (O(1) на узел).

Поле size (число узлов поддерева = 1 + size(лево) + size(право)) даёт: - SELECT(k) - k-й по порядку элемент: в узле L = size(лево), ранг узла L+1; k==L+1 - ответ, k<=L - влево, иначе вправо с k = k − L − 1. O(log n). - RANK(x) - место ключа: сумма размеров левых поддеревьев там, где уходим вправо. O(log n).

Поле max (наибольший правый конец отрезков поддерева) в BST по левому концу даёт поиск ПЕРЕСЕКАЮЩЕГО отрезка: если max(лево) < l, все левые кончаются раньше l - отбрасываем поддерево, идём вправо. O(log n).

Локальность поля - ключевое условие: пересчёт из детей за O(1) позволяет обновлять поле при вращениях, не обходя поддерево, - потому балансировка сохраняется.

Что унести

Дополнение - это ОДИН шаблон, а не набор трюков:

1. взять сбалансированное BST
2. добавить в узел поле, восстановимое из детей за O(1)
3. обновлять поле при вставке/удалении и при вращениях (O(1) на узел)
4. новая операция СПУСКАЕТСЯ по дереву, используя поле, чтобы отбросить поддерево

Меняется только ПОЛЕ и правило спуска:

Дополнение даёт то, чего не может ни хеш (нет порядка), ни массив (дорогая вставка), ни обычное дерево (нет рангов/диапазонов): ДИНАМИЧЕСКИЕ порядковые и диапазонные запросы за O(log n). Главная мысль - не конкретная структура, а МЕТОД: встретив «нестандартный» запрос, спроси «каким локальным полем дополнить дерево, чтобы ответить спуском?». Дерево отрезков и Фенвика (следующая глава) - это тот же приём, доведённый до диапазонных запросов.

Ловушки джокера

Поле, не восстановимое из детей локально (глубина, глобальный индекс) - вращение потребует обхода поддерева, O(1)-баланс сломается. Дополняют полем, зависящим только от детей.

Не обновлять поле при вращениях (только при вставке/удалении) - после балансировки поле неверно, операция врёт.

Для порядковой статистики взять высоту вместо размера - высота не говорит, сколько элементов слева.

В select ошибиться с поправкой при уходе вправо - вычитать size(лево) + 1 (левое поддерево И сам узел), не только size(лево).

Для пересечения взять не max правого конца - только он позволяет отбросить «все кончаются раньше l».

Ждать все пересечения за O(log n) - за O(log n) находится одно; все k - дороже.

Проверь себя

В чём приём дополнения и почему поле должно восстанавливаться из детей за O(1)?

Как поле size даёт select и rank за O(log n)?

Каким полем и как интервальное дерево находит пересекающийся отрезок?

Почему интервальное дерево и дерево порядковой статистики - один шаблон?

Какое поле дало бы диапазонные суммы?