1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 39
Текст из файла (страница 39)
Во всех остальных узлах АВЛ-условие выполняется. С) 4.30. Покажите, что АВЛ-дерево высоты )г содержит не более 2А+' — 1 и не менее 5+2 )г5('!+ Р' 5)" 5 — 2 $~5(! — $~ 5) узлов. е4.31. Пусть Т вЂ” дерево двоичного поиска с и узлами, обладающее АВЛ-свойством. Напишите алгоритм сложности 0(1одп) Рис. 9.37. Не АВЛ-дерево. ') В честь его авторов Г. М. Адельсоиа-Вельского и В. М. Лаидиса; см. их работу [!962]. $93 7 А. Ахо, Дж. Ховкрофт, Дж.
Уаьмвв гл. к стгкктугы данных для злдхч с множествами для операций ВСТАВИТЬ и УДАЛИТЬ, которые сохраняют АВЛ- свойство. Можете считать, что высоту каждого узла можно найти в нем самом и что информация о высотах корректируется автоматически. "4.32. Напишите алгоритмы для расцепления АВЛ-дерева и сцепления двух АВЛ-деревьев. Эти алгоритмы должны расходовать время, пропорциональное высотам деревьев. *4.33. Используйте АВЛ-дерево в качестве базиса алгоритма, выполняющего операции М1Х, ОБЪЕДИНИТЬ и УДАЛИТЬ над множествами целых чисел от 1 до а и затрачивающего 0(1ойа) шагов на операцию. Определение. Балансом узла о двоичного дерева называется число (1+Ц/(2+/.+Я), где /.
и /т — числа узлов в левом и правом поддеревьях узла и. Дерево двоичного поиска называется а-сбалансированным, если баланс каждого узла заключен между а и 1 — а. Пример 4.15. Баланс узла, отмеченного знаком и на рис. 4.37, равен ~/н Ни один другой узел не имеет баланса, столь сильно уклоняющегося от '/„так что дерево на рис. 4.37 ~/7-сбалансиро. вано. П "4.34. Укажите верхнюю и нижнюю границы числа узлов в сс-сбалансированном дереве высоты й. **4.35.
Повторите упр. 4.31 — 4.33 для деревьев с балансом а, где сс('/,. *4.36. Сможете ли вы сделать упр. 4.31 — 4.33, если а)'/,? 4.37, Разработайте понятие сбалансированного дерева с данными на листьях, в котором балансировка достигается за счет того, что разность высот поддеревьев поддерживается в пределах фиксированной постоянной. ':4.38.
Напишите алгоритм сложности 0(пб(п)), который по данному дереву с а узлами и списку нз п пар узлов находил бы для каждой пары (и, в) ближайшего общего предка узлов и и ш. "4.39. Длина внешних пуглей двоичного дерева определяется как сумма глубин всех его листьев, длина внутренних путей — как сумма глубин всех его узлов. Каково соотношение между длинами внешних и внутренних путей, если у каждого узла либо два сына, либо ни одного? "4.40. Разработайте структуру данных для реализации очере. дей, которая позволяла бы выполнять в префиксном режиме еле. ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ дующие операции: (а) ВПИСАТЬ (г, А), т. е.
добавить целое число ! к очереди А. Допускаются различные вхождения одного и того же числа. [б) ВЫПИСАТЬ(А), т. е. извлечь из А тот элемент, который находится там дольше всех. (в) СЛИТЬ(А, В, С), т. е. объединить очереди А и В в новую очередь С. Предполагается, что элементы находятся в объединенной очереди так долго, как они находились в соответствующей очереди А или В. Заметьте, что одно и то же число может несколько раз входить в А и В и каждое вхождение следует рассматривать как отдельный элемент.
Сколько времени нужно для выполнения последовательности из и операций? "4.41. Разработайте структуру данных для реализации операций упр. 4.40 в свободном режиме, Сколько времени нужно для выполнения п таких операций в свободном режиме? *4.42. Пусть начальное разбиение и= (В„ ..., Ве) в алгоритме 4.5 обладает тем свойством, что для каждого 1([(д справедливо включение [ '(В!)яВ! при некотором 1. Покажите, что в строке 6 иа рнс. 4.35 выбирается не более одного 1. Уменьшает ли наше допущение время работы алгоритма 4.5? Проблема для исследования 4.43. Со скоростью выполнения последовательности из п операций, выбранных из тех семи, что приведены в равд.
4.1 (или других основных операций того же типа), связано много нерешенных вопросов. Если элементы берутся из произвольного множества и единственный путь получения информации о них — это попарное сравнение, то любое множество основных операций, с помощью которых можно сортировать, потребует время 0 (и [опп). Но если универсум представляет собой множество целых чисел (1,2,..., п) (нлп даже (1, 2,..., пэ) для фиксированного й), то трудно привести соображения за то, что для сортировки потребуется более 0(п) времени, если только основных операций достаточно для нее.
Таким образом, есть возможность улучшить среднее время илп время в худшем случае, приведенные на рис. 4.36. Напротив, можно ли для некоторого подмножества (или даже всего множества) основных операций на целых числах от 1 до и получить нижние оценки, лучшие чем 0(п)? Замечания по литературе [)нформапню о разнообразии методов расстановки можно почерпнуть в кннгах Морриса [)968[, Ахо, Ульмана [[9731 н Кнута [[973а[ х), Последняя содержнт ') Кнут [)973а, 46Л[ дает краткую нсторню возникновения н развнтня этих методов, а также интересное обьясненне употребляемого в литературе на англнбском языке термина «Ьазп)пяь. По свндсгельсгву Кнута, это слово ев раз.
ных частях света уже стало общепринятым жаргономж В нашу лнтературу также гл. с стрккткпы данных для злдлч с множнствлмн также информацию о деревьях двоичного поиска. Алгоритм 4.2 для построения статического дерева двоичного поиска заимствован у Гилберта, Мура [1959). Алгоритм сложности 0(лз) для той же задачи можно найти у Кйута [1971[, где содержится также и решение упр. 4.6. Ху. Таккер [1971) показали, что время 0(л ) и память 0(л) достаточны, чтобы построить оптимальное дерево двоичного поиска, в котором данные появляются только на листьях. Кнут [1973а) дал реа.
лизацию эчого алгоритма эа время 0(л 1ойл). Рейнгольд [1972] приводит оптимальные алгоритмы для многих основных преобразований множеств, таких, как объединение и пересечение. Алгоритм 4.3 для задачи ОБЪЕЛИНИТЬ вЂ” НАЙТИ был, по-видимому, впервые применен Мак-Илроем и Моррисом.
Кнут [1969] приписывает сжатие путей Триггеру. Теорема 4.4 взята у Хопкрофта, Ульмана [1974], а теорема 4 3 — у Тарьяна [1974[. Приложение к приравниванию идентификаторов и вычислению смещения, обсуждавшиеся в равд. 4.8, заимствованы у Галлера, Фишера [!964]. Приложе. ние 3 об эквивалентности конечных автоматов взято из статьи Хопкрофта, Карпа [1971). Упр. 4.16 и 4.17, касающиеся сложности алгоритма 4.3 без сжатия путей, взяты у Фишера [1972) н Патерсона [1973] соответственно. АВЛ-деревья даны по Адельсону-Вельскому, Ландису (1962), а ответы на упр.
4.31 и 4.32 можно найти у Крейна [1972]. Понятие а-сбалансированного дерева наложено по Нивергельту, Рейнгольду [1973]. Читатель может обратиться к этой работе по поводу упр. 4.34 — 4.37. )(альнейшие применения 2-3-деревьев можно найти в рабоче Ульмана ]1974). Упр. 4.22 представляет собой раннее решение задачи ОБЪЕЛИНИТЬ— НАЙТЙ; оно приведено Стирнэом, Розенкранцем [1969).
Упр.4.38 содержится у Ахо, Хопкрофта, Ульмана [19?4!. Различие между префнксным и свободным режиыами работы алгоритмов ввели Хартманис, Льюис, Стирнз [1965]. Рабин [1963] изучил нежный частный случай префиксных вычислений, называемый вычислением в реальное время. Алгоритм разбиения и приложение к минимизации числа состояний конеч. ного автомата взяты из статьи Хопкрофта [1971[.
проник уже этот жаргон: хеширование, хеш-таблицы, хеш-функции. В данной книге мы вслед за переводчикаыи двухтомного труда Ахо, Ульмана [1972, 1973) называем эти методы лешодали рассшаноэкк.— Прим. ред. АЛГОРИТМЫ НА ГРАФАХ Многие задачи теоретического и прикладного характера можно сформулировать в терминах неориеитированных или ориентированных графов. В этой главе мы обсудим некоторые из основных задач на графах, решения которых полиномиально зависят (в смысле времени выполнения) от числа узлов и, следовательно, ребер графа.
В основном мы будем заниматься задачами, в которых речь идет о связности графа. Сюда входят алгоритмы для нахождения остовных деревьев, двусвязных компонент, сильно связных компонент и путей между узлами. В гл. 1О мы изучим более сложные задачи о графах. ЗЛ. ОСТОВНОЕ ДЕРЕВО НАИМЕНЬШЕЙ СТОИМОСТИ Пусть 0= (1', Е) — связный неориентированный граф, для которого задана функция стоимости, отображающая ребра в вещественные числа.
Напомним, что остовным деревом для данного графа называется неориентированное дерево, содержащее все узлы графа. Стоимость остовного дерева определяется как сумма стоимостей его ребер. Наша цель — найти для 0 остовное дерево наименьшей стоимости. Мы увидим, что остовиое дерево наименьшей стоимости для графа с г ребрами можно найти за время 0(г 1ойг) в общем случае и 0(г), если г достаточно велико по сравнению с числом узлов (см. упр. 5.3). Многие алгоритмы нахождения остов- ного дерева основаны на следующих двух леммах. Лемма 5.1. Пусть 6= (У, Е) — связный нгоригнтированный гра4 и 5= (У, Т) — остовног дерево для него.
Тогда (а) для любых двух узлов о, и о, из У путь между о, и о, в 5 гдинствгн и (б) если к 5 добавить ребра из Š— Т, то возникнет ровно один цикл. ГЛ. б. АЛГОРИТМЫ ИА ГРАФАХ Д о к а з а т е л ь с т в о. Утверждение (а) тривиально, ибо если бы было более одного пути, то в 5 был бы цикл. Утверждение (б) тоже тривиально, ибо между концами добавляемого ребра уже был один путь. С1 Лемма 5.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
