Программирование на языке Пролог для искусственного интеллекта


Усовершенствованные методы представления множеств деревьями


10 1 Двоично троичные справочники
10. 1.    Двоично - троичные справочники Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансирован...
Рисунок 10 1 Полностью разбалансированный
Рисунок 10. 1.  Полностью разбалансированный двоичный справочник.Производительность его та же, что и у списка. с ростом размера множества. Однако плохая сбалансированность дерева ведет к дегр...
Рисунок 10 2 23 справочник Отмеченный путь показывает процесс поиска элемента 10
Рисунок 10. 2.  2-3 справочник. Отмеченный путь показывает процесс поиска элемента 10. При поиске элемента Х в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уро...
Иллюстрирует описанный принцип
Рисунок 10.3 иллюстрирует описанный принцип....
Рисунок 10 3 Вставление нового
Рисунок 10. 3.  Вставление нового элемента в 2-3 справочник. Дереворастет сначала вширь, а затем уже вглубь. Включение нового элемента в 2-3 справочник мы запрограммируем как отношение  ...
Рисунок 10 4 Объекты показанные на рисунке удовлетворяют отношению встав( Дер 6 НДа Мб НДб)
Рисунок 10. 4.  Объекты, показанные на рисунке, удовлетворяют отношению встав( Дер, 6, НДа, Мб, НДб). 2-3 деревья мы будем представлять в программе следующим образом: nil представляет пусто...
Рисунок 10 5 Некоторые из случаев
Рисунок 10. 5.  Некоторые из случаев работы отношения встав. (a)  встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ); (b)  встав( в2( Д1, М, Д2), X,      &nbs...
Рисунок 10 6 Вставление элемента
Рисунок 10. 6.  Вставление элемента в 2-3 справочник. В этойпрограмме предусмотрено, что попытка повторноговставления элемента терпит неудачу. Программа для вставления нового элемента в 2-3 с...
Упражнения
Упражнения 10. 1. Определите отношение         внутри( Эдем, Дер) для поиска элемента Элем в 2-3 справочнике Дер. Посмотреть ответ 10. 2.    Введи...
Рисунок 10 7 (а) Программа для
Рисунок 10. 7.    (а)   Программа для отображения 2-3 справочника.(b)   Справочник (см. Рисунок 10.2), отпечатанный этой программой....
10 2 AVL дерево приближенно сбалансированное дерево
10. 2.    AVL - дерево: приближенно сбалансированное дерево AVL-дерево - это дерево, обладающее следующими свойствами: (1)        Левое и правое п...
Рисунок 10 8 Задача вставления
Рисунок 10. 8.  Задача вставления элемента в AVL-справочник (a)  AVL-дерево перед вставлением Х, Х > А; (b)  AVL-дерево после вставления Х в R; (с)  составные части...
Рисунок 10 9 Три правила построения нового AVLдepевa
Рисунок 10. 9.  Три правила построения нового AVL-дepевa. глубину h +1. В случае, когда Х меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким о...
Упражнение
Упражнение 10. 3. Определите отношение         avl( Дер) для проверки того, является ли ДерAVL-деревом, т.е. верно ли, что любые два его поддерева, подсоединенны...
Рисунок 10 10 Вставление элемента
Рисунок 10. 10.  Вставление элемента в AVL-справочник. В этойпрограмме предусмотрено, что попытка повторного вставленияэлемента терпит неудачу. По поводу процедуры соединитьсм.Рисунок 10.9. д...
Резюме
Резюме 2-3 деревья и AVL-деревья, представленные в настоящей главе, - это примеры сбалансированных деревьев. Сбалансированные или приближенно сбалансированные деревья гарантируют эффективн...
Литература
Литература 2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Па...


Начало


Книжный магазин