Стр. 41 - Основы алгоритмов и структур данных

Содержание 39
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.4.1.4. Алгоритм включения с балансировкой
Поскольку мы проводим балансировку, то перед включением дерево было
сбалансированным.
Шаг 0. Выполнить алгоритм включения (6). Допустим, включили новый
элемент z в лист p .
На последующих шагах 1,2,3,4…. проходим обратный путь этого листа к
корню дерева, выполняем на каждом шаге следующие действия (достаточно
поместить после рекурсивного вызова функций):
проверяем баланс текущей вершины: если он есть, то переходим к следующему
шагу (поднимаемся выше), если баланса нет, то выполняем балансировку. Если
при этом два последних шага выполнялись оба из правых или из левых
сыновей, то делаем одинарное вращение. Если два последних шага
выполнялись из разных сыновей, то выполняем двойное вращение. В любом
случае текущее поддерево не только становится сбалансированным, но и
восстанавливает ту высоту, которую оно имело до включения. Таким образом,
все вышестоящие деревья автоматически стали сбалансированными и следует
закончить алгоритм.
Поскольку при такой балансировке затрагиваются только вершины на
одной ветви между корнем и листом, то затраты на балансировку будут
пропорциональны высоте дерева, то есть О( 2 log n ).
?Самостоятельно записать алгоритм?
4.4.1.5. Алгоритм исключения с балансировкой
Так как балансировка проводится после каждого включения-исключения,
очевидно, перед исключением дерево было сбалансировано.