Методы программирования. Громов Ю.Ю - 118 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

118
будет обсуждаться ниже). Также предполагается, что дерево непустое,
т.е. RLINK(HEAD) ≠ Λ.
Для удобства описания в алгоритме используется обозначение
LINK(a, Р) для LLINK(Р) при а = –1 и для RLINK(Р) при а = +1.
А1. [Инициализация.] Присвоить Т ← НЕАD, S ← Р ← RLINK(НЕАD).
(Переменная-указатель Р будет двигаться вниз по дереву; S будет указы-
вать на место, где может потребоваться балансировка, а Т – на родитель-
ский по отношению к S узел.)
А2. [Сравнение.] Если K < KЕY(Р), то перейти к шагу А3; если
K > KЕY(Р), перейти к шагу А4; если K = KЕY(Р), поиск успешно завершён.
А3. [Перемещение влево.] Присвоить Q ← LLINK(Р). Если Q = Λ, то
выполнить Q
⇐
AVAIL и LLINK(Р) ← Q и перейти к шагу А5. В против-
ном случае, если В(Q) ≠ 0, то присвоить Т ← Р и S ← Q. И, наконец, при-
своить Р ← Q и вернуться к шагу А2.
А4. [Перемещение вправо.] Присвоить Q ← RLINK(Р). Если Q = Λ,
то выполнить Q
⇐
AVAIL, RLINK(Р) ← Q и перейти к шагу А5. В про-
тивном случае, если В(Q) ≠ 0, то присвоить Т ← Р и S ← Q. И, наконец,
присвоить Р ← Q и вернуться к шагу А2.
А5. [Вставка.] (Только что новый узел NODE(Q) вставлен в дерево и
теперь следует инициализировать его поля.) Установить KЕY(Q) ← K,
LLINK(Q) ← RLINK(Q) ← Λ и В(Q) ← 0.
А6. [Корректировка факторов сбалансированности.] (В настоящий
момент следует изменить факторы сбалансированности узлов между S и
Q с 0 на ±1.) Если K < KЕY(S), то присвоить а ← –1; в противном случае
присвоить а ← +1. Затем присвоить R ← Р ← LINK(а, S) и при необходи-
мости повторить следующую операцию несколько раз, пока Р не станет
равным Q: если K < KЕY(Р), то присвоить В(Р) ← –1 и Р ← LLINK(Р);
если K > KЕY(Р), то присвоить В(Р) ← +1 и Р ← RLINK(Р). (Если
K = KЕY(Р), то Р = Q и следует перейти к следующему шагу.)
А7. [Балансировка.] На этом шаге возможны несколько вариантов.
1) если В(S) = 0 (дерево стало выше), то присвоить В(S) ← а,
LLINK(НЕАD) ← LLINK(НЕАD) + 1 и прекратить выполнение алгоритма;
2) если В(S) = –а (дерево стало более сбалансированным), то при-
своить В(S) ← 0 и прекратить выполнение алгоритма;
3) если В(S) = а (дерево разбалансировано), то перейти к шагу А8
при В(R) = а или к шагу А9 при В(R) = –а.
(Случай (3) соответствует ситуации (см. рис. 41) при а = +1. При
этом S и R указывают на узлы А к В соответственно, LINK(–а, S) указыва-
ет на α и т.д.)
А8. [Однократный поворот.] Установить Р ← R, LINK(а, S) ←
LINK(–а, R), LINK(–а, R) ←S, В(S) ← В(R) ← 0. Перейти к шагу А10.

Страницы