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

Доказательство. Пусть Т(п) - число сравнений, производимых между элементами последовательности аи Оа, . . ., а„ при построении дерева двоичного поиска, Г(0)=0. Пусть bi, b, . . . . . ., Ьп- та же последовательность в порядке возрастания.

Если Oi, йа, . . ., а„ - случайная последовательность элементов, то fli с равной вероятностью совпадает с bj для любого /, Элемент Oi становится корнем дерева двоичного поиска, и в окончательном дереве /-1 элементов bi, Ьц, . . ., будут находиться в левом поддереве корня и п-/ элементов Ь, bj+,, . . ., 6„- в правом поддереве.

Подсчитаем среднее число сравнений, необходимых для вставки элементов bi, bi, . . ., bj-i в дерево. Каждый из этих элементов когда-нибудь сравнивается с корнем, и это дает /-1 сравнений с корнем. Затем по индукции получаем, что еще потребуется T(j-1) сравнений, чтобы вставить bi, Ьг, . . ., bj-i в левое поддерево. Итак, необходимо /-14-Г(/-1) сравнений, чтобы вставить Oi, Оа, . . .

в дерево двоичного поиска. Аналогичной-/+Т(п-/) сравнений потребуется, чтобы вставить в дерево элементы bj+y, bj+г,. . ., 6„.

Поскольку / с равной вероятностью принимает любое значение от 1 до п, то

T(n)-l(n-l+T(j-l) + T{n-j)), (4.1)

или, с учетом простых алгебраических преобразований,

T(n) = n-H-i;T(/). (4.2)

Способом, описанным в разд. 3.5, можно показать, что Т (п) < kn log п,

где &=1п 4=1,39. Таким образом, в среднем на вставку п элементов в дерево двоичного поиска тратится О (п log п) сравнений. □

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



Q end then



1) (2

Рис. 4.7. Дерево двоичного поиска с добавленными листьями.

4.5. ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА

В разд. 4.3 по данному множеству S = {ai, а, . . ., а„}, являющемуся подмножеством некоторого большого универсального множества и, строилась структура данных, позволяющая эффективно выполнить последовательность а, составленную только из операций ПРИНАДЛЕЖАТЬ. Рассмотрим снова эту задачу, но теперь предположим, что кроме множества S задается для каждого aU вероятность появления в а операции ПРИНАДЛЕЖАТЬ (а, S). Теперь нам хотелось бы построить дерево двоичного поиска для S так, чтобы последовательность а операций ПРИНАДЛЕЖАТЬ можно было выполнить в префиксном режиме с наименьшим средним числом сравнений.

Пусть ai, Cj, • Un - элементы множества S в порядке возрастания и Pi - вероятность появления в о операции ПРИНАДЛЕЖАТЬ (а,, S). Пусть (/о - вероятность появления в а операции ПРИНАДЛЕЖАТЬ (а, S) для некоторого а <аь а (/j - вероятность появления в а операции ПРИНАДЛЕЖАТЬ (а, S) для некоторого а, ai<.a<.ai+i. Наконец, пусть </„- вероятность появления в а операции ПРИНАДЛЕЖАТЬ (а, S) для некоторого а>а„. Для определения стоимости дерева двоичного поиска удобно добавить к нему п+1 фиктивных листьев, чтобы отразить элементы из U-S. Мы будем обозначать эти листья числами О, 1, . . ., п.

На рис. 4.7 показано дерево двоичного поиска, изображенное на рис. 4.4, с добавленными фиктивными листьями. Например, лист с меткой 3 представляет те элементы а, для которых end<;a<; <if.




Рис. 4.8, Поддерево Г ,

Нам надо определить стоимость дерева двоичного поиска. Если элемент а равен метке / (и) некоторого узла и, то число узлов, посещенных во время выполнения операции ПРИНАДЛЕЖАТЬ (а, S), на единицу больше глубины узла и. Если aS и ai<.a<iai+i, то число узлов, посещенных при выполнении операции ПРИНАДЛЕЖАТЬ (а, S), равно глубине фиктивного листа i. Поэтому стоимость дерева двоичного поиска можно определить как

2 Pi (ГЛУБИНА (а..) +1) + Д </, ГЛУБИНА (i).

Теперь, если у нас есть дерево двоичного поиска Т, обладающее наименьшей стоимостью, мы можем выполнить последовательность операций ПРИНАДЛЕЖАТЬ с наименьшим средним числом посещений узлов, просто применив для выполнения каждой операции ПРИНАДЛЕЖАТЬ алгоритм 4.1 на Т.

Если даны числа pt и qt, то как найти дерево наименьшей стоимости? Подход "разделяй и властвуй" предлагает определить элемент Ui, который надо поставить в корень. Это разбило бы данную задачу на две подзадачи: построение левого и правого поддеревьев. Однако, похоже, нет легкого пути определения корня без решения всей задачи. Поэтому придется решать 2п подзадач: по две для каждого возможного корня. Это естественно приводит к решению с помощью динамического программирования.

Для 0<i</<rt обозначим через Tfj дерево наименьшей стоимости для подмножества {aj+i, flj+a, . . ., aj}. Пусть Cij - стоимость дерева Ttj, а а,,- его корень. Вес Wij дерева определяется как

9,-+(Pi+i+?i+i)+. • -\-{Р1+ч1)-

Дерево Ti) состоит из корня а, левого поддерева Ti-i (т. е. дерева наименьшей стоимости для {ai+t, flj+g, . . ., Uh-i}) и правого поддерева Tj (т. е, дерева наименьшей стоимости для {а+и ft+a, ... . . ., й]}); см. рис. 4.8. Если i=k-\, то петлевого поддерева, а при k=j нет правого поддерева. Для удобства мы будем трактовать Тц как пустое дерево. Вес Шц дерева Тц равен qi, а его стоимость Сц равна 0.





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