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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

на a", "пометка на a меньше любой пометки на Q" и  т.д.,  но  мы
позволим  себе  этого не делать). Точно того же требует упорядо-
ченность дерева с корнем b, его левым сыном a, в котором P и Q -
левое и правое поддеревья a, R -  правое  поддерево  b.  Поэтому
первое дерево можно преобразовать во второе, не нарушая упорядо-
ченности.  Такое  преобразование  назовем малым правым вращением
(правым - поскольку существует симметричное, левое, малым - пос-
кольку есть и большое, которое мы сейчас опишем).

     Пусть b - правый сын a, c - левый сын b, P -левое поддерево
a, Q и R -левое и правое поддеревья c, S - правое  поддерево  b.
Тогда P < a < Q < c < R < b < S.








Такой же порядок соответствует дереву с корнем c, имеющим левого
сына a и правого сына b, для которого P и Q - поддеревья вершины
a,  а R и S - поддеревья вершины b. Соответствующее преобразова-
ние будем называть большим правым вращением. (Аналогично опреде-
ляется симметричное ему большое левое вращение.)

     12.2.3. Дано дерево, сбалансированное всюду, кроме корня, в
котором разница высот равна 2 (т.е. левое  и  правое  поддеревья
корня сбалансированы и их высоты отличаются на 2). Доказать, что
оно  может  быть  превращено в сбалансированное одним из четырех
описанных преобразований, причем высота  его  останется  прежней
или уменьшится на 1.

     Решение.  Пусть более низким является, например, левое под-
дерево, и его высота равна k.  Тогда  высота  правого  поддерева
равна k+2. Обозначим корень через a, а его правого сына (он обя-
зательно  есть)  через  b.  Рассмотрим левое и правое поддеревья
вершины b. Одно из них обязательно имеет высоту  k+1,  а  другое
может  иметь  высоту  k или k+1 (меньше k быть не может, так как
поддеревья сбалансированы). Если высота левого  поддерева  равна
k+1,  а  правого  - k, до потребуется большое правое вращение; в
остальных случаях помогает малое.

------------------------------------
------------------------------------
------------------------------------

                                        высота уменьшилась на 1



------------------------------------
------------------------------------
------------------------------------

                                         высота не изменилась



   k-1 или k (в одном из случаев k)

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 Большая Одесская Библиотека.