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

элементы в левом и правом сыновьях (если они существуют) того узла, в котором хранится A[i].

Например, сортирующее дерево на рис. 3.5 можно представить массивом

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

Не каждое сортирующее дерево можно представить таким способом. На языке представления деревьев можно сказать, что для образования такого массива требуется, чтобы листья самого низкого уровня стояли как можно левее (как, например, на рис. 3.5).

Если сортирующее дерево представляется описанным массивом, то некоторые операции из алгоритма Сортдеревом легко выполнить. Например, согласно алгоритму, нужно удалить элемент из корня, где-то запомнить его, переделать оставшееся дерево в сортирующее и удалить непомеченный лист. Можно удалить наибольший элемент из сортирующего дерева и запомнить его, поменяв местами All] и А1п], и затем не считать более ячейку п нашего массива частью сортирующего дерева. Ячейка п рассматривается как лист, удаленный из этого дерева. Для того чтобы переделать дерево, хранящееся в ячейках 1,2, . . ., п-1, в сортирующее, надо взять новый элемент Л[1] и провести его вдоль подходящего пути в дереве. Затем можно повторить процесс, меняя местами Л[1] и Л [п-1] и считая, что дерево занимает ячейки 1,2.....п-2 и т. д.

Пример 3.4. Рассмотрим на примере сортирующего дерева рис. 3.5, что происходит, когда мы поменяем местами первый и последний элементы массива, представляющего это дерево. Новый массив

соответствует помеченному дереву на рис. 3.6,а. Элемент 16 исключается из дальнейшего рассмотрения. Чтобы превратить полученное дерево в сортирующее, надо поменять местами элемент 4 с большим из его сыновей, т. е. с элементом 11.

В своем новом положении элемент 4 обладает сыновьями 10 и 5. Так как они больше 4, то 4 переставляется с 10, большим сыном. После этого сыновьями элемента 4 в новом положении становятся 1 и 2. Поскольку 4 превосходит их обоих, дальнейшие перестановки не нужны.




Рис. 3.6. а - результат перестановки элементов 4 и 16 в сортирующем дереве рис. 3.5; б - результат перестройки сортирующего дерева и удаления элемента 16.

Полученное в результате сортирующее дерево показано на рис. 3.6,6. Заметим, что хотя элемент 16 был удален из сортирующего дерева, он все же присутствует в конце массива А. □

Теперь перейдем к формальному описанию алгоритма Сорт-деревом.

Пусть «1, «2, • • •. й„- последовательность сортируемых элементов. Предположим, что вначале они помещаются в массив А именно в этом порядке, т. е. A{i]=ai, l<i<n. Первый шаг состоит в построении сортирующего дерева, т. е. элементы в А перераспределяются так, чтобы удовлетворялось свойство сортирующего дерева: АЦ]АШ] при l<i<n/2 и АШАШ+и при l<i<n/2. Это делают, строя, начиная с листьев, все большие и большие сортирующие деревья. Всякое поддерево, состоящее из листа, уже является сортирующим. Чтобы сделать поддерево высоты h сортирующим, надо переставить элемент в корне с наибольшим из элементов, соответствующих его сыновьям, если, конечно, он меньше какого-то из них. Такое действие может испортить сортирующее дерево высоты h-1, и тогда его надо снова перестроить в сортирующее. Приведем точное описание этого алгоритма.

Алгоритм 3.3. Построение сортирующего дерева

Вход. Массив элементов АН], 1</<п.

Выход. Элементы массива А, организованные в виде сортирующего дерева, т. е. АЦ]А1\ п/2 J] для 1<г<п.

Метод. В основе алгоритма лежит рекурсивная процедура ПЕРЕСЫПКА. Ее параметры i и / задают область ячеек массива А, обладающую свойством сортирующего дерева; корень строящегося дерева помещается в t.



procedure ПЕРЕСЫПКА (i, /):

1. if i-не лист и какой-то его сын содержит элемент, пре-

восходящий элемент в i tfien begin

2. пусть Л-тот сын узла i, в котором хранится

наибольший элемент;

3. переставить A[i] и A[k];

4. ПЕРЕСЫПКА (/г, /) end

Параметр / используется, чтобы определить, является ли i листом и имеет он одного или двух сыновей. Если i>]/2, то i - лист, и процедуре ПЕРЕСЫПКА (i, }) ничего не нужно делать, поскольку АШ - уже сортирующее дерево.

Алгоритм, превращающий весь массив Л в сортирующее дерево, выглядит просто:

procedure ПОСТРСОРТДЕРЕВА:

for in) step -1 until 1 do ПЕРЕСЫПКА (i, n) □

Покажем, что алгоритм 3.3 преобразует Л в сортирующее дерево за линейное время.

Лемма 3.2. Если узлы t+1, г+2, . . ., п являются корнями сортирующих деревьев, то после вызова процедуры ПЕРЕСЫПКА (i, п) все узлы i, i+l, . . ., п будут корнями сортирующих деревьев.

Доказательство. Доказательство проводится возвратной индукцией по i.

Базис, т. е. случай i=n, тривиален, так как узел п должен быть листом и условие, проверяемое в строке 1, гарантирует, что ПЕРЕСЫПКА (п, п) ничего не делает.

Для шага индукции заметим, что если i - лист или у него нет сына с большим элементом, то доказывать нечего (как и при обосновании базиса). Но если у узла i есть один сын (т. е. если 2i=n) и Л[Л<Л[21], то строка 3 процедуры ПЕРЕСЫПКА переставляет АШ и A[2i]. В строке 4 вызывается ПЕРЕСЫПКА(2i, п); поэтому из предположения индукции вытекает, что дерево с корнем 2i будет переделано в сортирующее. Что касается узлов i+l, i+2, .. . . . ., 2i-1, то они и не переставали быть корнями сортирующих деревьев. Так как после этой новой перестановки в массиве А выполняется неравенство Л[г]>Л[2Л, то дерево с корнем / также оказывается сортирующим.

Аналогично, если узел i имеет двух сыновей (т. е. если 2г+1<п) и наибольший из элементов в A[2i] и в Л[21+11 больше элемента

*) На практике мы бы начали с [ n/2J,





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