Основные процедуры для работы с деревьями

АЛЕКСАНДР ЯМПОЛЬСКИЙ

Основные процедуры для работы с деревьями

Иерархические структуры доминируют в мире. Систем, построенных на основе бескомпромиссного иерархического подхода, немного, так как такой подход выглядит труднореализуемым. Однако его применение повысит вероятность того, что ваша система в конце концов не окажется в тупике.

Статья содержит реализации основных («штатных») процедур для работы с деревьями, включая реализацию алгоритма эвристического поиска. Я попытался продемонстрировать преимущества алгоритма обхода «в ширину» при работе с большими деревьями.

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

Основные процедуры для работы с деревьями

В системах обработки информации иерархические объекты моделируются деревьями. Схема на рис. 1 демонстрирует связи между объектами, формирующими ветвь дерева.

Рисунок 1. Схема ветви дерева

На языке C# эта схема может быть реализована с помощью следующей структуры:

public struct ObjectN   // объект (узел дерева)

   {

   public string J_NAME;       // имя объекта

   public long J_TYPE;  // тип объекта(носитель знаний)

   public long IDF,     // указатель на «отца»

               IDB,     // указатель на «брата»

               ID1C;    // указатель на первого потомка

   }

Дерево моделируется массивом структур ObjectN:

public static ObjectN[] obj = new ObjectN[];

В качестве идентификатора объекта выступает индекс массива. В реальных системах дерево может храниться в файле, записи которого имеют структуру ObjectN. В этом случае номер записи файла будет являться идентификатором объекта.

Схема, показанная на рис. 1, позволяет легко строить и модифицировать деревья произвольного размера и конфигурации. Проблемы с добавлением узлов и вставкой ветвей отсутствуют (имеется в виду отсутствие проблем с перенастройкой системы связей между объектами). Например, для добавления нового узла необходимо знать индекс свободной ячейки массива и идентификатор объекта-«отца»:

FreeCell = getfreecell();

obj[FreeCell].IDF = FatherIdentifier;

obj[FreeCell].IDB = obj[FatherIdentifier].ID1C;

obj[FatherIdentifier].ID1C=FreeCell;

Все запросы к иерархически организованным структурам реализуются в процессе обхода узлов дерева. Основной целью обхода является выделение из сложной структуры отдельных фрагментов – целевых объектов.

Существуют два основных метода обхода древовидных структур: «depth first» обход (обход в глубину, далее DF-обход) и «breadth first» обход (обход в ширину, далее BF-обход).

Маршрут DF-обхода показан на рис. 2.

Рисунок 2. Схема DF-обхода

Общее направление обхода – поперек дерева. В процессе обхода для обработки (например, для формирования списка целевых объектов) хаотично выдаются узлы разного уровня. С первых шагов курсор уходит вглубь и, если дерево большое, нескоро вновь окажется на поверхности. Этот метод обхода по смыслу не соответствует иерархической структуре.

Преимущества метода связаны с процедурой его реализации и заключаются в том, что каждый узел при DF-обходе посещается только один раз. Проблем с исключением из маршрута неперспективных участков (отсечение ветвей на основе знаний об объектах) не существует.

Маршрут BF-обхода показан на рис. 3.

Рисунок 3. Схема BF-обхода

Общее направление обхода – сверху вниз. В процессе обхода для обработки последовательно выдаются узлы одного уровня. Курсор предпочитает держаться ближе к поверхности, т.е. к исходному узлу дерева. Можно надеяться, что в этой достаточно ограниченной зоне сосредоточены либо сами целевые объекты, либо промежуточные целевые объекты (т.е. объекты, при посещении которых может быть выполнена процедура отсечения, см. далее). Этот метод обхода, по-видимому, наиболее соответствует иерархической структуре.

Недостатки метода связаны с процедурой его реализации. Узлы в процессе BF-обхода посещаются более одного раза. Отсечение ветвей выполнить труднее, чем при DF-обходе.

Работа с большими деревьями невозможна без использования процедуры отсечения ветвей. Решение об отсечении принимается на основе знаний об отношениях между встреченными и целевыми объектами. Например, мы знаем, что бесперспективно искать письма в фотоальбоме. В случае дефицита знаний принятие решения об отсечении в данном узле невозможно. В этом случае встает вопрос о том, куда двигаться дальше: уходить в глубину, т.е. совершать DF-обход, или оставаться на поверхности, т.е. совершать BF-обход. На мой взгляд, второй вариант более безопасен по причине, которая уже упоминалась при обсуждении особенностей BF-обхода.

Преимущества BF-обхода могут быть использованы в процедурах поиска объектов. Например, нужно найти файл mpwt.doc. Полный адрес файла: docsdescsourvar1ver1mpwt.doc.

Было бы неплохо иметь возможность вместо полного адреса вводить отдельные узловые точки. В этом случае задание на поиск объекта могло бы выглядеть так: desc;var1;mpwt.doc. Папки desc и var1 являются промежуточными целевыми объектами. Для того чтобы выполнить задание, процедура поиска должна быстро просканировать близлежащие уровни и выполнить необходимые отсечения.

Я думаю, что полезной стратегией поиска могла бы быть такая: как можно быстрее найти хотя бы один целевой объект, получить от него дополнительную информацию, использовать эту информацию для уточнения района дальнейшего поиска. BF-обход хорошо подходит для этой стратегии.

Работа с иерархическими структурами изначально ориентирована на использование знаний. В структуре ObjectN элементом, предназначенным для выполнения функции носителя знаний, является тип объекта.

Тип объекта можно рассматривать как ссылку на абстрактный объект, обладающий типовыми свойствами. Это эквивалентно понятию «класс» в языках программирования.

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

Файл отношений между абстрактными объектами

Идентификатор абстрактного объекта (первый объект пары)	Идентификатор абстрактного объекта (второй объект пары)	Тип отношения	Значение отношения
…	…	…	…
Письмо	Альбом фотографий	Иерархическая совместимость	Не совместимы
…	…	…	…

Знания из этой таблицы могут быть использованы для принятия решений об отсечении неперспективных ветвей. В процессе обхода дерева объектов можно отбрасывать все объекты (ветви), не совместимые с разыскиваемым объектом.

Нерекурсивная процедура descent реализует на языке C# алгоритм BF-обхода дерева объектов. Вместе со встроенной возможностью отсечения ветвей она также реализует алгоритм эвристического поиска:

public static int descent(long SourceObj,int TravDepth)

// SourceObj - указатель исходного узла обхода

// TravDepth - лимит глубины обхода

{

long[] Router = new long[TravDepth]; // маршрутизатор

int Lev, // счетчик уровней дерева

    cur; // вспомогательный указатель уровня

bool EOTree, // признак завершения дерева

     EOLev; // признак завершения уровня

long ObjPnt, // вспомогательный указатель объекта

     FirstCh; // указатель на первого потомка исходного узла

FirstCh=obj[SourceObj].ID1C;

EOTree=false;

Lev=0;

while (!EOTree && Lev<TravDepth)

   {// цикл по уровням

   EOTree=true;

   ObjPnt=FirstCh;

   Lev=Lev+1;

   cur=1;

   EOLev=false;

   while (!EOLev)

      {// DF-обход фрагмента дерева глубиной Lev

      // спуск по левому краю ветви

      while (cur < Lev)

         {

         Router[cur]=ObjPnt;

         cur=cur+1;

         // Здесь может быть вставка – фрагмент кода,реализующий отсечение

         ObjPnt=obj[ObjPnt].ID1C;

         if (ObjPnt<1) break; // узел не имеет потомков

         }

      // выпуск очередной порции узлов уровня Lev

      while (ObjPnt>0)

         {

         Console.WriteLine("object: {0}",obj[ObjPnt].J_NAME);

         // здесь может быть процедура обработки объекта

         EOTree=EOTree && (obj[ObjPnt].ID1C<1);

         ObjPnt=obj[ObjPnt].IDB;

         }

      // подняться по массиву Router до первого ненулевого указателя на объект

      cur=cur-1;

      while (cur>0)

         {

         ObjPnt=obj[Router[cur]].IDB;

         if (ObjPnt>0) break;

         cur=cur-1;

         }

      if (cur == 0) EOLev=true;

      } // обход фрагмента дерева глубиной Lev

   } // цикл по уровням

return(0);

}

Выпуск узлов уровня Lev осуществляется в результате DF-обхода верхней части (от уровня 1 до уровня Lev) дерева, но только узлы уровня Lev выпускаются.

В процессе BF-обхода дерева с количеством уровней L каждый узел, лежащий на уровне Lev, посещается L-Lev+1 раз. В момент посещения каждого узла его полная генеалогия хранится в массиве Router. Как видно, BF-обход является надстройкой над DF-обходом.

Эта избыточность алгоритма иногда может обернуться его преимуществом. Так как процедура постоянно откатывается назад, она имеет возможность в это время подкорректировать параметры отсечения ветвей и соответственно границы района поиска объектов.

Отсечения неперспективных объектов возможны с помощью следующей процедуры:

// фрагмент кода, реализующий отсечение

// compatible – функция, определяющая совместимость объектов

// target_j_type - тип целевого объекта

if (!compatible(obj[ObjPnt].J_TYPE, target_j_type))

   {

   ObjPnt=0;

   break; // как если бы узел не имел потомков

   }

Процедура наследования свойств реализуется с помощью посещения предков объекта и получения от них недостающей информации.

while (ObjPnt != RootPnt)

   {

   // if (информация получена) break;

   ObjPnt=obj[ObjPnt].IDF;

   }

Эту процедуру можно использовать в процессе обработки выделенных объектов, т.е. после того, как процедура обхода выполнила свою задачу, сформировав список целевых объектов.

Заключение

В случае больших деревьев маловероятно то, что полная информация об отношениях между объектами доступна. BF-обход с использованием (там, где это возможно) отсечений – наиболее подходящая процедура для работы с такими деревьями.

Удачи!