Алгоритмы поиска на основе деревьев

Цель лекции: изучить алгоритмы поиска на основе деревьев, научиться решать задачи поиска через построение упорядоченного, случайного, оптимального или сбалансированного в высоту деревьев на языке C++.

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

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

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

Двоичные (бинарные) деревья

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

Двоичные упорядоченные деревья

Двоичное дерево упорядоченно, если для любой его вершины x справедливы такие свойства (рис 40.1):

Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным. В дальнейшем будет идти речь только о двоичных упорядоченных деревьях. Основными операциями, производимыми с упорядоченным деревом, являются:

Пример 1. Программная реализация основных операций бинарного дерева поиска.

#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;

typedef int T; // тип элемента
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
typedef struct Node_ {
  T data;  // значение узла
    struct Node_ *left;// левый потомок
    struct Node_ *right;// правый потомок
    struct Node_ *parent;// родитель
} Node;
Node *root = NULL; //корень бинарного дерева поиска

Node* insertNode(T data);
void deleteNode(Node *z);
Node* findNode(T data);
void printTree(Node *node, int l = 0);

int _tmain(int argc, _TCHAR* argv[]){
  int i, *a, maxnum;
  cout << "Введите количество элементов maxnum : ";
  cin >> maxnum;
  cout << endl;
    a = new int[maxnum];
    srand(time(NULL)*1000);
  // генерация массива
  for (i = 0; i < maxnum; i++)
    a[i] = rand();
    cout << "Вывод сгенерированной последовательности" << endl;
  for (i = 0; i < maxnum; i++)
    cout << a[i] << " ";
  cout << endl;
  cout << endl;
  // добавление элементов в бинарное дерево поиска
  for (i = 0; i < maxnum; i++) {
    insertNode(a[i]);
  }
  cout << "Вывод бинарного дерева поиска" << endl;
  printTree(root);
  cout << endl;
  // поиск элементов по бинарному дереву поиска
  for (i = maxnum-1; i >= 0; i--) {
    findNode(a[i]);
  }
  // очистка бинарного дерева поиска
  for (i = 0; i < maxnum; i++) {
    deleteNode(findNode(a[i]));
  }
  system("pause");
  return 0;
}

//функция выделения памяти для нового узла и вставка в дерево
Node* insertNode(T data) {
  Node *x, *current, *parent;
  current = root;
  parent = 0;
  while (current) {
    if ( data == current->data ) return (current);
      parent = current;
      current = data < current->data ? 
      current->left : current->right;
  }
  x = new Node;
  x->data = data;
  x->parent = parent;
  x->left = NULL;
  x->right = NULL;
  if(parent)
    if( x->data < parent->data )
      parent->left = x;
    else
    parent->right = x;
  else
    root = x;
  return(x);
}

//функция удаления узла из дерева
void deleteNode(Node *z) {
  Node *x, *y;
  if (!z || z == NULL) return;
  if (z->left == NULL || z->right == NULL)
    y = z;
  else {
    y = z->right;
    while (y->left != NULL) y = y->left;
  }
  if (y->left != NULL)
    x = y->left;
  else
    x = y->right;
  if (x) x->parent = y->parent;
  if (y->parent)
    if (y == y->parent->left)
      y->parent->left = x;
    else
      y->parent->right = x;
  else
    root = x;
  if (y != z) {
    y->left = z->left;
    if (y->left) y->left->parent = y;
      y->right = z->right;
    if (y->right) y->right->parent = y;
      y->parent = z->parent;
    if (z->parent)
      if (z == z->parent->left)
        z->parent->left = y;
      else
        z->parent->right = y;
    else
      root = y;
      free (z);
  } 
  else {
    free (y);
  }
}

//функция поиска узла, содержащего data
Node* findNode(T data) {
  Node *current = root;
  while(current != NULL)
    if(compEQ(data, current->data))
      return (current);
    else
      current = compLT(data, current->data) ? 
                current->left : current->right;
  return(0);
}

//функция вывода бинарного дерева поиска
void printTree(Node *node, int l){
  int i;
  if (node != NULL) {
    printTree(node->right, l+1);
    for (i=0; i < l; i++) cout << "    ";
    printf ("%4ld", node->data);
    printTree(node->left, l+1);
  }
  else cout << endl;
}

Алгоритм удаления элемента более трудоемкий, так как надо соблюдать упорядоченность дерева. При удалении может случиться, что удаляемый элемент находится не в листе, то есть вершина имеет ссылки на реально существующие поддеревья. Эти поддеревья терять нельзя, а присоединить два поддерева на одно освободившееся после удаления место невозможно. Поэтому необходимо поместить на освободившееся место либо самый правый элемент из левого поддерева, либо самый левый из правого поддерева. Упорядоченность дерева при этом не нарушится. Удобно придерживаться одной стратегии, например, заменять самый левый элемент из правого поддерева. Нельзя забывать, что при замене вершина, на которую производится замена, может иметь правое поддерево. Это поддерево необходимо поставить вместо перемещаемой вершины.

Временная сложность этих алгоритмов (она одинакова для этих алгоритмов, так как в их основе лежит поиск) оценим для наилучшего и наихудшего случая. В лучшем случае, то есть случае полного двоичного дерева, получаем сложность Omin(log n). В худшем случае дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем придется просмотреть половину списка. Это даст сложность Omax(n).

Случайные деревья

Случайные деревья поиска представляют собой упорядоченные бинарные деревья поиска, при создании которых элементы (их ключи) вставляются в случайном порядке.

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

При поступлении элементов в случайном порядке получаем дерево с минимальной высотой h (рис. 40.2А), при этом минимизируется время поиска элемента в дереве, которое пропорционально O(log n). При поступлении элементов в упорядоченном виде (рис. 40.2В) или в порядке с единичными сериями монотонности (рис. 40.2С) происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(n).

Оптимальные деревья

В двоичном дереве поиск одних элементов может происходить чаще, чем других, то есть существуют вероятности pk поиска k -го элемента и для различных элементов эти вероятности неодинаковы. Можно предположить, что поиск в дереве в среднем будет более быстрым, если те элементы, которые ищут чаще, будут находиться ближе к корню дерева.

Пусть даны 2n+1 вероятностей p1,p2,...,pn, q0,q1,...,qn, где pi – вероятность того, что аргументом поиска является Ki элемент; qi – вероятность того, что аргумент поиска лежит между вершинами Ki и Ki+1 ; q0 – вероятность того, что аргумент поиска меньше, чем значение элемента K1 ; qn – вероятность того, что аргумент поиска больше, чем Kn. Тогда цена дерева поиска C будет определяться следующим образом:

где $$\text{levelroot}_j$$ – уровень узла j, а $$\text{levellist}_k$$ – уровень листа K.

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

Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска, которое будет далеко от оптимального. Еще один подход состоит в выборе корня k таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением pk.

Существуют алгоритмы, которые позволяют построить оптимальное дерево поиска. К ним относится, например, алгоритм Гарсия-Воча. Однако такие алгоритмы имеют временную сложность порядка O(n2). Таким образом, создание оптимальных деревьев поиска требует больших накладных затрат, что не всегда оправдывает выигрыш при быстром поиске.

Сбалансированные по высоте деревья

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

Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении или удалении элементов может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. В 1962 году два советских математика: Г.М. Адельсон-Вельский и Е.М. Ландис – ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления и/или удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным. Дерево считается сбалансированным по АВЛ (сокращения от фамилий Г.М. Адельсон-Вельский и Е.М. Ландис), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное по АВЛ дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано по АВЛ.

При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.

Рассмотрим такие преобразования. Пусть вершина ). Аналогично определяется симметричное ему малое левое вращение.

Пусть ). Аналогично определяется симметричное ему большое левое вращение.

Схематично алгоритм добавления нового элемента в сбалансированное по АВЛ дерево будет состоять из следующих трех основных шагов.

Шаг 1. Поиск по дереву.

Шаг 2. Вставка элемента в место, где закончился поиск, если элемент отсутствует.

Шаг 3. Восстановление сбалансированности.

Первый шаг необходим для того, чтобы убедиться в отсутствии элемента в дереве, а также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным. Третий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин, и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.

#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;
typedef int ElementType;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode {
            ElementType Element;
            AvlTree Left;
            AvlTree Right;
            int Height;
        };

AvlTree MakeEmpty( AvlTree T );
Position Find( ElementType X, AvlTree T );
Position FindMin( AvlTree T );
Position FindMax( AvlTree T );
AvlTree Insert( ElementType X, AvlTree T );
ElementType Retrieve( Position P );
void printTree(AvlTree T, int l = 0);

int _tmain(int argc, _TCHAR* argv[]){
  int i, *a, maxnum;
  AvlTree T;
    Position P;
    int j = 0;
  cout << "Введите количество элементов maxnum : ";
  cin >> maxnum;
  cout << endl;
    a = new int[maxnum];
  srand(time(NULL)*1000);
  // генерация массива
  for (i = 0; i < maxnum; i++)
    a[i] = rand()%100;
  cout << "Вывод сгенерированной последовательности" << endl;
  for (i = 0; i < maxnum; i++)
    cout << a[i] << " ";
  cout << endl;
  cout << endl;
  // добавление элементов в АВЛ-дерево
    T = MakeEmpty( NULL );
  for( i = 0; i < maxnum; i++ )
        T = Insert( a[i], T );
  cout << "Вывод АВЛ-дерева" << endl;
  printTree(T);
  cout << endl;
  cout << "Min = " << Retrieve( FindMin( T ) ) << ", Max = " 
       << Retrieve( FindMax( T ) ) << endl;
  // удаление АВЛ-дерева
  T = MakeEmpty(T);
  delete [] a;
  system("pause");
  return 0;
}

//функция удаления вершины и его поддеревьев
AvlTree MakeEmpty( AvlTree T ) {
  if( T != NULL ){
    MakeEmpty( T->Left );
    MakeEmpty( T->Right );
    free( T );
  }
  return NULL;
}

// поиск вершины со значением X
Position Find( ElementType X, AvlTree T ) {
  if( T == NULL )
    return NULL;
    if( X < T->Element )
      return Find( X, T->Left );
    else
      if( X > T->Element )
        return Find( X, T->Right );
      else
        return T;
}

//функция поиска вершины с минимальным значением
Position FindMin( AvlTree T ) {
  if( T == NULL )
    return NULL;
  else
    if( T->Left == NULL )
      return T;
    else
      return FindMin( T->Left );
}

//функция поиска вершины с максимальным значением
Position FindMax( AvlTree T ) {
  if( T != NULL )
    while( T->Right != NULL )
      T = T->Right;
  return T;
}

//функция возвращает вес вершины
static int Height( Position P ) {
  if( P == NULL )
    return -1;
  else
    return P->Height;
}

//функция возвращает максимальное из двух чисел
static int Max( int Lhs, int Rhs ) {
  return Lhs > Rhs ? Lhs : Rhs;
}

/*функция выполняет поворот между вершинами K2 и его левым потомком*/
static Position SingleRotateWithLeft( Position K2 ) {
  Position K1;
  K1 = K2->Left;
  K2->Left = K1->Right;
  K1->Right = K2;
  K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
  K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;
  return K1;  //Новый корень
}

//функция выполняет поворот между вершинами K1 и его правым потомком
static Position SingleRotateWithRight( Position K1 ) {
  Position K2;
  K2 = K1->Right;
  K1->Right = K2->Left;
  K2->Left = K1;
  K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;
  K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;
  return K2;  //новый корень
}

//функция выполняет двойной левый-правый поворот
static Position DoubleRotateWithLeft( Position K3 ) {
  // поворот между K1 и K2/
  K3->Left = SingleRotateWithRight( K3->Left );
  // поворот между K3 и K2
  return SingleRotateWithLeft( K3 );
}

//функция выполняет двойной правый-левый поворот
static Position DoubleRotateWithRight( Position K1 ) {
  // поворот между K3 и K2
  K1->Right = SingleRotateWithLeft( K1->Right );
  // поворот между K1 и K2
  return SingleRotateWithRight( K1 );
}

//функция вставки вершины в АВЛ-дерево
AvlTree Insert( ElementType X, AvlTree T ){
  if( T == NULL ){
    T = new AvlNode();
    if( T == NULL )
      fprintf( stderr, "Недостаточно памяти!!!\n" );
    else {
      T->Element = X; T->Height = 0;
      T->Left = T->Right = NULL;
    }
  }
  else if( X < T->Element ) {
    T->Left = Insert( X, T->Left );
    if( Height( T->Left ) - Height( T->Right ) == 2 )
      if( X < T->Left->Element )
        T = SingleRotateWithLeft( T );
      else
        T = DoubleRotateWithLeft( T );
  }
  else if( X > T->Element ) {
    T->Right = Insert( X, T->Right );
      if( Height( T->Right ) - Height( T->Left ) == 2 )
        if( X > T->Right->Element )
          T = SingleRotateWithRight( T );
        else
          T = DoubleRotateWithRight( T );
  }
  T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
  return T;
}

//функция возвращает значение, хранящееся в вершине
ElementType Retrieve( Position P ) {
  return P->Element;
}

//функция вывода АВЛ-дерева на печать
void printTree(AvlTree T, int l){
  int i;
  if ( T != NULL ) {
    printTree(T->Right, l+1);
    for (i=0; i < l; i++) cout << "    ";
    printf ("%4ld", Retrieve ( T ));
    printTree(T->Left, l+1);
  }
  else cout << endl;
}

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

Шаг 1. Поиск по дереву.

Шаг 2. Удаление элемента из дерева.

Шаг 3. Восстановление сбалансированности дерева (обратный проход).

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

Деревья цифрового (поразрядного) поиска

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

Поиск начинается от корня дерева. Если содержащийся в корневой вершине ключ не совпадает с аргументом поиска, то анализируется самый левый бит аргумента. Если он равен 0, происходит переход по левой ветви, если 1 – по правой. Если не обнаруживается совпадение ключа с аргументом поиска, то анализируется следующий бит аргумента и т.д. Поиск завершается, когда будут проверены все биты аргумента либо встретится вершина с отсутствующей левой или правой ссылкой.

Ключевые термины

Бинарное дерево цифрового поиска – это дерево, в каждой вершине которого хранится полный ключ, а переход по ветвям происходит на основе значения очередного бита аргумента.

Двоичное (бинарное) дерево – это иерархическая структура, в которой каждый узел имеет не более двух потомков.

Идеально сбалансированное дерево – это дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1.

Ключ поиска – это поле, по значению которого происходит поиск.

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

Поиск – это процесс нахождения конкретной информации в ранее созданном множестве данных.

Сбалансированное по АВЛ дерево – это дерево, для каждой вершины которого выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1.

Случайные деревья поиска – это упорядоченные бинарные деревья поиска, при создании которых элементы вставляются в случайном порядке.

Упорядоченное двоичное дерево – это двоичное дерево, в котором для любой его вершины x справедливы свойства: все элементы в левом поддереве меньше элемента, хранимого в x ; все элементы в правом поддереве больше элемента, хранимого в x ; все элементы дерева различны.

Частично упорядоченное бинарное дерево – это упорядоченное бинарное дерево, в котором встречаются одинаковые элементы.

Лабораторная работа 40. Алгоритмы поиска на основе деревьев

Цель работы: изучить алгоритмы поиска на основе деревьев, научиться решать задачи поиска через построение упорядоченного, случайного, оптимального или сбалансированного в высоту деревьев на языке C++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 40.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученным алгоритмами поиска на основе деревьев, реализовав программный код на языке С++. Рекомендуется воспользоваться материалами лекции 40, где подробно рассматриваются описание используемых в работе алгоритмов, примеры их реализации на языке С++. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя функции. Этапы решения сопроводить комментариями в коде. В отчете следует отразить разработку и обоснование математической модели решения задачи и привести примеры входных и выходных файлов, полученных на этапе тестирования программ.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы