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

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

встав2( Дер, X, Деревья)

где Деревья — список, состоящий либо из одного, либо из трех аргументов:

 Деревья = [ НовДер], если встав( Дер, X, НовДер)

Деревья = [ НДа, Мб, НДб], 

 если встав( Дер, X, НДа, Мб, НДб)

Теперь отношение доб23 можно переопределить так:

доб23( Д, X, Д1) :-

 встав( Д, X, Деревья),

 соединить( Деревья, Д1).

Отношение соединить формирует одно дерево Д1 из деревьев, находящихся в списке Деревья.

% Отображение 2-3 справочников

отобр(Д) :-

 отобр( Д, 0).

отобр( nil, _ ).

отобр( л(А), H) :-

 tab( H), write( A), nl.

отобр( в2( Д1, М, Д2), H) :-

 H1 is H + 5,

 отобр( Д2, H1),

 tab( H), write( --), nl,

 tab( H), write( M), nl,

 tab( H), write( --), nl,

 отобр( Д1, H1).

отобр( в3( Д1, M2, Д2, М3, Д3), H) :-

 H1 is H + 5

 отобр( Д3, H1),

 tab( H), write( --), nl,

 tab( H), write( M3), nl,

 отобр( Д2, H1),

 tab( H), write( M2), nl,

 tab( H), write( --), nl,

 отобр( Д1, H1).

(a)

      15

    --

    15

    --

      13

  --

  13

  --

      12

    --

    12

      10

    10

    --

       8

--

 8

--

       7

    --

     7

    --

  --

   5

  --

       4

    --

     4

       3

     3

    --

       1

10.2. AVL-дерево: приближенно сбалансированное дерево

AVL-дерево — это дерево, обладающее следующими свойствами:

(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.

(2) Оба поддерева являются AVL-деревьями.

Деревья, удовлетворяющие этому определению, могут быть слегка разбалансированными. Однако можно показать, что даже в худшем случае глубина AVL-дерева примерно пропорциональна log n, где n — число вершин дерева. Таким образом гарантируется логарифмический порядок производительности операций внутри, добавить и удалить.

Операции над AVL-деревом работают по существу так же, как и над двоичным справочником. В них только сделаны добавления, связанные с поддержанием приближенной сбалансированности дерева. Если после вставления или удаления дерево перестает быть приближенно сбалансированным, то специальные механизмы возвращают ему требуемую степень сбалансированности. Для того, чтобы эффективно реализовать этот механизм, нам придется сохранять некоторую дополнительную информацию относительно степени сбалансированности дерева. На самом деле, нам нужно знать только разность между глубинами поддеревьев, которая может принимать значения -1, 0 или +1. Тем не менее для простоты мы предпочтем сохранять сами величины глубин поддеревьев, а не разности между ними.

Мы определим отношение вставления элемента как

доб_avl( Дер, X, НовДер)

где оба дерева Дер и НовДер — это AVL-деревья, причем НовДер получено из Дер вставлением элемента X. AVL-деревья будем представлять как термы вида

д( Лев, А, Прав)/Глуб

где А — корень, Лев и Прав — поддеревья, а Глуб — глубина дерева. Пустое дерево изображается как nil/0. Теперь рассмотрим вставление элемента X в непустой AVL-справочник

Дер = д( L, A, R)/H

Рис. 10.8. Задача вставления элемента в AVL-справочник (a) AVL-дерево перед вставлением X, X > А; (b) AVL-дерево после вставления X в R; (с) составные части, из которых следует построить новое дерево.

Начнем со случая, когда X больше А. X необходимо вставить в R, поэтому имеем следующее отношение:

доб_аv1( R, X, д( R1, В, R2)/Hb)

На рис. 10.8 показаны составные части, из которых строится дерево НовДер:

L, А, R1, В, R2

Какова глубина деревьев L, R, R1 и R2?  L и R могут отличаться по глубине не более, чем на 1. На рис. 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь глубину h+1.

Рис. 10.9. Три правила построения нового AVL-дepевa.