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

Структура данных

Тип универсума

Допустимые операции

Время выполнения п операций над множествами размера п

среднее

в худшем случае

Таблица расстановки

Любое множество, на котором можно вычислять функцию расстановки

ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ

0(п)

Дерево

двоичного

поиска

Любое упорядоченное множество

ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ MIN

0(п log п)

Древовидная структура из алгоритма 4.3

Множество целых чисел от 1 до п

ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ ОБЪЕДИНИТЬ НАЙТИ

не более 0{nG{n))

не более 0(п G (п))

2-3-деревья с неупорядоченным множеством листьев

Любое упорядоченное множество

ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ ОБЪЕДИНИТЬ НАЙТИ MIN

0(« log п.)

0{п logn)

2-3-деревья с упорядоченным множеством листьев

Любое упорядоченное множество

ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ НАЙТИ РАСЦЕПИТЬ СЦЕПИТЬ MIN

0{п log п)

0{п log п)

Рис. 4.36. Сводка свойств структур данных.

4.14. РЕЗЮМЕ

На рис. 4.36 приведены различные структуры данных, рассмотренные в этой главе, типы операций, которые можно совершать на их основе, и принимаемые нами соглашения о размере и природе того универсального множества, откуда брались элементы.



УПРАЖНЕНИЯ

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

4.2. Пусть элементами являются цепочки из букв и используется следующая функция расстановки для таблицы размера т=5: сложить "значения" букв, где А имеет значение I, В - значение 2 и т. д.; разделить результат на 5 и взять остаток. Выпишите содержимое таблицы расстановки и списков, при условии что вставляются цепочки DASHER, DANCER, PRANCER, VIXEN, COMET, CUPID, DONNER, BLITZEN.

4.3. Вставьте восемь цепочек из упр. 4.2 в дерево двоичного поиска. Какую последовательность узлов надо посетить, чтобы проверить, принадлежит ли RUDOLPH этому множеству?

4.4. Покажите, что процедура ПОИСК (рис. 4.3) дает наименьшее возможное среднее время поиска, если все элементы универсального множества разыскиваются с равной вероятностью.

4.5. Найдите оптимальное дерево двоичного поиска для а, Ь, ... .. . ,h, если эти элементы имеют вероятности соответственно 0,1; 0,2; 0,05; 0,1; 0,3; 0,05; 0,15; 0,05, а вероятность всех остальных равна 0.

**4.6. Покажите, что в алгоритме 4.2 можно ограничить поиск числа т в строке 8 на рис. 4.9 областью позиций от rtj-i до rt+ij и все равно с гарантией находить максимум.

*4.7. Используйте упр. 4.6 для такого изменения алгоритма 4.2, чтобы он работал время О(п).

4.8. Закончите доказательство теоремы 4.2, показав, что алгоритм построения дерева на рис. 4.10 работает правильно.

4.9. Закончите доказательство теоремы 4.3.

*4.10. Постройте интерфейс для перевода множества п внешних имен, лежащих между 1 и г, в множество внутренних имен, состоящее из целых чисел от 1 до п. Этот интерфейс должен переводить в обе стороны в предположении, что гп.

(а) Разработайте интерфейс с хорошим поведением в среднем.

(б) Разработайте интерфейс с хорошим поведением в худшем случае.



*4.11. Найдите эффективную структуру данных для представления подмножества S целых чисел, лежащих между 1 и п. Мы хотим выполнять на множестве следующие операции:

1) выбирать и удалять из него какой-то один его элемент,

2) добавлять в него целое число /.

Предполагается, что механизм не должен добавлять в S целое число г, если оно уже есть там. Структура данных должна быть такой, чтобы время на выборку и удаление элемента и время на добавление элемента не зависели от S.

4.12. Найдите дерево, которое получается, когда алгоритм 4.3 выполняет последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, порождаемую следующей программой. Допустим, что множестю i вначале есть {i} для lt 6.

begin

for i -1 step 2 until 15 do ОБЪЕДИНИТЬ (t, i + l, i);

for i -1 step 4 until 13 do ОБЪЕДИНИТЬ (i, i-f 2, i);

ОБЪЕДИНИТЬ (1, 5, 1);

ОБЪЕДИНИТЬ (9, 13, 9);

ОБЪЕДИНИТЬ (1, 9, 1);

for step 4 until 13 do НАЙТИ (i)

4.13. Пусть a - последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, причем все операции ОБЪЕДИНИТЬ входят в а перед операциями НАЙТИ. Докажите, что алгоритм 4.3 выполняет а за время, пропорциональное а.

4.14. So-depeeoM назовем дерево, состоящее из единственного узла. Si-дерево для f>0 получается операцией, которая делает корень одного 5, 1-дерева сыном корня другого Sj-i-дерева. Докажите, что

(а) 5„-дерево имеет (JJ узлов высоты h,

(б) 5„-дерево можно получить из 5„-дерева, тп, заменив каждый узел 5„-дерева на 5„ и-дерево так, что сыновья этого узла становятся сыновьями корня подставляемого 5„-„-дерева,

(в) 5„-дерево содержит узел с п сыновьями; они служат корнями So-, Si-, . . ., Sn-1-деревьев.

4.15. Рассмотрим алгоритм объединения непересекающихся множеств, который делает корень дерева с меньшим числом узлов (в случае одинакового количества узлов выбор дерева произволен)





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.0037