Главная Промышленная автоматика.

ДЛЯ операций ВСТАВИТЬ и УДАЛИТЬ, которые сохраняют АВЛ-свойство. Можете считать, что высоту каждого узла можно найти в нем самом и что информация о высотах корректируется автоматически.

*4.32. Напишите алгоритмы для расцепления АВЛ-дерева и сцепления двух АВЛ-деревьев. Эти алгоритмы должны расходовать время, пропорциональное высотам деревьев.

*4.33. Используйте АВЛ-дерево в качестве базиса алгоритма, выполняющего операции MIN, ОБЪЕДИНИТЬ и УДАЛИТЬ над множествами целых чисел от 1 до п и затрачивающего О (log п.) шагов на операцию.

Определение. Балансом узла v двоичного дерева называется число (l+L)/{2+L-\-R), где L и R - числа узлов в левом и правом поддеревьях узла v. Дерево двоичного поиска называется а-сба-лансированньш, если баланс каждого узла заключен между а и 1-а.

Пример 4.15. Баланс узла, отмеченного знаком * на рис. 4.37, равен 5/,. Ни один другой узел не имеет баланса, столь сильно уклоняющегося от Va. так что дерево на рис. 4.37 т-сбалансиро-вано. □

*4.34. Укажите верхнюю и нижнюю границы числа узлов в а-сбалансированном дереве высоты h.

**4.35. Повторите упр. 4.31-4.33 для деревьев с балансом а, где a<Vs-

*4.36. Сможете ли вы сделать упр. 4.31-4.33, если а>1/з?

4.37. Разработайте понятие сбалансированного дерева с данными на листьях, в котором балансировка достигается за счет того, что разность высот поддеревьев поддерживается в пределах фиксированной постоянной.

*4.38. Напишите алгоритм сложности 0{nG{n)), который по данному дереву с п. узлами и списку из п. пар узлов находил бы для каждой пары (v, w) ближайшего общего предка узлов v и w.

*4.39. Длина внешних путей двоичного дерева определяется как сумма глубин всех его листьев, длина внутренних путей - как сумма глубин всех его узлов. Каково соотношение между длинами внешних и внутренних путей, если у каждого узла либо два сына, либо ни одного?

*4.40. Разработайте структуру данных для реализации очередей, которая позволяла бы выполнять в префиксном режиме сле-



ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ

дующие операции:

(а) ВПИСАТЬ (f, А), т. е. добавить целое число i к очереди А. Допускаются различные вхождения одного и того же числа.

(б) ВЫПИСАТЬ (Л), т. е. извлечь из А тот элемент, который находится там дольше всех.

(в) СЛИТЬ (Л, В, С), т. е. объединить очереди Л и В в новую очередь С. Предполагается, что элементы находятся в объединенной очереди так долго, как они находились в соответствующей очереди Л или В. Заметьте, что одно и то же число может несколько раз входить в Л и В и каждое вхождение следует рассматривать как отдельный элемент.

Сколько времени нужно для выполнения последовательности из п операций?

*4.41. Разработайте структуру данных для реализации операций упр. 4.40 в свободном режиме. Сколько времени нужно для выполнения п таких операций в свободном режиме?

*4.42. Пусть начальное разбиение n={Bi, . . ., В} в алгоритме 4.5 обладает тем свойством, что для каждого 1:/ справедливо включение /~i(B,)B; при некотором /. Покажите, что в строке 6 на рис. 4.35 выбирается не более одного /. Уменьшает ли наше допущение время работы алгоритма 4.5?

Проблема для исследования

4.43. Со скоростью выполнения последовательности из п операций, выбранных из тех семи, что приведены в разд. 4.1 (или других основных операций того же типа), связано много нерешенных вопросов. Если элементы берутся из произвольного множества и единственный путь получения информации о них - это попарное сравнение, то любое множество основных операций, с помощью которых можно сортировать, потребует время О («Iog«). Но если универсум представляет собой множество целых чисел {1,2, ...,«} (или даже {1, 2, . . ., га*} для фиксированного k), то трудно привести соображения за то, что для сортировки потребуется более О (га) времени, если только основных операций достаточно для нее. Таким образом, есть возможность улучшить среднее время или время в худшем случае, приведенные на рис. 4.36. Напротив, можно ли для некоторого подмножества (или даже всего множества) основных операций на целых числах от 1 до га получить нижние оценки, лучшие чем О (га)?

Замечания по литературе

Информацию о разнообразии методов расстановки можно почерпнуть в книгах .Морриса [1968], Ахо, Ульмана [1973] и Кнута [1973а] Последняя содержит

1) Кнут [1973а, §6.4] дает краткую историю возникновения и развития этих методов, а также интересное объяснение употребляемого в литературе на английском языке термина «hashing». По свидетельству Кнута, это слово «в разных частях света уже стало общепринятым жаргоном». В нащу литературу также

7* 195



проник уже этот жаргон: хеширование, хеш-таблицы, хеш-функции. В данной книге мы вслед за переводчиками двухтомного труда Ахо, Ульмана [1972, 1973] называем эти методы методами расстановки.- Прим. ред.

также информацию о деревьях двоичного поиска. Алгоритм 4.2 для построения статического дерева двоичного поиска заимствован у Гилберта, Мура [1959]. Алгоритм сложности 0(п) для той же задачи можно найти у Кнута [1971], где содержится также и решение упр. 4.6. Ху, Таккер [1971] показали, что время 0{гг) и память 0(п) достаточны, чтобы построить оптимальное дерево двоичного поиска, в котором данные появляются только на листьях. Кнут [1973а] дал реализацию этого алгоритма за время О(п logn).

Рейнгольд [1972] приводит оптимальные алгоритмы для многих основных преобразований множеств, таких, как объединение и пересечение. Алгоритм 4.3 для задачи ОБЪЕДИНИТЬ - НАЙТИ был, по-видимому, впервые применен Мак-Илроем и Моррисом. Кнут [1969] приписывает сжатие путей Триттеру. Теорема 4.4 взята у Хопкрофта, Ульмана [1974], а теорема 4.5 - у Тарьяна [1974]. Приложение к приравниванию идентификаторов и вычислению смещения, обсуждавшиеся в разд. 4.8, заимствованы у Галлера, Фишера [1964]. Приложение 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 содержится у Ахо, Хопкрофта, Ульмана [1974].

Различие между префиксным и свободным режимами работы алгоритмов ввели Хартманис, Льюис, Стирнз [1965]. Рабин [1963] изучил важный частный случай префиксных вычислений, называемый вычислением в реальное время.

Алгоритм разбиения и приложение к минимизации числа состояний конечного автомата взяты из статьи Хопкрофта [1971].





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 [61] 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002