РЕКУРСИВНЫЕ АЛГОРИТМЫ ПРИ РАБОТЕ С БИНАРНЫМИ ДЕРЕВЬЯМИ

Степович-Цветкова Г.С.

Кандидат экономических наук, Ивановский государственный университет

РЕКУРСИВНЫЕ АЛГОРИТМЫ ПРИ РАБОТЕ С БИНАРНЫМИ ДЕРЕВЬЯМИ

Аннотация

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

Ключевые слова: бинарное дерево, рекурсия.

Stepovitch-Tsvetkova G.S.

PhD in economic, Ivanovo State University

RECURSIVE ALGORITHMS TO WORK WITH BINARY TREES

Abstract

Recursive nature of binary trees is analyzed, some recursive algorithms for manipulating binary trees with the evaluation of their complexity are discussed.

Keywords: binary tree, recursion.

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

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

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

Рис. 1 – Бинарное дерево в виде ветвящегося списка

В таком представлении все дерево задается указателем на единственный его элемент – корневой узел, а каждый из элементов является объединением полей данных и двух указателей – ссылок на потомков, и определяется следующим типом, описанным на языке программирования С++:

struct Node{

       int info;   // поле данных

       Node *left; // указатель на левое поддерево

       Node *right;// указатель на правое поддерево

};

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

То есть очевидно применение рекурсии при полном обходе дерева для проведения однотипных операций над его узлами, например, для вывода элементов дерева на экран. Отметим, что существует три варианта обхода дерева: в прямом порядке, в симметричном и в обратном порядке. В первом случае каждый узел посещается до того, как посещены его потомки. Симметричный обход предусматривает посещение сначала левого поддерева, затем узла, затем правого поддерева. В случае обратного обхода узлы посещаются «снизу вверх». Например, функция вывода на экран дерева в порядке симметричного обхода выглядит следующим образом:

void print_tree(Node *p){

  if (p){

print_tree(p->left); //вывод левого поддерева

cout<<" "<<p->info<<" "; // вывод корня поддерева

print_tree(p->right); //вывод правого поддерева

  }

}

Формальным параметром, передаваемым функции, является указатель на просматриваемый узел дерева. В самом первом вызове функции в качестве этого узла выступает корневой элемент дерева. Условием выхода из рекурсии является отсутствие узла дерева (p==NULL). Если указатель p не нулевой, то есть очередной узел дерева существует, тогда функция рекурсивно вызывается для левого потомка, затем выводится на экран значение поля данных рассматриваемого узла, после чего функция рекурсивно вызывается для правого поддерева.

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

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