Случайный афоризм
Стихи никогда не доказывали ничего другого, кроме большего или меньшего таланта их сочинителя. Федор Иванович Тютчев
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

  | if x = root then begin
  | | root := right [x];
  | end else if direction = l then begin
  | | left [father] := right [x];
  | end else begin {direction = r}
  | | right [father] := right [x];
  | end;
  end else if (left[x] <> null) and (right[x]=null) then begin
  | ..симметрично
  end else begin {left [x] <> null, right [x] <> null}
  | ..удалить вершину с двумя сыновьями
  end;

Удаление вершины с двумя сыновьями нельзя сделать просто так, но
ее  можно предварительно поменять с вершиной, пометка на которой
является непосредственно следующим (в порядке возрастания)  эле-
ментом за пометкой на x.

    y := right [x];
    father := x; direction := r;
    {теперь father и direction относятся к вершине y}
    while left [y] <> null do begin
    | father := y; direction := r;
    | y := left [y];
    end;
    {val [y] - минимальная из пометок, больших val [x],
     y не имеет левого сына}
    val [x] := val [y];
    ..удалить вершину y (как удалять вершину, у которой нет ле-
      вого сына, мы уже знаем)

     12.1.6. Упростить программу удаления, заметив, что  некото-
рые случаи (например, первые два из четырех) можно объединить.

     12.1.7.  Использовать упорядоченные деревья для представле-
ния функций, область определения которых  -  конечные  множества
значений типа T, а значения имеют некоторый тип U. Операции: вы-
числение  значения  на  данном  аргументе, изменение значения на
данном аргументе, доопределение  функции  на  данном  аргументе,
исключение элемента из области определения функции.

     Решение. Делаем как раньше, добавив еще один массив

         func_val: array [1..n] of U;

если val [x] = t, func_val [x] = u, то значение хранимой функции
на t равно u.

     Оценка количества действий.

     Для  каждой из операций (проверки, добавления и исключения)
количество действий не превосходит  C  *  (высота  дерева).  Для
"ровно подстриженного" дерева (когда все листья на одной высоте)
высота  по порядку величины равна логарифму числа вершин. Однако
для кривобокого дерева все может быть гораздо хуже: в  наихудшем
случае  все  вершины  образуют цепь и высота равна числу вершин.
Так случится, если элементы множества добавляются в возрастающем
или убывающем порядке. Можно доказать, однако, что при  добавле-
нии  элементов "в случайном порядке" средняя высота дерева будет
не больше C * (логарифм числа вершин). Если этой оценки "в сред-

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 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.