Для примера посмотрим, как процедура ищет в дереве на рис. 15.4 отрезок, перекрывающийся с отрезком г = [22,25]. Мы начинаем с корня (ж = root[T]), который хранит отрезок [16,21], не перекрывающийся с г. Так как max[left[x]] = 23, что больше, чем low[i] = 22, то мы переходим к левому ребёнку корня (ж <- left[x]). Этот ребёнок хранит отрезок [8,9], также не перекрывающийся с г. На этот раз max[left[x]] = 10 меньше low[i] = 22, поэтому мы переходим к правому ребёнку вершины ж. Там находится отрезок [15,23], перекрывающийся с г, и поиск завершается.

Рассмотрим пример безрезультатного поиска в том же дереве - будем искать отрезок, перекрывающийся с г = [11,14]. Снова начинаем с корня. Корень хранит отрезок [16, 21], не перекрывающийся с г. Так как max[left[x]] = 23 больше low[i] = 11, переходим к левому ребёнку. Теперь в ж хранится отрезок [8,9]. Он не перекрывается с г, и max[left[x]] = 10 меньше low[i] = 11, поэтому идём направо. (Слева искомого отрезка быть не может). В ж теперь хранится [15,23], с г этот отрезок не перекрывается, left[x] = nil, поэтому идём направо и возвращаем значение nil.

Корректность процедуры Interval-Search устанавливает теорема 15.2, которая утверждает, что если отрезки int[x] и г не перекрываются, то дальнейший поиск идёт в правильном направлении (если нужные отрезки вообще есть в дереве, то они есть и в выбираемой части дерева). Поэтому нам достаточно просмотреть всего один путь. (Обратите внимание, что слова «правильное направление» не означают, что в другом направлении искомых отрезков нет: мы утверждаем лишь, что если они есть вообще, то есть и в «правильном» направлении!)

Теорема 15.2. Пусть ж - произвольная вершина дерева, г - отрезок, не перекрывающийся с int[x], и мы выполняем строки 3-5 процедуры Interval-Search (Г, г). Тогда:

1.Если выполняется строка Jh то либо поддерево с корнем left[x] (левое поддерево) содержит отрезок, перекрывающийся с г, либо поддерево с корнем right[x] (правое поддерево) не содержит отрезка, перекрывающегося с г.

2.Если выполняется строка 5, то левое поддерево не содержит отрезка, перекрывающегося с г.

Доказательство. Начнём с более простого случая 2. Строка 5 выполняется, если не выполнено условие в строке 3, то есть если left[x] = nil или max[left[x]] < /ою[г]. В первом случае левое поддерево пусто, поэтому не содержит отрезка, перекрывающегося с г. Предположим, что left[x] ф nil и max[left[x]] < /огф]. Рассмотрим произвольный отрезок г из левого поддерева (см. рис. 15.5а). Так как max[left[x]] - наибольший правый конец таких отрезков, то

high[i] max[left[i]] < /огф],

Рис. 15.5 Отрезки в доказательстве теоремы 15.2. Пунктиром показано значение max[left[x]]. (а) Случай 2: мы идем направо. Никакой интервал г не перекрывается с г. (б) Случай 1: мы идем налево. Выберем в левом поддереве отрезок г , для которого high[i] = max[left[x]] 1ою[г]. Тогда либо г перекрывается с г, либо г лежит целиком справа от г, и г не перекрывается ни с каким отрезком г" из правого поддерева, потому что low[i] low[i"].

поэтому отрезок г целиком лежит левее отрезка г. Случай 2 рассмотрен.

Рассмотрим теперь случай 1. Предположим, что в левом поддереве нет отрезков, перекрывающихся с г. Тогда нужно доказать, что таких отрезков нет и в правом. Так как выполняется строка 4, то условие в строке 3 выполнено, и max[left[x]] /ою[г]. Поэтому в левом поддереве найдётся отрезок г7, для которого

high[i] = max[left[i]] low[i]

(см. рис. 15.56). Но отрезки г и г7 не перекрываются (по предположению - мы считаем, что в левом поддереве нет отрезков, перекрывающихся с г). Это означает, что отрезок г1 лежит целиком справа от г (целиком слева он лежать не может), то есть high[i] < low[i]. В дереве Г выполнено свойство упорядоченности левых концов, поэтому и все отрезки правого поддерева лежат целиком справа от г: для произвольного отрезка г" из правого поддерева выполнено

high[i] < /ою[г7] low[i"].

□

Упражнения

15.3-1 Напишите процедуру Left-Rotate для дерева промежутков, которая обновляет поля max за время 0(1).

15.3-2 Перепишите процедуру Interval-Search для случая, когда в дереве промежутков хранятся не отрезки, а интервалы (то есть нас интересуют перекрытия ненулевой длины).

15.3-3 Постройте алгоритм, который по заданному отрезку возвращает перекрывающийся с ним отрезок с минимальным левым концом (или константу nil, если таких отрезков нет).

Задачи к главе 15

299

15.3-4 Напишите программу, которая по заданному отрезку г и дереву промежутков Г возвращает список всех отрезков дерева Г, перекрывающихся с г. Время работы должно быть О (min (га, k log га)), где к - число элементов возвращаемого списка. (Дополнительный вопрос: как сделать это, не меняя дерева?)

15.3-5 Какие надо внести изменения в определение дерева промежутков, чтобы дополнительно реализовать процедуру Interval-Search-Exactly (Г, г), которая либо возвращает вершину х дерева Г, для которой /огфп£[ж]] = low[i] и high[int[x]] = high[i], либо выдаёт константу nil, если таких вершин нет (ищет отрезок, равный г, а не просто перекрывающийся с г.) Время работы процедуры Interval-Search-Exactly, а также всех прежних процедур промежутков должно оставаться равным О (log га).

15.3-6 Рассмотрим множество Q натуральных чисел. Определим Min-Gap как расстояние между двумя ближайшими числами в Q. Например, если Q = {1, 5, 9,15,18, 22}, то Min-Gap(Q) равно 18 -15 = 3. Реализуйте структуру данных, эффективно реализующую добавление, удаление и поиск элемента, а также операцию Min-Gap. Каково время работы этих операций?

15.3-7* При разработке интегральных схем информация часто представляется в виде списка прямоугольников. Пусть даны га прямоугольников со сторонами, параллельными осям координат. Каждый прямоугольник задаётся четырьмя числами: координатами левого нижнего и правого верхнего углов. Написать программу, которая за время О (га log га) выясняет, есть ли среди этих прямоугольников два перекрывающихся (но не требуется найти все перекрывающиеся прямоугольники). Обратите внимание, что границы перекрывающихся прямоугольников могут не пересекаться, если один лежит внутри другого. (Указание. Двигаем горизонтальную прямую снизу вверх и смотрим, как меняется её пересечение с прямоугольниками.)

Задачи

15-1 Точка максимальной кратности

Мы хотим следить за точкой максимальной кратности (point of maximum overlap) множества промежутков - точкой, которая принадлежит максимальному числу промежутков из этого множества. Как нам обновлять информацию об этой точке при добавлении и удалении элемента?