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

Содержание 43
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Текущее дерево сбалансировано, но уменьшилась высота, следовательно,
вышестоящие деревья могли потерять баланс. Переходим к отцу и повторяем
анализ.
3,с
A
В
1
4
С
3 2
1
Рис. 43. Двойное вращение
C
В
1 2
A
3 4
Рис. 44. Дерево после вращений
Выполняем двойное вращение (вокруг B затем вокруг A). Текущее дерево
сбалансировано, но уменьшилась высота, следовательно, вышестоящие деревья
могли потерять баланс. Переходим к отцу и повторяем анализ.
?Самостоятельно выполнить двойное вращение. Проанализировать продолжение (конец,
переход). Записать алгоритм удаления с балансировкой?
4.5. В-деревья. Поиск во внешней памяти
Данные находятся на магнитном диске или другом внешнем устройстве с
прямым доступом. Значит, теперь каждый шаг поиска включает сравнительно
медленную операцию обращения к диску. Следовательно, желательна такая