Деревья ПОИСКА Дерево поиска – это либо пустое дерево, либо непустое двоичное дерево, в котором все элементы различны и в котором для каждой вершины справедливо следующее утверждение: во всех вершинах ее (вершины) левого поддерева находятся элементы, строго меньшие элемента из данной вершины, а во всех вершинах ее правого поддерева находятся элементы, строго большие элемента из данной вершины. x вершины x < x> x Условно это можно изобразить так:

Операции для деревьев поиска Построение дерева поиска Пусть в дерево последовательно поступают следующие элементы: а) б) в) г) д)

Поиск элемента Алгоритм поиска элемента с заданным ключом очевиден: 1. Начинаем с корня. 2. Для каждой очередной вершины выполняются следующие действия а) если ключ совпадает с заданным ключом, то искомая вершина найдена; б) если искомый ключ меньше ключа вершины дерева, то переходим к левому поддереву, если больше, то к правому поддереву; 3. Если поддерево пусто, то поиск неудачен, вершины с заданным ключом в дереве нет. Реализацию заданного алгоритма в виде булевской функции необходимо проделать самостоятельно. В качестве побочного эффекта функция должна получать ссылку на вершину с найденным ключом, либо nil в противном случае.

Вставка элемента Алгоритм также очевиден: Применяется такая же последовательность действий как и при поиске, только в случае нахождения вершины с заданным ключом у нее изменяется тело, а если такой вершины не найдено, то к последней вершине слева (если заданный ключ меньше) или справа (если заданный ключ больше) подвешивается новая вершина с заданным ключом. type ТЭД=запись; таблица=дерево; Если в дереве N вершин, тогда оценка поиска в среднем 1.4 log 2 N сравнений