| 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;
| end;
end;
Восстановление сбалансированности требует движения от
листьев к корню, поэтому будем хранить в стеке путь от корня к
рассматриваемой в данный момент вершине. Элементами стека будут
пары (вершина, направление движения из нее), т.е. значения типа
record
| vert: 1..n; {вершина}
| direction : (l, r); {l - левое, r- правое}
end;
Программа добавления элемента t теперь выглядит так:
if root = null then begin
| get_free (root);
| left [root] := null; right [root] := null; diff[root] := 0;
| val [root] := t;
end else begin
| x := root; ..сделать стек пустым
| {инвариант: осталось добавить t к непустому поддереву с
| корнем в x; стек содержит путь к x}
| while ((t < val [x]) and (left [x] <> null)) or
| | ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | ..добавить в стек пару
| | | x := left [x];
| | end else begin {t > val [x]}
| | | ..добавить в стек пару
| | | x := right [x];
| | end;
| end;
| if t <> val [x] then begin {t нет в дереве}
| | get_free (i); val [i] := t;
| | left [i] := null; right [i] := null; diff [i] := 0;
| | if t < val [x] then begin
| | | ..добавить в стек пару
| | | left [x] := i;
| | end else begin {t > val [x]}
| | | ..добавить в стек пару
| | | right [x] := i;
| | end;
| | d := 1;
| | {инвариант: стек содержит путь к изменившемуся поддереву,
| | высота которого увеличилась по сравнению с высотой в
| | исходном дереве на d (=0 или 1); это поддерево сбалан-
| | сировано; значения diff для его вершин правильны; в ос-
| | тальном дереве все осталось как было - в частности,
| | значения diff}
| | while (d <> 0) and ..стек непуст do begin {d = 1}
| | | ..взять из стека пару в
| | | if direct = l then begin
| | | | if diff [v] = 1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] - 1;
| | | end else begin {direct = r}
| | | | if diff [v] = -1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] + 1;
| | | end;
| | | {c = изменение высоты поддерева с корнем в v по сравне-
| | | нию с исходным деревом; массив diff содержит правиль-
| | | ные значения для этого поддерева; возможно нарушение
| | | сбалансированности в v}
| | | balance (v, d1); d := c + d1;
| | end;
| end;
end;
Легко проверить, что значение d может быть равно только 0 или 1
(но не -1): если c = 0, то diff [v] = 0 и балансировка не произ-
водится.
Программа удаления строится аналогично. Ее основной фраг-
мент таков:
{инвариант: стек содержит путь к изменившемуся поддереву,
высота которого изменилась по сравнению с высотой в
исходном дереве на d (=0 или -1); это поддерево
сбалансировано; значения diff для его вершин правильны;
в остальном дереве все осталось как было -
в частности, значения diff}
while (d <> 0) and ..стек непуст do begin
| {d = -1}
| ..взять из стека пару в
| if direct = l then begin
| | if diff [v] = -1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] + 1;
| end else begin {direct = r}
| | if diff [v] = 1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] - 1;
| end;
| {c = изменение высоты поддерева с корнем в v по срав-
| нению с исходным деревом; массив diff содержит
| правильные значения для этого поддерева;
| возможно нарушение сбалансированности в v}
| balance (v, d1);
| d := c + d1;
end;
Легко проверить, что значение d может быть равно только 0 или -1
(но не -2): если c = -1, то diff [v] = 0 и балансировка не про-
изводится.
Отметим также, что наличие стека делает излишними перемен-
ные father и direction (их роль теперь играет вершина стека).
12.2.6. Доказать, что при добавлении элемента
(а) второй из трех случаев балансировки (см. рисунок выше)
невозможен;
(б) полная балансировка требует не более одного вращения
(после чего все дерево становится сбалансированным),
в то время как при удалении элемента может понадобиться
много вращений.
Замечание. Мы старались записать программы добавления и
удаления так, чтобы они были как можно более похожими друг на
друга. Используя специфику каждой из них, можно многое упрос-
тить.
Существуют и другие способы представления множеств, гаран-
тирующие число действий порядка log n на каждую операцию. Опишем
один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого
множества. Этот элемент служил границей между левым и правым
поддеревом. Будем теперь хранить в вершине k >= 1 элементов мно-
жества (число k может меняться от вершины к вершине, а также при
добавлении и удалении новых элементов, см. далее). Эти k элемен-
тов служат разделителями для k+1 поддерева. Пусть фиксировано
некоторое число n >= 1. Будем рассматривать деревья, обладающие
такими свойствами:
(1) Каждая вершина содержит от n до 2n элементов (за исклю-
чением корня, который может содержать любое число элементов от 0
до 2n).
(2) Вершина с k элементами либо имеет k+1 сына, либо не
имеет сыновей вообще (такие вершины называются листьями).
(3) Все листья находятся на одной и той же высоте.
Добавление элемента происходит так. Если лист, в который он
попадает, неполон (т.е. содержит менее 2n элементов), то нет
проблем. Если он полон, то 2n+1 элемент (все элементы листа и
новый элемент) разбиваем на два листа по n элементов и разделя-
ющий их серединный элемент. Этот серединный элемент надо доба-
вить в вершину предыдущего уровня. Это возможно, если в ней ме-
нее 2n элементов. Если и она полна, то ее разбивают на две, вы-
деляют серединный элемент и т.д. Если в конце концов мы захотим
добавить элемент в корень, а он окажется полным, то корень рас-
щепляется на две вершины, а высота дерева увеличивается на 1.
Удаление элемента. Удаление элемента, находящемся не в лис-
те, сводится к удалению непосредственно следующего за ним, кото-
рый находится в листе. Поэтому достаточно научиться удалять эле-
мент из листа. Если лист при этом становится неполным, то его
можно пополнить за счет соседнего листа - если только и он не
имеет минимально возможный размер n. Если же оба листа имеют
размер n, то на них вместе 2n элементов, вместе с разделителем -
2n+1. После удаления одного элемента остается 2n элементов - как
раз на один лист. Если при этом вершина предыдущего уровня ста-
новится меньше нормы, процесс повторяется и т.д.
12.2.7. Реализовать описанную схему хранения множеств, убе-
дившись, что она также позволяет обойтись C*log(n) действий для
операций включения, исключения и проверки принадлежности.
12.2.8. Можно определять сбалансированность дерева иначе:
требовать, чтобы для каждой вершины ее левое и правое поддеревья
имели не слишком сильно отличающиеся количества вершин. (Преиму-
щество такого определения состоит в том, что при вращениях изме-
няется сбалансированность только в одной вершине.) Реализовать
на основе этой идеи способ хранения множеств, гарантирующий
оценку в C*log(n) действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие и малые
вращения. Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)
Н Е П О К У П А Й Т Е Э Т У К Н И Г У !
(Предупреждение автора)
В этой книге ничего не говорится об особенностях BIOSа,
DOSа, OSа, GEMа и Windows, представляющих основную сложность при
настоящем программировании.
В ней нет ни слова об объектно-ориентированном программиро-
вании, открывшем новую эпоху в построении дружественных и эффек-
тивных программных систем.
Из нее Вы не узнаете о графических возможностях компьютера,
без которых немыслимо современное программирование, о богатстве
и разнообразии мира видеоадаптеров.
Не рассказано в ней и о написании резидентных программ,
тонкости взаимодействия которых должен знать каждый.
Искусственный интеллект, открывший новые рынки сбыта для
программного обеспечения, обойден презрительным молчанием.
Экспертные системы, которые в скором будущем займут место
на рабочем столе каждого, даже не упоминаются.
Логическое программирование, постепенно вытесняющее уста-
ревший операторный стиль программирования, не затронуто.
Драматический поворот от баз данных к базам знаний, вызвав-
ший в жизни новую профессию -- инженер знаний -- остался незаме-
ченным автором.
Проблемы отладки и сопровождения программ, занимающие, по
общему мнению профессионалов, 90% в программировании, игнориру-
ются.
В книге используются лишь самые элементарные возможности
паскаля. Обширные возможности, предоставляемые современными ин-
тегрированными программными средами, остаются невостребованными.
(Не говоря уже о том, что паскаль уже вообще устарел, вытеснен-
ный языком Си.)
Игрушечные головоломки, которым посвящена книга, никому не
нужны. Если же перед Вами встанет действительно важная задача,
неужели Вы не справитесь с ней сами, без непрошеных учителей и
советчиков?
Короче говоря, покупать эту книгу глупо - особенно теперь,
когда выходит столько переводных руководств, написанных в циви-
лизованных странах настоящими профессионалами.
Глава 1. Переменные, выражения, присваивания.
1.1. Задачи без массивов
1.1.1. Даны две целые переменные a, b. Составить фрагмент
программы, после исполнения которого значения переменных поменя-
лись бы местами (новое значение a равно старому значению b и на-
оборот).
Решение. Введем дополнительную целую переменную t.
t := a;
a := b;
b := t;
Попытка обойтись без дополнительной переменной, написав
a := b;
b := a;
не приводит к цели (безвозвратно утрачивается начальное значение
переменной a).
1.1.2. Решить предыдущую задачу, не используя дополни-
тельных переменных (и предполагая, что значениями целых перемен-
ных могут быть произвольные целые числа).
Решение. (Начальные значения a и b обозначим a0, b0.)
a := a + b; {a = a0 + b0, b = b0}
b := a - b; {a = a0 + b0, b = a0}
a := a - b; {a = b0, b = a0}
1.1.3. Дано целое число а и натуральное (целое неотрица-
тельное) число n. Вычислить а в степени n. Другими словами, не-
обходимо составить программу, при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой пере-
менной (например, b) становится равным а в степени n. (При этом
разрешается использовать и другие переменные.)
Решение. Введем целую переменную k, которая меняется от 0
до n, причем поддерживается такое свойство: b = (a в степени
k).
k := 0; b := 1;
{b = a в степени k}
while k <> n do begin
| k := k + 1;
| b := b * a;
