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




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


    Глава 10. Усовершенствованные методы представления множеств деревьями
    Глава 10 УСОВЕРШЕНСТВОВАННЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ ДЕРЕВЬЯМИ В данной главе мы рассмотрим усовершенствованные методы представления множеств при помощи деревьев. Основная идея состоит в том...
    Двоично - троичные справочники
    Двоично - троичные справочники Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансированы. Глубина сбалансированн...
    Полностью разбалансированный двоичный справочник.
    Полностью разбалансированный двоичный справочник. Производительность его та же, что и у списка. с ростом размера множества. Однако плохая сбалансированность дерева ведет к деградации производитель...
    Отмеченный путь показывает процесс поиска элемента 10.
    2-3 справочник. Отмеченный путь показывает процесс поиска элемента 10. При поиске элемента Х в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уровня, руководствуясь п...
    Вставление нового элемента в 2-3 справочник. Дерево
    Вставление нового элемента в 2-3 справочник. Дерево растет сначала вширь, а затем уже вглубь. Включение нового элемента в 2-3 справочник мы запрограммируем как отношение доб23( Дер, X, НовДер) где...
    Объекты, показанные на рисунке, удовлетворяют отношению встав( дер, 6, нда, мб, ндб).
    Объекты, показанные на рисунке, удовлетворяют отношению встав( Дер, 6, НДа, Мб, НДб) . 2-3 деревья мы будем представлять в программе следующим образом: nil представляет пустое дерево; л( Х) предст...
    Некоторые из случаев работы отношения...
    Некоторые из случаев работы отношения встав. (a) встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ); (b) встав( в2( Д1, М, Д2), X, в3( НД1а, Мб, НД1б, М, Д2) ); (c) встав( в3( Д1, М2, Д2, М3, Д3), X, в2(...
    Вставление элемента в 2-3 справочник. В этой
    Вставление элемента в 2-3 справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу. Программа для вставления нового элемента в 2-3 справочник показана...
    Упражнения
    Упражнения Определите отношение внутри( Эдем, Дер) для поиска элемента Элем в 2-3 справочнике Дер . Посмотреть ответ Введите в программу рис. 10.6 изменения для устранения лишних возвратов (опреде...
    Avl - дерево: приближенно сбалансированное дерево
    AVL - дерево: приближенно сбалансированное дерево AVL-дерево - это дерево, обладающее следующими свойствами: (1) Левое и правое поддеревья отличаются по глубине не более чем на 1. (2) Оба поддерев...
    Задача вставления элемента в avl-справочник...
    Задача вставления элемента в AVL-справочник (a) AVL-дерево перед вставлением Х, Х А; (b) AVL-дерево после вставления Х в R; (с) составные части, из которых следует построить новое дерево. глубина...
    Три правила построения нового avl-дepевa.
    Три правила построения нового AVL-дepевa. глубину h +1. В случае, когда Х меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случа...
    Вставление элемента в avl-справочник.
    Вставление элемента в AVL-справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу. По поводу процедуры соединить см. рис. 10.9. деревья представляйте...
    Резюме
    Резюме 2-3 деревья и AVL-деревья, представленные в настоящей главе, - это примеры сбалансированных деревьев. Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выпол...
    Литература
    Литература 2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Па...








Начало