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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



Этот день в истории
В 1681 году скончался(-лась) Педро Кальдерон


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

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

  | left [b] := left [a] {поддерево P}
  | left [a] := b;
  | diff [b] := h_Q - h_P;
  | diff [a] := h_R - (max (h_P, h_Q) + 1);
  end;

  procedure BR (a:integer);{большое правое вращение с корнем a}
  | var b,c: 1..n; val_a,val_b,val_c: T;
  |     h_P,h_Q,h_R,h_S: integer;
  begin
  | b := right [a]; c := left [b]; {b,c <> null}
  | val_a := val [a]; val_b := val [b]; val_c := val [c];
  | h_Q := 0; h_R := diff[c]; h_S := (max(h_Q,h_R)+1)+diff[b];
  | h_P := 1 + max (h_S, h_S-diff[b]) - diff [a];
  | val [a] := val_c; val [c] := val_a;
  | left [b] := right [c] {поддерево R}
  | right [c] := left [c] {поддерево Q}
  | left [c] := left [a] {поддерево P}
  | left [a] := c;
  | diff [b] := h_S - h_R;
  | diff [c] := h_Q - h_P;
  | diff [a] := max (h_S, h_R) - max (h_P, h_Q);
  end;

Левые вращения (большое и малое) записываются симметрично.

     Процедуры  добавления  и  удаления  элементов  пишутся  как
раньше, но только добавление и  удаление  должно  сопровождаться
коррекцией  массива  diff  и восстановлением сбалансированности.
При этом используется процедура с такими свойствами:

   дано:  левое и правое поддеревья вершины с номером a сбалан-
       сированы, в самой вершине разница высот не больше  2,  в
       поддереве с корнем a массив diff заполнен правильно;
   надо:  поддерево с корнем a сбалансировано и массив diff со-
       ответственно изменен, d - изменение его высоты (равно  0
       или -1); в остальной части все осталось как было}

  procedure balance (a: integer; var d: integer);
  begin {-2 <= diff[a] <= 2}
  | if diff [a] = 2 then begin
  | | b := right [a];
  | | if diff [b] = -1 then begin
  | | | BR (a); d := -1;
  | | end else if diff [b] = 0 then begin
  | | | SR (a); d := 0;
  | | end else begin {diff [b] = 1}
  | | | SR (a); d := - 1;
  | | end;
  | end else if diff [a] = -2 then begin
  | | b := left [a];
  | | if diff [b] = 1 then begin
  | | | BL (a); d := -1;
  | | end else if diff [b] = 0 then begin
  | | | SL (a); d := 0;
  | | end else begin {diff [b] = -1}
  | | | SL (a); d := - 1;
  | | end;
  | end else begin {-2 < diff [a] < 2, ничего делать не надо}
  | | d := 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 : 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 Большая Одесская Библиотека.