вершины х, за время О (log га)?

15.1-6 Заметим, что процедуры OS-Select и OS-Rank используют поле size только для того, чтобы узнать порядковый номер вершины х в поддереве с корнем х. Предположим, что мы храним в вершине вместо поля size этот порядковый номер. Как обновлять эту информацию при добавлении и удалении элемента? (Напомним, что добавление и удаление сопровождаются вращениями.)

15.1-7 Как, используя порядковые деревья, посчитать число инверсий (см. задачу 1-3) в массиве размера га за время O(ralogra)?

15.1-8* Рассмотрим га хорд окружности, заданных своими концами (считаем, что все 2га концевых точек различны). Придумайте алгоритм, который за время О (га lgra) определяет, сколько пар хорд пересекаются внутри круга. (Например, если все хорды - диаметры, то ответом будет С2.)

15.2. Общая схема работы с дополнительной информацией

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

Пополнение структуры данных делится на четыре шага:

1.выбираем базовую структуру данных;

2.решаем, какую дополнительную информацию мы будем хранить (и обновлять);

3.проверяем, что эту информацию удаётся обновлять при выполнении операций, допустимых для выбранной структуры данных;

4.реализуем новые операции.

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

Давайте посмотрим на конструкции раздела 15.1 с точки зрения этих правил.

На шаге 1 мы выбрали красно-чёрные деревья в качестве базовой структуры.

На шаге 2 мы решили добавить к каждой вершине поле size. Смысл хранения дополнительной информации состоит в том, что она позволяет выполнять некоторые операции быстрее. Без поля size мы не смогли бы выполнить операции OS-Select и OS-Rank

за время О (log га). (Несколько иной вариант выбора дополнительной информации дан в упр. 15.2-1.)

На шаге 3 мы убедились, что обновление полей size при добавлении и удалении элементов можно выполнить без ухудшения асимптотики для времени добавления и удаления. В этом смысле наш выбор удачен: если бы, скажем, мы решили хранить для каждой вершины её порядковый номер, то процедуры OS-Select и OS-Rank работали бы быстро, но добавление нового элемента повлекло бы за собой изменение дополнительной информации во многих вершинах дерева (во всех, если добавленный элемент минимален). Наш выбор (поле size) даёт удачный компромисс между лёгкостью использования и обновления.

На шаге 4 мы реализовали процедуры OS-Select и OS-Rank, из-за которых мы, собственно, и затевали всё это дело.

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

Дополнительная информация для красно-чёрных деревьев

Следующая теорема показывает, что для красно-чёрных деревьев информацию определённого вида можно обновлять, не замедляя (асимптотически) операции добавления и удаления. Её доказательство во многом повторяет рассуждения из раздела 15.1.

Теорема 15.1 (Пополнение красно-чёрного дерева). Рассмотрим дополнительный атрибут f, определённый для вершин красно-чёрных деревьев. Предположим, что для всякой вершины х значение f[x] полностью задаётся остальной информацией, хранящейся в вершинах х, left[x] и right[x] (в том числе значениями f[left[x]] и f[right[x]]), и его вычисление по этим данным требует времени 0(1). Тогда поля f можно обновлять при добавлении и удалении элемента из дерева, не ухудшая (асимптотически) время выполнения добавления и удаления.

Доказательство. Идея доказательства состоит в том, что изменение поля / в некоторой вершине х повлечёт за собой изменения поля / только в вершинах, расположенных на пути из корня в х. В самом деле, изменение f[x] повлечёт за собой изменение что в свою очередь изменити т.д., но другие вершины

останутся нетронутыми. От /[гоо/[Г]] не зависит значение поля / в других вершинах, и процесс изменений остановится. Так как высота дерева равна О (log га), то после изменения поля f[x] для какой-то одной вершины х мы сможем обновить все необходимые поля за время О (log га).

Добавление элемента х в дерево Г делается в два этапа (см. разд. 14.3). На первом этапе вершину х добавляют в качестве

ребёнка уже существующей вершины р[х]. Значение f[x] вычисляется за время 0(1), так как новая вершина - лист (точнее, её дети - nil-листья). Далее происходит О (lgra) изменений полей на пути к корню. Итак, первый этап занимает время О (log га). На втором этапе мы выполняем вращения (самое большее два); после каждого потребуется О (lgra) операций для распространения изменений вверх по дереву.

Удаление также проводится в два этапа (см. разд. 14.4). На первом этапе изменения возникают, если удаляемая вершина заменяется её последователем, а также когда мы выбрасываем удаляемую вершину или её последователя. И в том и в другом случае мы изменяем поле / у одной вершины, поэтому обновление всех полей займет время О (log га). На втором этапе мы делаем самое большее три вращения, каждое из которых требует времени O(logra) для обновления полей на пути к корню.□

Во многих случаях (в частности, для поля size) при вращениях все поля можно обновить за время 0(1), а не О (log га). Такая ситуация возникает в упр. 15.2-4.

Упражнения

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

15.2-2 Будем хранить в каждой вершине красно-чёрного дерева её чёрную высоту. Возможно ли обновлять это поле при добавлении и удалении элемента из дерева, не ухудшив (асимптотически) время работы этих операций?

15.2-3 Будем хранить в вершине её глубину. Возможно ли обновлять это поле при добавлении и удалении элемента из дерева, не ухудшив (асимптотически) время работы этих операций?

15.2-4* Пусть <g> - ассоциативная бинарная операция на некотором множестве М, и пусть в каждой вершине красно-чёрного дерева хранится некоторый элемент а множества М (свой в каждой вершине). Пусть теперь мы хотим хранить в каждой вершине х поле f[x] = a[xi]<S>a[x2] <S> • • -® а[жт], где х\, Х2, , хт - все вершины поддерева с корнем х (в порядке возрастания ключей). Показать, что поле / при вращениях можно обновлять за время 0(1). Провести аналогичное рассуждение для поля size.

15.2-5* Мы хотим реализовать для красно-чёрных деревьев операцию RB-enumerate(a;, а, Ь), которая выдаёт список всех вершин