Вопросы и упражнения. 1. Для алгоритма поиска со вставкой по дереву можно применить ту же идею барьера, которая рассматривалась для линейного поиска в массиве (п

1. Для алгоритма поиска со вставкой по дереву можно применить ту же идею барьера, которая рассматривалась для линейного поиска в массиве (п. 2.1). Как для этого нужно изменить структуру данных дерева и текст процедуры поиска?

2. Докажите, что длины всех ветвей ИС-дерева различаются не более, чем на 1.

3. Можно ли при удалении вершины дерева поиска, имеющей двух сыновей, вместо ближайшей вершины слева использовать ближайшую справа?

4. Докажите, что число листьев для наихудших АВЛ-деревьев при увеличении высоты дерева образует последовательность Фибоначчи.

5. Напишите фрагмент программы, выполняющий поворот в АВЛ-дереве для случая 2.

6. Сформулируйте алгоритм вставки в B+-дерево, исходя из примера B+-дерева на рис. 4.10.

7. Известна модификация страничных деревьев поиска, называемая B++-деревьями. Для этих деревьев каждая страница, кроме корня, заполнена не менее, чем на 3/4. Объясните, как должна работать вставка в B++-дерево и сколько ключей может содержать корень такого дерева.

8. Чем отличается операция изменения значения ключевого поля записи базы данных от изменения неключевого поля?

Специальные методы сортировки и поиска

В предыдущих разделах задачи сортировки и поиска рассматривалась в предположении, что в качестве ключа могут использоваться данные любого типа с единственным ограничением: на множестве значений ключа определено некоторое отношение линейного порядка, т.е., проще говоря, для любой пары значений справедливо одно из отношений: <, = или >. Больше никаких предположений о множестве ключей не делалось.

Такой подход хорош своей универсальностью. Рассмотренные алгоритмы работают одинаково эффективно для числовых, строковых и других ключей. В некоторых библиотеках имеются даже стандартные функции сортировки (чаще всего QuickSort) и поиска (бинарного), которые в качестве одного из параметров принимают произвольную функцию сравнения ключей, возвращающую значения –1, 0, +1, что означает результат сравнения соответственно <, =, >.

Платой за универсальность являются ограничения скорости алгоритмов. Мы показали, что для сортировки наилучшая оценка времени есть T_max(n) = O(n·log(n)), для поиска – T_max(n) = O(log(n)), и лучших оценок нельзя получить в принципе.

В ряде практически важных задач можно добиться лучших результатов. Но для этого следует больше знать о структуре используемых ключей. Ниже описаны два важных случая, когда удается построить алгоритмы не столь универсальные, но зато более эффективные.