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

УПРАЖНЕНИЯ

сыном корня большего дерева, но не использует сжатие путей. Докажите, что верхнюю границу 0{n\ogn) нельзя улучшить. Иными словами покажите, что для некоторой постоянной с и произвольно больших значений п существуют последовательности операций ОБЪЕДИНИТЬ и НАЙТИ, требующие сп log п шагов.

**4Л6. Пусть Т{п) - временная сложность (в худшем случае) выполнения п операций ОБЪЕДИНИТЬ и НАЙТИ при условии, что применяется древовидная структура из разд. 4.7 и сжатие путей для операций НАЙТИ, но операция ОБЪЕДИНИТЬ (Л, В, С) выполняется так: корень дерева А становится сыном корня дерева В независимо от того, какое множество больше. Покажите, что Г (n)fei« log« для некоторой постоянной fei>0.

**4.17. Покажите, что Г («)2« log« для некоторой постоянной ki, где Т (п) обозначает то же, что и в упр. 4.16.

**4.18. Покажите, как можно вьшолнить последовательность из п операций ОБЪЕДИНИТЬ, НАЙТИ, ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ, УДАЛИТЬ на множестве целых чисел 1, 2, . . ., « за время О {nG{n)). При этом считайте, что УДАЛИТЬ(1, S) делает i членом нового множества {i}, которому надо присвоить (произвольное) имя. Это множество можно впоследствии слить с другим. Кроме того, предположите, что никакой элемент не принадлежит более чем одному множеству.

4.19. Обобщите МШ-задачу для свободного режима так, чтобы можно было выполнять операцию MIN вида MlN(i), которая находит все целые числа, меньшие i, вставленные до нее и еще не найденные предыдущей операцией MIN.

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

4.21. Обобщите МШ-задачу для свободного режима следующим образом. Пусть Т - дерево с п узлами. Каждому узлу ставится в соответствие целое число от 1 до «. Некоторым узлам приписаны операции ИЗВЛЕЧЬ.МШ. Пройдите дерево в обратном порядке. Встретив операцию ИЗВЛЕЧЬ М1Н в узле v, найдите в дереве с корнем V наименьшее целое число (исключая число в самом узле v) среди тех чисел, которые не были удалены ранее, и удалите его. Укажите алгоритм для этого процесса, работающий в свободном режиме и имеющий сложность 0(nG(«)).

**4.22. Разработайте алгоритм сложности О (« log log п) для задачи ОБЪЕДИНИТЬ - НАЙТИ, пользуясь структурой данных, со-



Текущее состояние

состояние

Вход 0 1

Следуиицее состояние

Следуюиее состояние

Начальными состояниями являются 1 и А соответственно, а множествами заключительных состояний - множества {5} и {С, Е) соответственно.

4.26. Напишите полные программы для выполнения операций на 2-3-деревьях:

(а) УДАЛИТЬ,

(б) ОБЪЕДИНИТЬ,

(в) ПРИНАДЛЕЖАТЬ (в предположении, что множество листьев упорядочено и каждый узел помечен номером самого высокого листа среди всех листьев, с которыми он соединен),

(г) РАСЦЕПИТЬ (в предположении, что задан лист, по которому производится расцепление, и множество листьев упорядочено).

стоящей из дерева, каждый лист которого отстоит от корня на расстояние 2. Ограничьте степень корня числом между 1 и n/logn, а степень каждого его сына - числом между 1 и logn. Как модифицировать этот алгоритм, чтобы он делал не более О (п log log log n) шагов? Какую наилучшую границу на время можете вы получить, обобщая этот метод?

4.23. Покажите, как можно хранить в таблице символов смещения от начала отсчета, упомянутые в приложении 2 разд. 4.8. Указание: Примените технику, использованную для определения глубины.

4.24. Напишите программу для операций ОБЪЕДИНИТЬ и НАЙТИ, осуществляющую вычисления с весом, как в приложении 2 разд. 4.8.

4.25. С помощью алгоритма на рис. 4.25 выясните эквивалент-кость конечных автоматов

Вход



4.27. Напишите полную программу для вставки нового узла в 2-3-дерево, предполагая, что множество листьев упорядочено.

4.28. Напишите программы для основных операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ, УДАЛИТЬ, MIN, ОБЪЕДИНИТЬ и НАЙТИ, используя 2-3-деревья с метками НАИМЕНЬШИЙ из разд. 4.П. Универсальным множеством считайте {1, 2, . . ., п}.

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

Определение. АВЯ-деревом ) называют такое дерево двоичного поиска, что для каждого узла v высоты его левого и правого поддеревьев отличаются не более чем на единицу. Если какого-то поддерева нет, его "высота" считается равной -1.

Пример 4.14. Дерево на рис. 4.37 не является АВЛ-деревом, потому что высота левого поддерева узла * равна 2, а правого - 0. Во всех остальных узлах АВЛ-условие выполняется. □

4.30. Покажите, что АВЛ-дерево высоты h содержит не более 2*+1-1 и не менее

5 + 2 15/1+ V"5\ , 5-2 Vl>(\- V~\ -5-V-J -

узлов.

*4.31. Пусть Т - дерево двоичного поиска с п узлами, обладающее АВЛ-свойством. Напишите алгоритм сложности О (log л)


Рис. 4.37. Не АВЛ-дерево.

1) В честь его авторов Г. М. Адельсона-Вельского и Е. М. Ландиса; см. их работу [1962].





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