Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 76
Текст из файла (страница 76)
Таким образом, центрированный обход дерева приводит к перечислению отрезков в порядке сортировки по их левым концам. Шаг 2. Дополнительная информация. В дополнение к самим отрезкам, каждый узел х содержит значение глах [х], которое представляет собой максимальное значение всех конечных точек отрезков, хранящихся в поддереве, корнем которого является х. Шаг 3. Поддержка информации. Мы должны убедиться, что вставка и удаление в дереве с п узлами могут быть выполнены за время О (1йп). Определить значение поля тах в узле х можно очень просто с использованием полей гпах дочерних узлов: тах [х] = шах (Ьгдй [1пт [ж]], тах [1е9 [х]], гпах [г1дМ [х]]) .
Таким образом, по теореме 14.1, вставка в дерево отрезков и удаление из него может быть выполнена за время О (1к и). В действительности, как показано в упражнениях 14.2-4 и 14.3-1, обновление поля тах после вращения может быть выполнено за время О (1). 377 26н26 25 ! — — ~~30 19 н20 17 ! — ~19 22 21 12 22 8н9 6~ — — ~!О 5~ — -~8 0~ — ч3 0 5 10 15 20 25 30 а) 419.20) ', 1;--~Г-) 6) Рис. 14.4.
Множество отрезков и его представление в виде дерева отрезков Шаг 4. Разработка новых операций. Единственная новая операция, которую мы хотим разработать, — это 1нтекчАЕ ЗКАксн(Т,1), которая осуществляет поиск отрезка в дереве Т, который перекрывается с данным. Если такого отрезка в дереве нет, процедура возвращает указатель на ограничитель п11 )Т]: 1хтекчА$.
БеАксн(Т,г) 1 х + — то!)Т] 2 и2ЬПе х 56 пгЦТ) и 1 не перекрывается с 1п1')х] 3 йо 11' !ей) ф пй)Т] и тех)1еЯ)х)) > 1ош]1) 4 Феп х — 1ефх] 5 е!ве х — ттдй1]х) 6 гетпгп х Для поиска отрезка, который перекрывается с г, мы начинаем с присвоения указателю х корня дерева и выполняем спуск по дереву. Спуск завершается когда мы находим перекрывающийся отрезок или когда х указывает на ограничитель Глава 14.
Расширение структур данных ,8Я '! ®' Ю ДО,3) 1 16,10) ) 1 125120) 1 :1 . -- 22222х 69 Ю Часть йй Структуры данных 378 ит1 [Т]. Поскольку каждая итерация основного цикла выполняется за время О [1), а высота красно-черного дерева с п узлами равна О [18 и), время работы процедуры 1нтнкуи. Знлксн равно О [18 и). Перед тем как мы убедимся в корректности процедуры 1нтекум. Белксн, давайте посмотрим, как она работает, на примере дерева, показанного на рис. 14.4. Предположим, что мы хотим найти отрезок, перекрывающийся с отрезком г' = = [22, 25].
Мы начинаем работу с корня, в котором содержится отрезок [16,21], который не перекрывается с отрезком г'. Поскольку значение тах [1е~~ (х]] = 23 превышает 1ото (1] = 22, цикл продолжает выполнение с х, указывающим на левый дочерний узел корня. Этот узел содержит отрезок [8,9], который также не перекрывается с отрезком 1. Теперь тах (1ег2 [х]] = 10 меньше 1ою [1] = 22, так что мы переходим к правому дочернему узлу.
В нем содержится отрезок (15, 23], перекрывающийся с х, так что процедура возвращает указатель на данный узел. В качестве примера неудачного поиска попробуем найти в том же дереве отрезок, перекрывающийся с отрезком г' = [11, 14]. Мы вновь начинаем с корня. Поскольку отрезок в корне [16, 21] не перекрывается с г, и поскольку тах [1е~1 [х]] = = 23 больше, чем 1ото (г] = 11, мы переходим к левому дочернему узлу корня с отрезком [8, 9].
Отрезок (8, 9] также не перекрывается с г, а тах [1ег2 [х]] = 10, что меньше, чем 1ою [г] = 11, поэтому мы переходим вправо (обратите внимание, что теперь в левом поддереве нет ни одного отрезка, перекрывающегося с т. Отрезок [15,23] не перекрывается с г, его левый дочерний узел — ит1 [Т], так что цикл завершается и процедура возвращает указатель на ограничитель ит2 [Т]. Для того чтобы убедиться в корректности процедуры 1нтнкчль Яклксн, нам надо разобраться, почему для поиска нам достаточно пройти по дереву всего лишь по одному пути. Основная идея заключается в том, что в любом узле х, если гиг [х] не перекрывается с г, то дальнейший поиск всегда идет в правильном направлении, т.е.
перекрывающийся отрезок, если таковой имеется в дереве, гарантированно будет обнаружен в исследуемой части дерева. Более точно это свойство сформулировано в следующей теореме. Теорема 14.2. Процедура 1нтнкуль Бнлксн[Т, 1) либо возвращает узел, отрезок которого перекрывается с отрезком г, либо, если в дереве Т не содержится отрезка, перекрывающегося с г, возвращает ит1 (Т]. Доказательство. Цикл твййе в строках 2-5 завершается, если х = ит2 [Т] либо если 1 перекрывается с гит (х].
В последнем случае процедура тривиально возвращает значение х. Поэтому нас интересует первый случай, когда цикл завершается из-за того, что х = ит2 [Т]. Воспользуемся следующим инвариантом цикла и'Ы1е в строках 2-5. Если дерево Т содержит отрезок, который перекрывается с г, то этот отрезок находится в поддереве, корнем которого является узел х. Глава 14. Расширение структур данных 379 ) г 1 — — 4 а) б) Рис. 14.5. Отрезки в доказательстве теоремы 14.2. Пунктирной линией показана величина тах [1еф [х]] Инициализация.
Перед выполнением первой итерации в строке 1 переменной х присваивается указатель на корень дерева, так что инвариант выполняется. Сохранение. Прн каждой итерации цикла згЫ)е выполняется либо строка 4, либо строка 5. Покажем, что инвариант цикла сохраняется в любом случае. При выполнении строки 5 (в силу невыполнения условия в строке 3) мы имеем 1е)г [х] = п11 [Т] или тах [1ефх]] < 1ою [1]. Если 1е]1 [х] = п11 ]Т], то поддерево, корнем которого является 1е~1 [х]„очевидно, не может содержать отрезок, перекрывающийся с г, так что присвоение х — пдЬ1 [х] сохраняет инвариант цикла.
Предположим, следовательно, что 1еГ1 [х] ~~ п11 [Т] и тах [1ег1[х]] < 1ою [1]. Как показано на рис. 14.5а, для каждого интервала з' из левого поддерева х выполняется следующее соотношение: БлдЬ [1] (~ тах[1еф [х]] < 1ою [1]. В соответствии со свойством трихотомии отрезков, 1' и 1 не перекрываются. Таким образом, левое поддерево х не содержит отрезков, перекрывающихся с г, и присвоение х — г1дЬ1 [х] сохраняет инвариант. Пусть выполняется строка 4. В этом случае мы покажем, что если в левом поддереве х нет отрезка, перекрывающегося с г, то его вообще нет в дереве.
Строка 4 выполняется в случае, когда тах [1е)т [хЦ > 1ою [1]. Кроме того, по определению поля тах в левом поддереве х должен быть некоторый интервал 1', такой что Ь1дЬ [1'] = тах [1ег1 [х]] > 1ою [1]. (Данная ситуация проиллюстрирована на рис.
14.5б.) Поскольку 1 и 1' не перекрываются и поскольку неверно, что Ь1дЬ [1'] < < 1ою [1], отсюда в соответствии со свойством трихотомии отрезков следует, что Ь19Ь [1] < 1ою [г']. Поскольку дерево отрезков упорядочено в соответствии с левыми концами отрезков, из свойства дерева поиска вытекает, что для любого отрезка га нз правого поддерева х Ь1дЬ [1] < 1ою [1'] < 1ою [1"] . 380 Часть 111. Структуры данных Из трихотомии отрезков следует, что 1 и гв не перекрываются.
Мы можем, таким образом, заключить, что независимо от того, имеется ли в левом поддереве х отрезок, перекрывающийся с г, присвоение х — 1еу2 [х] сохраняет инвариант цикла. Завершение. Если цикл завершается по условию х = пп [Т], то в дереве, корнем которого является х, нет отрезков, перекрывающихся с г.
Обращение инварианта цикла приводит к заключению, что дерево Т не содержит отрезков, перекрывающихся с г. Следовательно, возвращаемое процедурой значение пя [Т] совершенно корректно. Итак, процедура 1нтекчле 8елксн работает корректно. Упражнения 14.3-1. Напишите псевдокод процедуры 1.еет Нотлте, которая работает с узлами дерева отрезков и обновляет поля тах за время О (1). 14.3-2. Перепишите код процедуры 1нтекчлг. Белксн для корректной работы с интервалами (отрезками без конечных точек).
14.3-3. Разработайте эффективно работающий алгоритм, который для данного отрезка г возвращает отрезок, перекрывающийся с г и имеющий минимальное значение левого конца (либо п11 [Т], если такого отрезка не существует). 14.3-4. Пусть у нас имеется дерево отрезков Т и отрезок 1. Опишите, каким образом найти все отрезки в дереве Т, перекрывающиеся с отрезком 1, за время О (ппп(п, 1с 18п)), где 1с — количество найденных отрезков. 1Дополлшпвльное условие: попробуйте найти решение, не изменяющее дерево.) 14.3-5. Какие изменения надо внести в процедуры дерева отрезков для поддержки новой операции 1нтекчм. 8елксн Ехлсти'(Т, г), которая возвращает указатель на узел х дерева отрезков Т, такой что 1ож [1п1 [х]] = 1ою [г] и )пдп [гп1 [х]] = )пдву [1] (либо пг1 [Т], если такого узла в дереве Т нет).
Все операции, включая 1нтекчлг, Белксн Ехлстьч, должны выполняться в дереве с и узлами за время О (18 и). 14.3-6. Пусть у нас есть динамическое множество натуральных чисел Щ на котором определена операция Мич блк, возвращающая минимальное расстояние между соседними числами в Я. Например, если Я = (1, 5, 9, 15, 18, 22), то М1н блг(Я) возвратит значение 18 — 15 = 3, так как 15 и 18— ближайшие соседние числа в Я. Разработайте максимально эффективные процедуры 1хзект, 13ееете, Белксн и М~н блг и проанализируйте нх время работы. Глава 14.
Расширение структур данных 381 * 14.3-7. Базы данных при разработке СБИС зачастую представляют интегральную схему как список прямоугольников. Предположим, что все прямоугольники ориентированы вдоль осей х и у, так что представление прямоугольника состоит из минимальных и максимальных координат х и у. Разработайте алгоритм для выяснения, имеются ли в данном множестве из и прямоугольников два перекрывающихся (искать все перекрывающиеся пары не надо). Перекрытием считается также ситуация, когда один прямоугольник лежит полностью внутри другого, пусть при этом их границы и не пересекаются.
Время работы алгоритма должно составлять О (и 18 и). (Указание: перемещайте "строку развертки*' по множеству прямоугольников.) Задачи 14-1. Точка максимального перекрытия Предположим, что мы хотим найти точку максимального перекрытия множества отрезков, т.е. точку, в которой перекрывается наибольшее количество отрезков множества. а) Покажите, что такая точка всегда имеется и представляет собой конечную точку одного из отрезков. б) Разработайте структуру данных, которая поддерживает эффективную работу операций 1)чтвкчл!. 1)чзвкт, 1)чтвкуд). Рн етн и Рпв РОМ (которая возвращает точку максимального перекрытия).
(Указание: воспользуйтесь красно-черным деревом всех конечных точек отрезков. С каждым левым концом отрезка связано значение +1, с правым — значение — 1. Добавьте к узлам дерева некоторую дополнительную информацию для поддержки точки максимального перекрытия.) 14-2.
Перестановка Иосифа Задача Иосифа ! формулируется следующим образом. Предположим, что и человек расставлены в круг и задано некоторое натуральное число т ( и. Начиная с определенного человека, мы идем по кругу, удаляя каждого т-го человека. После удаления человека счет продолжается дальше. Процесс продолжается, пока все и человек не будут удалены. Порядок, в котором люди удаляются из круга, определяет (и, т)-нерестановку 'Достаточно подробно об этой задаче, се происхождении и вариациях можно прочесть, например, в книге У. Болл, П Коксетср. Математические эссе и развлечения. — Млмир, ! 986 (стр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
