Prolog

        Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).

Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (рис. 9.8).

        внутри( X, дер( _, X, _ ).

        внутри( X, дер( Лев, Корень, Прав) ) :-

                больше( Корень, X),               % Корень больше, чем Х

                внутри( X, Лев).                     % Поиск в левом поддереве

        внутри( X, дер( Лев, Корень, Прав) ) :-

                больше( X, Корень),               % Х больше, чем корень

                внутри( X, Прав).                   % Поиск в правом поддереве

Рис. 9. 7.  Поиск элемента Х в двоичном справочнике.

Рис. 9. 8.  (а)     Дерево Д, построенное как результат достижения целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).     (b)    Дерево, полученное при другом порядке целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Здесь уместно сделать несколько замечаний относительно эффективности поиска в справочниках. Вообще говоря, поиск элемента в справочнике эффективнее, чем поиск в списке. Но насколько? Пусть n - число элементов множества. Если множество представлено списком, то ожидаемое время поиска будет пропорционально его длине n. В среднем нам придется просмотреть примерно половину списка. Если множество представлено двоичным деревом, то время поиска будет пропорционально глубине дерева. Глубина дерева - это длина самого длинного пути между корнем и листом дерева. Однако следует помнить, что глубина дерева зависит от его формы

.

Мы говорим, что дерево (приближенно) сбалансировано, если для каждой вершины дерева соответствующие два поддерева содержат примерно равное число элементов. Если дерево хорошо сбалансировано, то его глубина пропорциональна log n. В этом случае мы говорим, что дерево имеет логарифмическую сложность. Сбалансированный справочник лучше списка настолько же, насколько log n меньше n. К сожалению, это верно только для приближенно сбалансированного дерева. Если происходит разбалансировка дерева, то производительность падает. В случае полностью разбалансированных деревьев, дерево фактически превращается в список. Глубина дерева в этом случае равна n, а производительность поиска оказывается столь же низкой, как и в случае списка. В связи с этим мы всегда заинтересованы в том, чтобы справочники были сбалансированы. Методы достижения этой цели мы обсудим в гл. 10.

Упражнения

9. 9.    Определите предикаты

        двдерево( Объект)

        справочник( Объект)

распознающие, является ли Объект двоичным деревом или двоичным справочником соответственно. Используйте обозначения, введенные в данном разделе.

Посмотреть ответ

9. 10.    Определите процедуру

        глубина( ДвДерево, Глубина)

вычисляющую глубину двоичного дерева в предположении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.

Посмотреть ответ

9. 11.    Определите отношение

        линеаризация( Дерево, Список)

соответствующее "выстраиванию" всех вершин дерева в список.

Посмотреть ответ

9. 12.    Определите отношение

        максэлемент( Д, Элемент)

таким образом, чтобы переменная Элемент приняла значение наибольшего из элементов, хранящихся в дереве Д.

Посмотреть ответ

9. 13.    Внесите изменения в процедуру

        внутри( Элемент, ДвСправочник)

добавив в нее третий аргумент Путь таким образом, чтобы можно было бы получить путь между корнем справочника и указанным элементом.

Посмотреть ответ

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

9. 3.    Двоичные справочники: добавление и удаление элемента

Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:

        внутри( X, S)                        % Х  содержится в  S

        добавить( S, X, S1)              % Добавить  Х  к  S,  результат -  S1

        удалить( S, X, S1)                % Удалить  Х  из  S,  результат -  S1

Рис. 9. 9.  Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок:

добавить( Д1, 6, Д2), добавить( Д2, 6, Д3), добавить( Д3, 6, Д4)

        доблист( nil, X, дер( nil, X, nil) ).

        доблист( дер( Лев, Х, Прав), Х, дер( Лев, Х, Прав) ).

        доблист( дер( Лев, Кор, Прав), Х, дер( Лев1, Кор, Прав)) :-

                больше( Кор, X),