Структура и алгоритм обработки данных

В различных задачах применяются  различные виды деревьев, так например:

• при разработке парсеров или трансляторов полезным может оказатьсядерево синтаксического разбора (синтаксическое дерево) [ 5 ];
• при работе со строками удобными могут оказаться суффиксные деревья;
• при разработке оптимальных алгоритмов на графах полезным может оказаться структура данных в виде кучи;
• двоичные деревья поиска используются при реализациях словаря, они являются достаточно простым и распространенным видом деревьев, поэтому их мы рассмотрим более подробно;
• перечислять дальше виды деревьев не имеет смысла, думаю, уже понятно, что разновидностей деревьев много, и у каждой есть своя сфера применения.

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

При обходе дерева поиска, начиная с левого поддерева, значения будут просмотрены в порядке неубывания, начиная с правого – невозрастания, т.е. дерево поиска хранит отсортированные данные.

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

Известно, что операция поиска элемента в неотсортированном массиве  имеетсложность O(n), а в отсортированном – O(log(n)), n – количество элементов в дереве/списке. Логарифмическая сложность поиска в отсортированном массиве обеспечивается двоичным поиском, т.е. вместо того, чтобы обходить все элементы массива последовательно, массив каждый раз делится пополам, поиск продолжается в половине массива (очень похоже на поиск по оглавлению книги или поиск слова в обычном, бумажном словаре). Поиск элементов в отсортированном массиве выполняется очень быстро, однако, вставка элемента в отсортированный массив потребует сдвига элементов (операция со сложностьюO(n)).

Операция вставки элемента в отсортированный динамический список не требует сдвига элементов, однако, перед тем как вставить элемент, необходимо найти подходящую позицию. Для связных списков  нельзя использовать двоичный поиск (т.к. элементы могут располагаться в  памяти не последовательно друг за другом), а значит, что операция вставки и поиска элемента отсортированном динамическом списке имеет сложность O(n).

Таким образом, поиск в  отсортированном массиве имеет  логарифмическую сложность, однако, операция вставки имеет сложность O(n), динамические списки не решают проблему.

Деревья поиска позволяют  выполнять операцию вставки элемента за времяO(log(n)), а операцию поиска – за O(h), где h – высота дерева. В примерах следующего раздела будет приведен пример правила построения произвольного дерева поиска (не сбалансированного), высота которого в худшем случае совпадает с количеством элементов в дереве (так будет если в дерево добавлять уже отсортированные данные), однако, обычно и такое дерево будет иметь высоту весьма близкую к log(n). Высота сбалансированного дерева поиска – log(n), поиск всбалансированном дереве поиска (это такое дерево, высота правого и левого поддерева, которого различаются не более чем на единицу) выполнится за времяO(log(n)). Отмечу, что существуют самобалансирующиеся деревья поиска, например, красно-черные деревья, АВЛ-деревья или расширяющиеся деревья, но их рассмотрение выходит за рамки статьи [2, 5, 6].

Конечно, дерево поиска необходимо поддерживать в отсортированном  состоянии, операции добавления или  удаления элементов выполняются  дольше, чем в неотсортированных  массивах или списках.

Добавление элемента (E) в дерево поиска выполняется рекурсивно:

1. если дерево является пустым – то значение E помещается в корневую вершину;
2. если значение E больше значения корневой вершины – осуществляется вставка E в правое поддерево (рекурсивно), иначе – в левое.

Удаление элемента (E) из дерева поиска, несколько запутаннее, поэтому  алгоритм тут не приведен, зато приведены  поясняющие иллюстрации (рисунок 2).

рис. 2 удаление узла из дерева поиска

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

Такие алгоритмы добавления элемента и удаления элемента дерева имеют трудоемкость O(log(n)), однако не гарантируют сбалансированности полученного дерева. Аналогичные операции для, например, красно-черных деревьев сложнее, но их трудоемкость, по-прежнему, O(log(n)).

Нередко пишут, что деревья  сложнее в использовании, чем  массивы и списки, на самом деле, это не всегда так  и зависит от используемых библиотек. Например, контейнер словаря (map) стандартной библиотеки С++ чаще всего реализуется через красно-черные деревья, но нельзя сказать, что он менее удобен в использовании чем список (list) из той же библиотеки – каждый из них имеет свою область применения и удобен тогда, когда используется по назначению.

 

 

 

 

 

Пример программы  на языке C++

#include "conio.h"

#include "stdio.h"

#include "string.h"

#include "stdafx.h"

char Tree  ;

struct Node {

        char data;

        Node *left, *right;

        };

typedef Node *PNode;

int Priority ( char c )

{

switch ( c ) {

   case '+': case '-': return 1;

   case '*': case '/': return 2;

   }

return 100; // это не арифметическая операция

}

 

PNode MakeTree (char Expr[], int first, int last)

{

int MinPrt, i, k, prt;

PNode Tree = new Node;  // создать в памяти новую вершину

if ( first == last ) {  // конечная вершина: число или

   Tree->data = Expr[first];  //             переменная

   Tree->left = NULL;

   Tree->right = NULL;

   return Tree;

   }

MinPrt = 100;

for ( i = first; i <= last; i ++ ) {

   prt = Priority ( Expr[i] );

   if ( prt <= MinPrt ) { // ищем последнюю операцию 

      MinPrt = prt;       //      с наименьшим приоритетом

      k = i;

      }

}

Tree->data = Expr[k];  // внутренняя вершина (операция)

Tree->left  = MakeTree (Expr,first,k-1); // рекурсивно строим

Tree->right = MakeTree (Expr,k+1,last);  // поддеревья

return Tree;

}

 

int CalcTree (PNode Tree)

{

   int num1, num2;

   if ( ! Tree->left )           // если нет потомков,

      return Tree->data - '0';   //      вернули число

   num1 = CalcTree(Tree->left);  // вычисляем поддеревья

   num2 = CalcTree(Tree->right);

   switch ( Tree->data ) {       // выполняем операцию 

      case '+': return  num1+num2;

      case '-': return  num1-num2;

      case '*': return  num1*num2;

      case '/': return  num1/num2;

      }

   return 32767;  // неизвестная операция, ошибка!

}

 

void main()

{

  char s[80];

  PNode Tree;

  printf("vvedite virazhenie > ");

  gets(s);

  Tree = MakeTree(s, 0, strlen(s)-1);

  printf ( "= %d \n", CalcTree ( Tree ) );

  getch();

}

 

 

Сеанс работы.

 

 

 

 

 

 

 

 

 

 

 

 

 

Обход графа в  ширину. Применение.

Основные понятия

Граф - это совокупность узлов (вершин) и соединяющих их ребер (дуг).

     Цепь – это  последовательность ребер, соединяющих две (возможно не соседние)вершины u и v. В направленном графе такая последовательность ребер называется «путь».

      Граф называется связным, если существует цепь между любой парой вершин. Если граф несвязный, то его можно разбить на k связных компонент – он называется k-связным.

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

      Цикл – это цепь из какой-нибудь вершины v в нее саму.

      Полный граф – это граф, в котором проведены все возможные ребра (для графа, имеющего n вершин таких ребер будет n(n-1)/2).

      Неориентированный (обычный) граф – граф, в котором важен только сам факт связи двух вершин

      Ориентированный (орграф) граф – граф , для которого важным является еще и направление связи вершин

      Взвешенные граф - граф, в котором важной информацией является еще и степень (величина, вес) связи вершин

 

 

Описание  графов

        Для описания графов часто используют два типа матриц – матрицу смежности (для не-взвешенных графов) и весовую матрицу (для взвешенных).

       Матрица смежности графа с N вершинами – это матрица размером N на N, где каждый эле-мент с индексами (i,j) является логическим значением и показывает, есть ли дуга из вер-шины i в вершину j.

Часто вместо логических значений (истина/ложь) используют целые числа (1/0). Для не-ориентированных графов матрица смежности всегда симметрична относительно главной диаго-нали (рисунок а). Для ориентированных графов (рисунок б) это не всегда так, потому что может

существовать путь из вершины i в вершину j и не существовать обратного пути.

 

Процедура поиска в ширину

          Обход в ширину применяется  для нахождения кратчайшего пути  между вершинами графа.

           Работа всякого алгоритма обхода состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра - зависит от конкретной задачи, для решения которой производится обход. В любом случае, однако, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую. 
 
          Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины  . Иначе говоря, сначала посещается сама вершина  , затем все вершины, смежные с  , то есть находящиеся от нее на расстоянии  , затем вершины, находящиеся от  на расстоянии  , и т.д. 
 
           Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной  . Вначале все вершины помечаются как новые. Первой посещается вершина  , она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины  . Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину  с новой вершиной  , то вершина  посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым. 
 
            Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь - когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале. Схематически процесс изменения статуса вершин изображен на рис. 4.1. Черным кружком обозначена активная вершина. 
 
 
Рис. 4.1.  

 

 

 

 

 

 

 

 

 

 

 

 

Пример программы на языке C++

#include"stdafx.h"

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

#define MAXV 1000  /* максимальное количество вершин*/

bool processed[MAXV+1]; /* Обработанные вершины */

bool discovered[MAXV+1]; /* Открытыевершины*/

int parent[MAXV+1]; /* Родитель вершины*/

bool directed=false;

const int MAXSIZE = 100;

struct queue {

int data[MAXSIZE];

int size, head, tail;

};

typedef struct edgenode {

int y;   /* информация о смежности*/

int weight;  /* вес ребра, если есть*/

struct edgenode *next;    /* следующее ребро в списке*/

} ;

typedef struct graph{

edgenode *edges[MAXV+1];     /* информацияосмежности*/

int degree[MAXV+1];  /* степень каждой вершины*/

int nvertices;   /* количество вершин в графе*/

int nedges;   /* количество ребер в графе*/

bool directed;   /* графориентированный? */

} ;

void initialize_search(graph *g)

{ int i; /* counter */

for (i=1; i<=g->nvertices; i++) {

processed[i] = discovered[i] = false;

parent[i] = -1;

}

}

void process_vertex_early(int v)

{

printf("processed vertex %d\n",v);

}

void process_edge(int x, int y)

{

printf("processed edge (%d,%d)\n",x,y);

}

void init_queue(queue *q) 

{q->head=0;

q->size=0;

q->tail=0;

}

 

bool empty_queue(queue *q) 

{ return q->size ==0; }

 

void enqueue(queue *q, int start)

{if ( q->size == MAXSIZE ) {

printf ("ochered perepolnena\n");

return;

}

q->tail++;

if ( q->tail >= MAXSIZE ) // замыканиевкольцо

q->tail = 0;

q->data[q->tail] = start;

q->size ++;

}

int dequeue(queue *q)

{int temp;

if (q->size == 0 ) {

printf ("ochered pusta\n");

return 32767; // сигналобошибке

}

 

q->head ++;

temp = q->data[q->head];

if (q->head >= MAXSIZE ) q->head = 0;

q->size --;

return temp;

}

void bfs(graph *g, int start)

{

queue q; /* очередь вершин для обработки*/

int v;       /* текущая вершина*/

int y;      /* следующая вершина*/

edgenode *p;      /* временный указатель*/

init_queue(&q);

enqueue(&q,start);

discovered[start] = true;

while (empty_queue(&q) == false) {

v = dequeue(&q);  //текущаявершина

process_vertex_early(v); //выводвершинынаэкран

processed[v] = true; //обработанная

p = g->edges[v];  //указатель на связн. вершину

while (p != NULL) {

y = p->y;  //след. вершина

if ((processed[y] ==false) || g->directed)

process_edge(v,y);//вывод ребра на экран

if (discovered[y] == false) {

enqueue(&q,y);

discovered[y] = true;

parent[y] = v; //родительдляследвершины

}

p = p->next;

}

}

}

void find_path(int start, int end, int parents[])

{

if ((start == end) || (end == -1))

printf("\n%d",start);

else {

find_path(start,parents[end],parents);

printf(" %d",end);

}

}

void connected_components(graph *g)

{

int c; /* component number */

int i; /* counter */

initialize_search(g);

c=0;

for (i=1; i<=g->nvertices; i++)

{if (discovered[i] == false) {

c = c+1;

printf("Component %d:",c);

bfs(g,i);

printf("\n");

}

}

}

void initialize_graph(graph *g, bool directed)

{

int i; /* counter */

g -> nvertices = 0;

g -> nedges = 0;

g -> directed = directed;

for (i=1; i<=MAXV; i++) g->degree[i] = 0;

for (i=1; i<=MAXV; i++) g->edges[i] = NULL;

}

void insert_edge(graph *g,  int  x,  int  y,  bool  directed)