Анимация
JavaScript

Главная  Библионтека 

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

щую операцию несколько раз, пока Р не станет равным Q: если К < KEY(P),

установить В (Р) •<--1 и Рч- LLINK(Р); если К > КЕУ(Р), установить В(Р) •(- +1

и Р •(- RLINK(P). (Если К = KEY(P), то Р = Q и перейти к следующему шагу.)

А7. [Балансировка.] На этом шаге возможны несколько вариантов.

i) Если B(S) = О (дерево стало выше), установить B(S) 4- а, LLINK(HEAD) 4- LLINK (HEAD) + 1 и прекратить выполнение алгоритма.

ii) Если B(S) = -а (дерево стало более сбалансированным), установить В(S) <- О и прекратить выполнение алгоритма.

iii) Если B(S) = а (дерево разбалансировано), перейти к шагу А8 при В(Я) = а или к шагу А9 при В(Я) = -а.

(Случай (iii) соответствует ситуации, приведенной в (1), при а - +1; S и R указывают на узлы А и В соответственно, LINK(-o,S) указывает на а и т. д.)

А8. [Однократный поворот.] Установить Р •(-R, LINK(o,S)(-LINK(-o,R), LINK (-о,R) i-S, B(S) I- B(R) +- 0. Перейти к шагу AlO.

А9. [Двукратный поворот.] Установить Р •(-LINK (-о, R), LINK(-o,R) 4-LINK(o,P), LINK(o,P) Ч-R, LINK(o,S) I-LINK(-a,P), LINK(-o,P) I-S; присвоить сначала

{(-0,0), еслиВ(Р)= о; ( 0,0), еслиВ(Р) = 0; (3)

( О,о), если В(Р) = -о;

а затем - В(Р) •(- 0. А10. [Последний штрих.] (Балансирующее преобразование (1) в (2) завершено; Р указывает на корень нового поддерева, а Т - на родительский по отношению к корню старого поддерева узел S.) Если S = RLINK(Т), следует установить RLINK(Т) •(- Р; в противном случае следует установить LLINK(Т) •(- Р.

Этот алгоритм достаточно длинный, однако разделяется на три простые части: на шагах А1-А4 осуществляется поиск, на шагах А5-А7 - вставка нового узла и на шагах А8-А10 при необходимости ребалансируется дерево. Тот же алгоритм может использоваться и для прошитых деревьев (см. упр. 6.2.2-2).

Известно, что для этого алгоритма требуется около ClogN единиц времени, где С - некоторая константа. Однако следует оценить ее величину, чтобы знать, при каких N использование сбалансированных деревьев становится эффективнее других алгоритмов. Приведенная ниже MIX-реализация алгоритма позволяет приступить к решению этого вопроса.

Программа А {Поиск со вставкой по сбалансированному дереву). Эта программа, реализующая алгоритм А, использует узлы дерева в следующем формате:

LLINK

RLINK

гА = К, ill = Р, г12 = Q, г13 = R, г14 = S, г15 = Т. Код шагов А7-А9 дублируется, так что значение а используется в программе в неявном виде.

01 В EQU 0:1

02 LLINK EQU 2:3



RLINK EQU

START LDA

Al. Инициализация.

ENT5

HEAD

Т 4- HEAD.

0,5(RLINK)

Q f-RLINK (HEAD).

Переход к A2 с S <- P Q.

0,1(RLINK)

A4. Перемещение вправо. Q <- RLINK (?)

Переход к шагу A5 при Q = Л,

0,2(B)

rX4-B(Q).

Переход, если B(Q) =0.

ENT5 0,1

Т •<-?.

ENT4

S •(-, Q.

ENTl

Р 4- Q.

CMPA

\2. Сравнение.

Переход к шагу А4, если К > KEY(P).

SUCCESS

Выход при К = KEY(P).

0,1(LLINK)

Cl-S

A3. Перемещение влево. 0 4- LLINK (?).

J2NZ

Cl-S

Переход при Q # Л.

AVAIL

А5. Вставка.

OVERFLOW

0,2(RLINK)

AVAIL

Q AVAIL.

KEY(Q) 4-К.

LLINK(Q) <- RLINK(Q) 4- Л.

К < mY(p)>

0,1(RLINK)

RLINK (?) <r- Q

0,1(LLINK)

1-S-A

LLINK(?) 4- Q.

CMPA

A6. Корректировка фактора сбалансированности.

Переход при А < КЕУ(З).

0,4(RLINK)

R4- RLINK(S).

0,4(LLINK)

1-S-E

Rf-LLINK (S).

ENTl

Р R.

ENTX

rX4- -1.

Переход к циклу сравнения.

F2 + 1-S

Переход к шагу А7, если К = KEY(?).

0,1(1:1)

В(Р) <- +1 (было +0).

0,1(RLINK)

? 4-RLINK (Р).

CMPA

F + l-S

F + l-S

Переход при К > KEY(P).

0,1(B)

В(Р) <- -1.

0,1(LLINK)

Р LLINK (?).

Переход к циклу сравнения.

0,4(B)

А7. Балансировка. г12 4-B(S).

0,4(B)

B(S) 4- 0.

CMPA

Переход к подпрограмме а = +1 при К > KEY(S).

DONE

Выход при г12 = -а.

С1 +Л

Переход, если B(S) было равно 0.



ENTl

P R.

0,3(B)

rI2 4-B(R),

Переход к шагу A8 при rI2 = а.

0,3(RLINK)

А9. Двукратный поворот.

0,1(LLINK)

ЫЫК(а,Р •(-LINK(-a,R))

0,3(RLINK)

LINK (-а, R).

0,1(LLINK)

LINK (а, Р) f-R.

0,1(B)

rI2 4-В(Р).

Tl,2

-а, 0 или 0

0,4(B)

•B(S).

T2,2

0, 0 или о

0,3(B)

B(R).

0,1(RLINK)

AS. Однократный поворот.

0,4(LLINK)

LINK(a,S) 4-LINK(-a,P).

0,1(RLINK)

LINK (-а,Р) S.

Объединение с другой ветвью.

DONE

Выход при г12 = -а.

G2 + J2

Переход, если B(S) было равно 0.

ENTl

P4-R.

0,3(B)

rI2 4-B(R).

Переход к шагу А8 при г12 = а.

0,3(LLINK)

А9. Двукратный поворот.

0,1(RLINK)

LINK(a,P <-LINK(-a,R))

0,3(LLINK)

LINK(-a,R).

0,1(RLINK)

LINK (а, Р) •<-R.

0,1(B)

rl2 .f-BCP).

T2,2

-a, 0 или 0

0,4(B)

B(S).

Tl,2

0, 0 или a

0,3(B)

-> B(R).

O.KLLINK)

A8. Однократный поворот.

0,4(RLINK)

LINK(a,S) <-LINK(-a,P).

O.KLLINK)

LINK(-a,P) Ч- S.

0,KB)

B(P) Ч-0.

CMP4

0.5(RLINK)

AlO. Последний штрих.

Переход при RLINK (Т) # S.

0,5(RLINK)

RLINK (Т) P.

DONE

Выход.

0,5(LLINK)

LLINK (Т) <-P.

DONE

Выход.

Таблица для (3).

ENTX

гХч-+1.

0,4(B)

B(S) <- а.

HEAD(LLINK)

LLINK(HEAD)

INCX

HEAD(LLINK)

Ч- LLINK (HEAD).

DONE

Вставка завершена.



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