в поддереве с корнем ж, для которых ключ к находится в промежутке а к Ь. Как сделать это за время ©(то + log га), где га - количество вершин в дереве, а то - число выдаваемых ключей? (Указание. Достаточно полей, имеющихся в красно-чёрных деревьях; новые поля не нужны.)

В этом разделе мы используем красно-чёрные деревья для хранения меняющегося множества промежутков. Отрезком (closed interval) [£1,2] называется множество вещественных чисел t, для которых t\ t t2. (Предполагается, что t\ t2.) Полуинтервал (half-open interval) и интервал (open interval) получаются из отрезка выкидыванием одного или двух концов соответственно. В этом разделе мы имеем дело только с отрезками, но все результаты легко распространяются на интервалы и полуинтервалы.

Представим себе базу данных, в которой хранится информация о протяжённых по времени событиях: для каждого события хранится промежуток времени, которое оно занимает. Рассматриваемая в этом разделе структура данных позволяет по любому промежутку найти все события, которые пересекаются с этим промежутком, причём делает это достаточно быстро.

Мы считаем, что отрезок [ii,] представляет собой запись г, состоящую из двух полей: low[i] = t\ (левый конец (low endpoint)) и high[i] = t2 (правый конец (high endpoint)). Будем говорить, что отрезки гиг перекрываются (overlap), если low[i] high[i] и low[i] high[i]; иными словами, если гПг ф 0. (Обратите внимание, что отрезки, имеющие общий конец, считаются перекрывающими-

Всего возможно три варианта взаимного расположения отрезков гиг (рис. 15.3):

1.отрезки гиг перекрываются,

2.high[i] < low[i],

3.high[i] < /огф].

Деревом промежутков (interval tree) назовём красно-чёрное дерево, каждая вершина ж которого хранит отрезок гга£[ж]. Дерево промежутков позволяет реализовать следующие операции:

Interval-Insert (Г, ж) добавляет к дереву Г элемент ж (содержащий некоторый отрезок int[x]);

Interval-Delete (Г, ж) удаляет из дерева Г элемент ж;

Interval-Search (Г, г) возвращает указатель на элемент ж дерева Г, для которого отрезки г и int[x] перекрываются (и возвращает nil, если такого элемента в дереве нет).

15.3. Деревья промежутков

Рис. 15.3 Три варианта взаимного расположения отрезков г и г . (а) Отрезки г и г перекрываются. Возможно четыре варианта; во всех четырёх 1ою[г] high[i] и low[i] high[i]. (б) high[i] < low[i]. (в) high[i] < 1ою[г].

Пример дерева промежутков показан на рис.15.4. Следуя схеме раздела 15.2, мы реализуем такую структуру данных и операции на ней.

Шаг 1: Базовая структура данных

Мы уже выбрали базовую структуру: красно-чёрное дерево, каждая вершина х которого содержит отрезок т/[ж]. Ключом вершины является левый конец отрезка /огфп£[ж]]; обход дерева в порядке «левое поддерево - корень - правое поддерево» перечисляет вершины в порядке возрастания ключей.

Шаг 2: Дополнительная информация

Каждая вершина, помимо отрезка, содержит поле тах[х], в котором хранится максимальный из правых концов отрезков, содержащихся в поддереве с корнем х.

Шаг 3: Обновление дополнительной информации

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

тах[х] = max(high[int[x]], max[left[x]], max[right[x]]),

и остаётся лишь сослаться на теорему 15.1. Можно отметить также, что при вращениях поле max можно обновлять за время 0(1) (упр. 15.2-4 и 15.3-1).

Рис. 15.4 Дерево промежутков, (а) Набор из 10 отрезков (выше тот, у которого левый конец больше), (б) Дерево промежутков, хранящее эти отрезки. При этом свойство упорядоченности дерева выполняется для левых концов.

Шаг 4: Новые операции

Процедура Interval-Search (Г, г) находит в дереве Г отрезок, перекрывающийся с г. Если такого отрезка нет, она возвращает значение nil.

6 return х

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