Деревья поиска
Дерево — одна из наиболее распространенных структур данных в программировании.
Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.
- Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
- Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
- Предки — родители родителей, их родители, и так далее.
- Потомки — дети детей, их дети, и так далее.
- Лист (терминальная вершина) — вершина, не имеющая детей.
- Поддерево — вершина дерева вместе со всеми её потомками.
- Степень вершины — количество её детей.
- Глубина вершины — расстояние от корня до неё.
- Высота дерева — максимальная из глубин всех вершин.
Деревья чаще всего представляются в памяти как динамически создаваемые структуры с явными указателями на своих детей, либо как элементы массива связанные отношениями, неявно определёнными их позициями в массиве.
Деревья также используются в контексте графов.
Бинарные деревья поиска
Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:
- У каждой вершины не более двух детей.
- Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
- У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
- У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.
Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.
Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:
Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.
Дерево как структура данных
Какую выгоду можно извлечь из такой структуры данных, как дерево? В этой статье мы расскажем о данных в виде дерева, рассмотрим основные определения, которые следует знать, а также узнаем, как и зачем используется дерево в программировании. Спойлер: бинарные деревья часто применяют для поиска информации в базах данных, для сортировки данных, для проведения вычислений, для кодирования и в других случаях. Но давайте обо всем по порядку.
Основные термины
Дерево — это, по сути, один из частных случаев графа. Древовидная модель может быть весьма эффективна в случае представления динамических данных, особенно тогда, когда у разработчика стоит цель быстрого поиска информации, в тех же базах данных, к примеру. Еще древом называют структуру данных, которая представляет собой совокупность элементов, а также отношений между этими элементами, что вместе образует иерархическую древовидную структуру.
Каждый элемент — это вершина или узел дерева. Узлы, соединенные направленными дугами, называются ветвями. Начальный узел — это корень дерева (корневой узел). Листья — это узлы, в которые входит 1 ветвь, причем не выходит ни одной.
Общую терминологию можно посмотреть на левой и правой части картинки ниже:
Какие свойства есть у каждого древа:
— существует узел, в который не входит ни одна ветвь;
— в каждый узел, кроме корневого узла, входит 1 ветвь.
На практике деревья нередко применяют, изображая различные иерархии. Очень популярны, к примеру, генеалогические древа — они хорошо известны. Все узлы с ветвями, исходящими из единой общей вершины, являются потомками, а сама вершина называется предком (родительским узлом). Корневой узел не имеет предков, а листья не имеют потомков.
Также у дерева есть высота (глубина). Она определяется числом уровней, на которых располагаются узлы дерева. Глубина пустого древа равняется нулю, а если речь идет о дереве из одного корня, тогда единице. В данном случае на нулевом уровне может быть лишь одна вершина – корень, на 1-м – потомки корня, на 2-м – потомки потомков корня и т. д.
Ниже изображен графический вывод древа с 4-мя уровнями (дерево имеет глубину, равную четырем):
Следующий термин, который стоит рассмотреть, — это поддерево. Поддеревом называют часть древообразной структуры, которую можно представить в виде отдельного дерева.
Идем дальше. Древо может быть упорядоченным — в данном случае ветви, которые исходят из каждого узла, упорядочены по некоторому критерию.
Степень вершины в древе — это число ветвей (дуг), выходящих из этой вершины. Степень равняется максимальной степени вершины, которая входит в дерево. В этом случае листьями будут узлы, имеющие нулевую степень. По величине степени деревья бывают:
— двоичные (степень не больше двух);
— сильноветвящиеся (степень больше двух).
Деревья — это рекурсивные структуры, ведь каждое поддерево тоже является деревом. Каждый элемент такой рекурсивной структуры является или пустой структурой, или компонентом, с которым связано конечное количество поддеревьев.
Когда мы говорим о рекурсивных структурах, то действия с ними удобнее описывать посредством рекурсивных алгоритмов.
Обход древа
Чтобы выполнить конкретную операцию над всеми вершинами, надо все эти узлы просмотреть. Данную задачу называют обходом дерева. То есть обход представляет собой упорядоченную последовательность узлов, в которой каждый узел встречается лишь один раз.
В процессе обхода все узлы должны посещаться в некотором, заранее определенном порядке. Есть ряд способов обхода, вот три основные:
— прямой (префиксный, preorder);
— симметричный (инфиксный, inorder);
— обратный (постфиксный, postorder).
Существует много древовидных структур данных: двоичные (бинарные), красно-черные, В-деревья, матричные, смешанные и пр. Поговорим о бинарных.
Бинарные (двоичные) деревья
Бинарные имеют степень не более двух. То есть двоичным древом можно назвать динамическую структуру данных, где каждый узел имеет не большое 2-х потомков. В результате двоичное дерево состоит из элементов, где каждый из элементов содержит информационное поле, а также не больше 2-х ссылок на различные поддеревья. На каждый элемент древа есть только одна ссылка.
У бинарного древа каждый текущий узел — это структура, которая состоит из 4-х видов полей. Какие это поля:
— информационное (ключ вершины);
— служебное (включена вспомогательная информация, однако таких полей может быть несколько, а может и не быть вовсе);
— указатель на правое поддерево;
— указатель на левое поддерево.
Самый удобный вид бинарного древа — бинарное дерево поиска.
Что значит древо в контексте программирования?
Мы можем долго рассуждать о математическом определении древа, но это вряд ли поможет понять, какие именно выгоды можно извлечь из древовидной структуры данных. Тут важно отметить, что древо является способом организации данных в форме иерархической структуры.
В каких случаях древовидные структуры могут быть полезны при программировании:
- Когда данная иерархия существует в предметной области разрабатываемой программы. К примеру, программа должна обрабатывать генеалогическое древо либо работать со структурой каталогов. В таких ситуациях иногда есть смысл сохранять между объектами программы существующие иерархические отношения. В качестве примера можно вывести древо каталогов операционной системы UNIX:
- Когда между объектами, которые обрабатывает программа, отношения иерархии не заданы явно, но их можно задать, что сделает обработку данных удобнее. Как тут не вспомнить разработку парсеров либо трансляторов, где весьма полезным может быть древо синтаксического разбора?
- А сейчас очевидная вещь: поиск объектов более эффективен, когда объекты упорядочены, будь то те же базы данных. К примеру, поиск значения в неструктурированном наборе из тысячи элементов потребует до тысячи операций, тогда как в упорядоченном наборе может хватить всего дюжины. Вывод прост: раз иерархия — эффективный способ упорядочивания объектов, почему же не использовать древовидную иерархию для ускорения поиска узлов со значениями? Так и происходит: если вспомнить бинарные деревья, то на практике их можно применять в следующих целях:
— поиск данных в базах данных (специально построенных деревьях);
— сортировка и вывод данных;
— вычисления арифметических выражений;
— кодирование по методу Хаффмана и пр.
Деревья как концепция — Алгоритмы на деревьях
Иерархические структуры окружают нас везде — например, структура управления предприятием, адреса, содержания в книгах. Иерархия встречается и в программировании, например, в работе со стандартными типами данных, такими как массивы. Так как такие данные нельзя разместить линейно, программисты используют деревья. Они считаются одной из важнейших нелинейных структур, которые встречаются при работе с алгоритмами.
В этом уроке мы поговорим о деревьях, узнаем, какие проблемы они решают, и какие характеристики и способы представления деревьев существуют.
Что такое деревья и для чего они нужны
Деревья используют, чтобы отразить в памяти компьютера иерархические взаимосвязи. Их применяют для реестра Windows, XML-документов, DOM-структур HTML-страниц, родословных, каталогов запчастей или файловых систем. Например, так файловую структуру видят конечные пользователи:
При этом для программистов она выглядит иначе:
Это древовидное представление структуры. Из этой схемы можно сделать вывод, что дерево — это конечное множество, которое состоит из вершин или узлов, а еще есть выделенный узел — корень дерева. В примере выше вершины — это все папки, а корень дерева — «Новая папка».
Каждый узел содержит данные и ссылки на другие непересекающиеся между собой деревья. В этом случае каждая папка в дереве, от которой исходят другие данные, является для них корневым узлом. При этом эти данные образуют поддерево основного дерева.
Помимо представления иерархических взаимосвязей, деревья применяют в следующих случаях:
- Организация быстрого поиска в отсортированных данных, например, в индексах баз данных
- Кластеризация данных. Возможность разбивать данные на кластеры применяется в базах данных и машинном обучении
- Решение сложных арифметических выражений. Дерево используется, чтобы хранить порядок выполнения операций, значений аргументов и промежуточных результатов
- Алгоритмы принятия решений. Дерево решений — инструмент интеллектуального анализа данных и проведения предсказаний. Он считается более простым в работе инструментом, чем нейросети, так как формулирует правила на естественном языке
- Сетевое взаимодействие. Деревья используют для маршрутизации и работы механизмов определения IP-адресов по URL сайта, например, DNS-сервера
Деревья часто используют в проектах по разработке программ. Как результат — разработчики выделили терминологию описания узлов и формы деревьев.
Какие узлы есть в деревьях
Так как внешний вид дерева схож с генеалогическим деревом, термины генеалогии применяются и в программировании. Например, в отношении алгоритмических деревьев можно услышать такие термины, как «основатель династии», «мама», «ребенок», «брат», «двоюродный дядя». При этом существуют стандартизированные именования для отношений узлов:
- Родительский узел или предок — узел, который находится на первом уровне иерархии
- Дочерний узел или потомок — узел, на который есть ссылки из рассматриваемого узла
- Корневой узел — узел, на который нет ссылок из других узлов
- Сестринские узлы — два узла, у которых общие родители
- Листовой узел, лист дерева или терминальный узел — узел, у которого количество поддеревьев равно нулю
- Узел ветвления или внутренняя вершина — узел, у которого есть дочерние структуры
Количество поддеревьев у узла называется его степенью. Максимальное значение степени узла — степень дерева. Если степень дерева равна двум, значит, у каждого узла может быть не более двух потомков:
Какие формы деревьев бывают
Из-за определенных особенностей задач и алгоритмов, разработчики применяют разные формы деревьев со своими особенностями организации вершин:
- Упорядоченное дерево — дерево, в котором все вершины отсортированы. Такие деревья еще называются плоскими, так как при последовательном обходе вершин получится отсортированный массив:
Далее в курсе мы будем считать все деревья упорядоченными, если в условии не сказано обратное.
- Полное дерево — дерево, в котором количество дочерних узлов у каждой внутренней вершины равно степени дерева:
- Завершенное дерево – дерево, у которого каждый уровень, кроме последнего, является полным:
- Идеальное дерево — полное дерево, у которого все терминальные узлы располагаются на одном уровне:
Мы познакомились с основной терминологией, которая используется при работе с деревьями. Теперь рассмотрим, какие есть способы представления деревьев в графическом виде и в коде.
Как могут выглядеть деревья
Чтобы изображать иерархические структуры, используют следующие варианты:
- Древовидное схематическое представление
- Круги Эйлера
- Списки с отступами
- Код
Разберем каждый способ изображения дерева.
Древовидное схематическое представление
В качестве основного способа представления деревьев используют имена, номера вершин или содержимое полезных данных узла. Они соединяются линиями, которые обозначают связи между вершинами:
Этот способ похож на природные деревья, только в информатике корень дерева обычно рисуется вверху схемы.
Круги Эйлера
Мы можем изобразить алгоритмическое дерево по правилам теории множеств с помощью кругов Эйлера:
Данный способ на практике встречается достаточно редко, так как поддеревья обычно не пересекаются между собой. В такой ситуации использование схематичного представления более наглядно для человека.
Списки с отступами
Иерархическую связь можно изображать через пронумерованный список с отступами, где отступ или номер строки будут означать ее уровень:
Такой формат используют при работе с книгой, так как оглавление — это дерево.
Код
Чтобы работать с деревьями, их нужно уметь не только рисовать, но и хранить в памяти компьютера.
В виде кода мы получаем следующий класс узла:
class BinaryTreeNode constructor(value, parent) this.child1 = null; this.child2 = null; this.parent = parent; this.value = value; > >class BinaryTreeNode public BinaryTreeNode child1 = null; public BinaryTreeNode child2 = null; public BinaryTreeNode parent; public Object value; BinaryTreeNode(Object value, BinaryTreeNode parent) this.parent = parent; this.value = value; > >class BinaryTreeNode: def __init__(self, value, parent=None): self.child1 = None self.child2 = None self.parent = parent self.value = valueparent = $parent; $this->value = $value; > >Чтобы организовать из узла дерево, нужно добавить методы, которые заполняют ссылки на поддеревья child1 и child2 . Как реализуются деревья в коде, разберем подробно в следующих уроках.
Прежде чем писать код дерева, разработчики часто изображают иерархию графически, чтобы видеть полную картину взаимосвязей.
Занятие 11. Деревья в программировании: построение и использование Текст научной статьи по специальности «Математика»
Автор знакомит читателя с понятием дерева, с примерами использования этой структуры как в повседневной жизни, так и в программировании. Рассматриваются некоторые алгоритмы обработки дерева.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Дмитриева Марина Валерьевна
Списки и другие динамические структуры
Занятие 8. Формулы, формулы, формулы. . .
Организация данных в виде очереди
Обход деревьев на основе автоматного подхода
Алгоритм кодирования бинарного дерева с минимальной избыточностью
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Текст научной работы на тему «Занятие 11. Деревья в программировании: построение и использование»
Дмитриева Марина Валерьевна
ЗАНЯТИЕ 11. ДЕРЕВЬЯ В ПРОГРАММИРОВАНИИ: ПОСТРОЕНИЕ И ИСПОЛЬЗОВАНИЕ
Многие реальные объекты имеют иерархическую структуру, например, схема предприятия или структура власти в государстве, генеалогическое дерево семьи или родословная некоторого человека. Для представления таких объектов и обработки связанной с ними информации удобна организация данных, отражающая структуру объектов. Если абстрагироваться от конкретного содержания элементов, то получится математический объект, называемый деревом. Рассмотрим некоторые способы представления и обработки деревьев.
ПРЕДСТАВЛЕНИЕ ДАННЫХ С ПОМОЩЬЮ ДЕРЕВА
Данные, имеющие иерархическую структуру, удобно представлять с помощью деревьев. Дерево представляет собой конечное множество элементов, называемых узлами, или вершинами. Вершины расположены на разных уровнях иерархии. На самом высоком уровне иерархии (пусть номер этого уровня 1) располагается единственный узел, называемый корнем. Каждый узел, расположенный на г-ом уровне, связан на более высоком (г-1)-ом уровне с единственным узлом, который является исходным, или предком для данного узла. Каждый узел г-ого уровня может быть связан с одним или несколькими узлами на более низком (г+1)-ом уровне. Такие узлы (г+1)-ого уровня называются
порожденными узлами, или потомками. Узлы, не имеющие порожденных, называются листьями. На плоскости узлы удобно изображать точками, узлы г-ого уровня связывать дугами с порожденными узлами (г+1)-ого уровня.
Примером дерева может служить генеалогическое дерево, в котором порожденными узлами являются сыновья. На рисунке 1 изображено лишь два поколения потомков Александра Невского: сыновья и внуки.
Дмитрий I Андрей II
урл&Ле иерархии . рлспамлгле1&с& Нл^и^лемий корнем.
Юрий II Иоанн I Калита Рисунок 1
Можно построить генеалогическое дерево своей семьи, выбрав в качестве корня дерева, например, прадедушку. С помощью дерева можно представить родословную некоторого человека. В таком дереве каждый узел имеет два порожденных, например, левый узел хранит данные о матери, правый — об
МофШ пасеиршень геЯелмхгагеосае сбей
семш, 6 клгесеи&е .
отце. На каком-то уровне информация о родственниках безвозвратно утеряна.
На рисунке 2 изображено дерево, узлы которого помечены буквами. Корнем этого дерева является узел А. Это единственный узел, расположенный на самом высоком уровне иерархии. Порожденные корнем узлы: С, Д Е. Узел А для узлов С, Д Е является исходным. Узлы О, I, К, Ь, М, Е не имеют порожденных узлов и являются листьями. На рисунке 3 изображены три дерева. Последнее дерево состоит лишь из одного узла — корня Е. Эти три дерева являются поддеревьями дерева, расположенного на рисунке 2. Корни этих поддеревьев связаны с единственным узлом А. Узел А расположен на
более высоком уровне иерархии. Таким образом, порожденные узлы являются корнями поддеревьев данного дерева. При таком способе представления дерева достаточно иметь указатель на корень дерева для того, чтобы получить доступ к любой вершине дерева.
Дерево можно определить как частный случай графа, а именно, дерево — это связный граф без циклов. В [6] приведены примеры различных деревьев и способы их представления.
Приведем рекурсивное определение дерева. Деревом называется конечное множество элементов Д состоящее из одного или нескольких элементов, удовлетворяющее условиям:
1. Есть один выделенный элемент, называемый корнем дерева.
2. Остальные элементы множества Д содержатся в т попарно непересекающихся множествах Д2. Дт, каждое из которых является деревом. Деревья Др Д2. Дт являются поддеревьями выделенного корня.
Дерево, изображенное на рисунке 2, можно представить в виде совокупности множеств (рисунок 4). Элемент А — корень дерева, остальные элементы содержатся в трех попарно непересекающихся множествах , , . Каждое из множеств, в свою очередь, является деревом. Рассмотрим множество . Элемент С — корень дерева, остальные элементы содержатся в трех по-
«Приберем. рекурсив-Аое определение fepeе6i.
парно непересекающихся множествах [О>,,, каждое из которых — дерево, состоящее лишь из одного элемента -корня. Если узлы изобразить точками на плоскости, а корни дерева связать с корнями поддеревьев, то получим изображение, как на рисунке 2.
При работе с деревьями удобно определить пустое дерево как дерево, не содержащее узлов.
И ИХ ПРЕДСТАВЛЕНИЕ
Структуры данных и алгоритмы их обработки будут наиболее простыми в случае так называемых бинарных деревьев, то есть таких деревьев, каждый узел которых имеет не более двух порожденных узлов (левого и правого), и, соответственно, не более двух поддеревьев (левого и правого). На рисунке 5 представлены бинарные деревья. Деревья на рисунках 5в и 5г различны, так как в первом случае узел D является левым порожденным для С, а во втором — правым порожденным для С.
Один из способов представления деревьев применяется в случае, если из-
вестно, что каждый элемент дерева имеет не более k поддеревьев при небольшом значении k. Тогда можно включить в каждый элемент k указателей на поддеревья. Наиболее частый случай k = 2, при котором дерево называют бинарным, а два поддерева — левым и правым, соответственно. При таком способе представления достаточно иметь лишь указатель на корень дерева, чтобы получить доступ к любому элементу, спускаясь вниз по указателям. Отсутствующее дерево представляется пустым указателем.
Узел дерева представляет собой запись, состоящую из трех полей, первое поле — информационное, второе и третье — указатели на левый и правый порожденные узлы (на корни левого и правого поддеревьев). Если элемент имеет тип node, то тип значения, называемого указателем на элемент node, записывается так: Anode. В разделе определения типов можно ввести синоним для типа Anode: tree=Anode .
Описание типов данных для бинарного дерева может выглядеть так: type elem_tree=char; tree=Anode;
Заметим, что в описании сначала идет определение типа tree, так как тип tree используется при описании полей left и right. Заметим, что конструкция Az — единственный описатель типа, который может содержать еще не определенный в программе идентификатор типа Z. Если в программе переменная t описана следующим образом: var t: tree, то говорят, что t является указателем на элемент типа node. Переменная t может иметь значение nil. Это означает, что указатель не установлен ни на какой элемент. Переменная, на которую установлен указатель, обозначается tA, в нашем случае tA имеет тип node. Получить доступ к полям переменной tA можно следующим образом: tA. info, tA . left, tA . right.
Если в программе описаны две переменные p и q (var p,q: tree), то после выполнения оператора присваивания p:=q оба указателя p и q установлены на одну и ту же переменную, а именно на ту, на которую первоначально был установлен указатель q. Значение переменной типа указателя может измениться в результате выполнения оператора присваивания p:=nil. Значение переменной типа указателя
может измениться в результате выполнения стандартной процедуры new (p), при выполнении которой выделяется память под значение типа node, и указатель p устанавливается на новый, созданный элемент с неопределенными значениями полей. Если память не может быть выделена, то значение p становиться равным nil.
Выполнение оператора присваивания рл._ дл приведет к тому, что, хотя указатели установлены на разные переменные, значения этих переменных одинаковы.
ОСНОВНЫЕ АЛГОРИТМЫ ОБРАБОТКИ БИНАРНЫХ ДЕРЕВЬЕВ
При обработке деревьев удобно использовать рекурсивные методы. Напомним, что при разработке рекурсивного алгоритма требуется обратить внимание на следующие моменты:
1. Определить параметры, от которых зависит решение задачи.
2. Решить задачу в тривиальном случае.
3. Свести задачу к ней самой, но с другими, более «простыми», параметрами.
ЧИСЛА УЗЛОВ БИНАРНОГО ДЕРЕВА
При выбранном способе представления дерева для его задания достаточно иметь указатель на корень дерева, который и является единственным параметром. Если дерево пусто, то число его узлов равно 0. Это и есть решение задачи в триви-
Ири 6-ибрлЯАо^ способе fefiefia
его jnyaHufr дос&л&огЯо име&ь укл^л&ель Нл кореЯь
Окшишйе рещрси&Кый л*горм%ж ммигес&&л лиа&ьеб- биНлрНога
альном случае. Если же дерево не пусто, то число его узлов определяется как сумма числа узлов в левом поддереве и числа узлов в правом поддереве, увеличенная на единицу. Число узлов дерева можно определить рекурсивно следующим образом:
nnode(t)=1+nnode(t/)+ nnode(tr), где t — исходное дерево, t/, tr — левое и правое поддеревья. Таким образом, решение задачи о числе узлов дерева сведено к решению той же самой задачи, но уже применительно к поддеревьям данного дерева. В каждом из поддеревьев число узлов меньше, чем в дереве. Именно в этом смысле понимаются в данном случае более «простые» параметры.
Опишем функцию, которая для бинарного дерева, заданного указателем на корень, определяет количество узлов в дереве.
function nnode (t: tree): integer; begin
if t=nil then nnode=0
else nnode = 1+nnode(^.left) + nnode(^.right)
Задача 1. Уровень 1.
1) Опишите рекурсивный алгоритм вычисления количества листьев бинарного дерева.
В терминах генеалогического дерева — это количество членов рода, не имеющих (или не имевших) сыновей. В терминах дерева родословной — это те предки, про обоих родителей которых нам ничего не известно. 2) Опишите рекурсивный алгоритм вычисления количества ребер бинарного дерева. В терминах генеалогического дерева — это число сыновей в роду, в терминах дерева родословной — число известных предков.
ОПРЕДЕЛЕНИЕ ВЫСОТЫ ДЕРЕВА
Высотой дерева называется максимальный из уровней всех узлов дерева. Высота пустого дерева равна 0, высота дерева, состоящего лишь из корня, равна 1, высота дерева, изображенного на рисунке 6, равна 5. На рисунке 7 изображено дерево, где через А и В обозначены поддеревья, которые в общем случае могут быть и пустыми. При построении ал-
горитма можно рассуждать и так: как найти высоту дерева T, если известны высоты поддеревьев A и B? Для того чтобы найти высоту дерева T, надо взять максимальную из высот поддеревьев A и B и увеличить на 1.
Рекурсивно высоту бинарного дерева t опишем так:
h(t)=max(h(tl),h(tr))+1, h(null)=0, где t — исходное дерево, tl, tr — левые и правые поддеревья, null — пустое дерево.
. tcatc лай&и бшо&у fefte&a если и^&ес&Яи
ПОИСК ЭЛЕМЕНТА В ДЕРЕВЕ
Рассмотрим решение задачи поиска элемента в дереве. При решении этой задачи используются два параметра, один параметр задает дерево, второй — тот элемент, который требуется найти в дереве. Как и ранее, тривиальное решение будет в случае, когда дерево пусто. В таком дереве нет узлов, следовательно, нет интересующего нас узла. Если дерево не пусто, то исследуется корень дерева. Если элемент, расположенный в корне дерева, совпадает с заданным элементом, то задача решена. В противном случае поиск элементов следует производить
Лв поддеревьях А и В (рисунок 7). Порядок просмотра поддеревьев произволен, если это не оговорено особо. Просматриваем, например, поддерево А. Если требуемый элемент найден, то задача решена. Если же элемент в поддереве А не обнаружен, то поиск следует продолжать в поддереве В. В этом случае результат поиска во всем дереве зависит от того, найден или нет элемент в поддереве В.
Задача 2. Уровень 1. Опишите рекурсивный алгоритм, определяющий число элементов в бинарном дереве, равных заданному.
Уровень 2. Напишите рекурсивную процедуру определения числа узлов, находящихся на заданном уровне.
Окамайе ремра&Лый алгори&ж, оореефеляощий гасло злемеЛ&об б баЛарЛом феребе, рабЛих ¿арлЛЛаму.
Формат ввода: Заданный уровень к Количество узлов в дереве п
Дрмжечянме. ЛП — ссылка на левое поддерево, ПП — ссылка на правое поддерево, пустые поддеревья обозначаются 0.
Формат вывода: Число узлов на уровне к
Дерево изображено на рисунке 8.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
рексрибЛфа про^еф^р^ оореуелеЛия Лахофящахся Ла ^ЛфЛЛЛаж уробне.
Одна из распространенных задач при работе с деревьями — выполнение некоторого действия р с каждым элементом дерева. Часто такую задачу называют задачей обхода дерева. При работе с деревьями операций [7] приводились алгоритмы обхода, позволяющие по дереву операций получить префиксную и постфиксную нотацию формул.
В качестве примера приведем левосторонний обход дерева. При левостороннем обходе сначала полностью обходится левое поддерево корня (если поддерево существует), затем действие р применяется к корню дерева, а затем обходится правое поддерево. При этом поддерево обходится левосторонним способом, то есть описанный алгоритм является рекурсивным.
Опишем алгоритм нахождения всех узлов дерева, расположенных на г-ом уровне (г >0). В этом случае задача имеет два параметра, один задает бинарное дерево, второй — номер уровня, на котором ищем вершины. Если дерево пусто, то вершин г-ого уровня в нем нет. Если же дерево не пусто и значение г равно 1, то элемент г-ого уровня -это корень дерева. Сведем решение задачи к ней самой, но с другими параметрами. Заметим, что все узлы г-ого уровня дерева I являются узлами
уадагей обхоул фере&а.
(г -1)-ого уровня для левого и правого поддеревьев дерева Например, узлы D, Е, ¥ являются узлами третьего уровня для дерева на рисунке 6 и узлами второго уровня для левого и правого поддеревьев, изображенных на рисунке 9.
Уровень 2. После многих часов, проведенных в библиотеке, Виви составила свою родословную. Она получилась настолько обширной, что Виви запуталась в отношениях родства между своими предками. Помогите Виви разобраться в ее родословной. Для этого напишите программу, которая выписыва-
ет для двух предков Виви их отношение родства. Родословная задана бинарным деревом, причем для каждого человека в корне левого поддерева находится его мать, а в корне правого — отец.
Формат ввода: п (количество узлов дерева без учета корня)
1 имя 1 ЛП1 ПП1
2 имя 2 ЛП2 ПП2
п имя п ЛПп ППп Имя предка 1 Имя предка 2
Формат вывода: Отношение родства между предком 1 и предком 2.
Примечание. Для описания следует использовать только слова «мать, матери, сын, сына, отец, отца, дочь, дочери». (Если имен, приведенных в примере окажется недостаточно, можно использовать следующие: Васио, Петио, Толио, Борио, Мими, Диди, Лулу, Зузу и т.д.) Дерево изображено на рисунке 10.
Люси = мать дочери сына Лили
Антонио (Г’ Лили 4 5
БИНАРНОЕ ДЕРЕВО ПОИСКА
Бинарное дерево удобно использовать для быстрого поиска данных. Будем считать, что элементы, которые будут организованы в бинарное дерево, снабжены числовым признаком, который назовем весом элемента. Элементы в дереве будем размещать таким образом, чтобы левое поддерево любого узла L содержало только те узлы, вес которых меньше, чем вес узла Ь, а правое поддерево — те узлы, вес которых больше или равен весу узла Ь. Такие деревья называют деревьями поиска или сортировки. На рисунке 11 изображено такое дерево.
Опишем алгоритм добавления элемента с заданным значением г в дерево поиска Т. Сравнивается вес г с весом корня дерева Т. Если вес г меньше, то элемент следует разместить в левом поддереве Т, в противном случае — в правом. Далее поиск места для размещения элемента повторяется рекурсивно. Добавляемый элемент образует новый лист дерева.
При добавлении элементов со значениями 3 и 5 в дерево поиска, изображенное на рисунке 11, дерево примет вид, показанный на рисунке 12.
Guftafeftoe дерево удобно
бисЛрого поиссл gaftftux.
Опишем процедуру добавления в бинарное дерево поиска T элемента z. Считаем, что тип информационного поля элемента дерева -целый
(elem_tree=integer) procedure add_tree
(var t: tree; z: elem_tree); var p:tree; begin if t=nil
then begin new(t); tA.info := z; tA.left := nil; tA.right := nil end
. дерево примой (кид, tcatc fuucajafto fta fcucyftice.
При левостороннем обходе бинарного дерева поиска элементы дерева образуют возрастающую последовательность, ле-12 восторонний обход дерева на рисунке 12 обеспечит обработку вершин в порядке: 2 3 3 4 5 5 6
7 8 9 10. При правостороннем обходе значения будут расположены в порядке убывания.
Для деревьев поиска легче, чем для обычных бинарных деревьев, решается задача поиска. На каждом шаге известно поддерево, в котором следует продолжать поиск.
ПОИСК С ВКЛЮЧЕНИЕМ
При решении многих задач используется алгоритм, который получил название Доиск с включением. Согласно этому алгоритму элемент добавляется в дерево поиска лишь в тех случаях, если такого элемента в дереве не было. Таким образом, все элементы дерева различны.
Уровень 1. Опишите два алгоритма (рекурсивный и нерекурсивный) поиска элемента с заданным весом в дереве поиска.
Уровень 2. Задана последовательность ненулевых целых чисел, число 0 — признак конца. Напишите программу, которая формирует последовательность чисел в порядке убывания, причем каждое число встречается в этой последовательности лишь один раз.
Указание. По заданной последовательности постройте дерево поиска, используя процедуру, реализующую алгоритм поиска с включением. Затем осуществите правосторонний обход построенного дерева.
Формат ввода: Последовательность натуральных чисел, завершаемая нулем
Формат вывода: Отсортированная в порядке убывания последовательность без повторений
Дрижер. Ввод: 6 2 8 5 0 Вывод: 5 2
ОоимшЯе фба алгоритма . ооиасл с ^ЛфЛЛЛим бесом б феребе поиаса.
Рассмотрим задачу, которая является упрощенным вариантом задачи о частотном словаре. Вместо анализа слов некоторого текста, будут анализироваться числа некоторой последовательности.
Во входном потоке задана последовательность ненулевых целых чисел, число 0 считается признаком конца последовательности. Требуется написать программу, которая формирует две таблицы. В каждой из таблиц хранится число и количество его вхождений в последовательность. Первая таблица упорядочена в порядке возрастания чисел, вторая — в порядке убывания частот вхождения. Нам неизвестно количество различных чисел в последовательности, поэтому мы не знаем размера таблиц.
Можно поступить следующим образом: все числа последовательности организовать в бинарное дерево поиска. Для каждого числа проверять, встречалось ли оно ранее в последовательности. Если число встретилось впервые, то в дерево включить узел, одно из полей которого совпадает с числом, второе поле характеризует частоту вхождения и равно в данном случае 1. Если же рассматриваемое число уже в последовательности
встречалось, то в дереве есть соответствующий этому числу узел. В этом случае узел надо найти и частоту вхождения увеличить на 1.
После просмотра всей последовательности будет построено дерево поиска, количество узлов которого равно количеству различных чисел в последовательности. С каждым числом хранится количество его вхождений в последовательность. Осуществляя левосторонний обход дерева, получим таблицу, числа в которой упорядочены по возрастанию. Рассмотрим последовательность чисел: 12 7 3 15 3 9 7 12 13 7 3 9 17 9 13 3 17 3 9 0. После просмотра всей последовательности будет построено дерево Г, изображенное на рисунке 13. В каждом узле дерева первое число — элемент последовательности, второе число — частота вхождения в последовательность. При применении левостороннего обхода к построенному дереву Г будут выведены значения, представленные в таблице 1.
ты которого упорядочены по частоте вхождения, а затем применить к нему процедуру правостороннего обхода.
При левостороннем обходе дерева Г в качестве процедуры обработки узла возьмем процедуру добавления узла в дерево поиска ^ так чтобы дерево L было упорядочено по частоте вхождения элементов в последовательность. Дерево изображено на рисунке 14.
Применяя правосторонний обход к дереву ^ получим следующую таблицу 2, элементы которой упорядочены в порядке убывания частот.
Элемент последовательности Частота вхождения
Применим правосторонний обход дерева Г и построим дерево поиска элементы которого упорядочены по частоте вхождения. Дерево представлено на рисунке 15. Применяя к дереву Ъ, пра-
Элемент последовательности Частота вхождения
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Для того чтобы построить таблицу в порядке убывания частот, можно по дереву поиска построить дерево, элемен-
восторонний обход, получим таблицу 3, которая упорядочена в порядке убывания частот, но отлична от таблицы 2.
Элемент последовательности Частота вхождения
Уровень 2. Напишите программу, которая по последовательности чисел формирует две таблицы и реализует описанный алгоритм.
Формат ввода: Последовательность натуральных чисел, завершаемая нулем
Формат вывода: Две таблицы построчно и поочередно
12 7 3 15 3 9 7 12 13 7 3 9 17 9 13 3 17 3 9 0
С помощью бинарного дерева удобно представлять различные формулы. В [7] рассматривались различные способы представления формул и некоторые алгоритмы их обработки. Один из способов представления формул — использование дерева операций. Формула просматривалась слева направо, и с помощью стека строилось дерево операций. Напомним, что в дереве операций каждый узел (кроме листьев) соответствует операции, а левое и правое поддеревья — операндам.
Опишем алгоритм построения дерева операций по формуле, представленной строкой. Формула просматривается слева направо один раз.
Будем считать, что формула состоит из однобуквенных идентификаторов (букв латинского алфавита), круглых скобок и
Один способов предайлблеНи^-формул — «спольуоблНие деряба операций.
операций (+, -, *, /). Для анализа формулы нам удобно ввести следующие понятия, характеризующие отдельные части формулы и формулу в целом. Будем называть лножителел либо идентификатор переменной либо формулу, заключенную в круглые скобки. Назовем терлол либо один множитель либо последовательность множителей, соединенных знаками «*» и «/», форлулом — либо один терм либо последовательность термов, соединенных знаками «+» и «-».
Опишем процедуру Form с одним параметром t, действие которой состоит в том, что по просмотренной формуле процедура строит соответствующее ей дерево операций со ссылкой на корень t По данному нами определению, формула всегда начинается с терма. Будем считать, что процедура Term(^) строит дерево для части формулы, являющейся термом, и ^ — ссылка на корень построенного дерева. При анализе формулы в результате исполнения вызова Term(^) будет построено дерево, соответствующее первому терму формулы со ссылкой на корень ir Если в формуле следующий за первым термом символ отличен от знака операции «+» или «-», то это означает, что формула состоит из одного терма, и анализ формулы завершен. Если же вслед за первым термом идет знак операции «+» или «-», то требуется продолжать анализ формулы. Далее формируется узел дерева для знака операции. В качестве левого поддерева надо взять дерево, соответствующее пер-
вому терму, с помощью процедуры Term построить дерево для следующего терма — формулы и взять его в качестве правого поддерева узла, соответствующего знаку операции, и т.д. Если формула имеет вид /D Tj+Tj-Tj+Tj, то в результате работы процедуры Form должно быть по-РИСуН0К 18 строено дерево, показанное на рисунке 16. Процедура Form по формуле A+B-C+D построит дерево, изображенное на рисунке 17, а по формуле A+(B-(C+D)) — дерево, изображенное на рисунке 18.
При решении этой задачи тип элемента дерева символьный (elem_tree=char). Опишем процедуру, которая строит дерево с указателем t на его вершину для формулы. Первый элемент уже выбран. Текущий символ хранится в переменной c.
procedure Form (var t: tree);
var p,t1,t2 : tree; begin Term(t1);
Теперь опишем процедуру Term. Нам требуется, чтобы процедура Term умела по соответствующему терму строить дерево с указателем на корень t Мы определили терм так, что он всегда начинается с множителя. Будем считать, что процедура Mn(t) строит дерево операций для части формулы, определенной как мно-
житель, и формирует указатель t на корень построенного дерева. Процедура Term похожа на процедуру Form.
Процедура Mn анализирует часть формулы, определенной как множитель, строит дерево, соответствующее проанализированной части формулы, и выбирает следующий за множителем символ. Считаем, что первый символ множителя уже выбран. Множителем является либо идентификатор, либо формула, заключенная в скобки. Если очередной символ — буква (множитель в данном случае — это идентификатор), то строится дерево t с одним узлом, и для анализа выбирается следующий символ формулы.
Если же очередной символ — открывающая круглая скобка, то требуется проанализировать случай, когда множитель представляет собой формулу, заключенную в скобки. Следует воспользоваться процедурой Form, которая умеет строить дерево с указателем на корень t для любой формулы. Итак, в этом случае множитель имеет вид f), и мы предположили, что в результате работы процедуры Form построено дерево со ссылкой на корень t, соответствующее формуле f. После работы процедуры Form выбран следующий за формулой символ. Если этот символ — закрывающая скобка, то анализ множителя завершен, осталось выбрать только следующий за скобкой символ для продолжения анализа формулы. Если же проанализирована формула f а за ней символ, отличный от закрывающей скобки, то нарушен баланс скобок, возникла ошибочная ситуация. Если же окажется, что очеред-
ной символ не буква и не открывающая скобка, то должна быть зафиксирована ошибка.
Уровень 2. Напишите программу, которая по формуле, представленной строкой, строит дерево операций. По дереву операций сформируйте формулу в постфиксной записи.
Формат ввода: Формула со знаками операций «+», «-», «*», «/» и операндами, представленными буквами латинского алфавита.
Формат вывода: Формула в постфиксной записи.
Одну и ту же формулу можно записать разными способами, расставляя в ней скобки или опуская их согласно приоритетам операций. Например, формула а*Ь+с может быть записана одним из способов: (а*Ь)+с, ((а*Ь)+с), ((а)*(Ь)+(с)).
Можно считать, что все формулы различны, но эквиваленты между собой. Пару скобок назовем избыточной, если после ее удаления формула остается эквивалентной исходной. Три приведенные формулы содержат избыточные скобки. Каждой из четырех формул соответствует дерево операций, приведенное на рисунке 19.
¡офЛо сш&л&ь, &се формулы, рлржгЛи, Ла жМллеЛ&и мефду собой.
Уровень 2. Пусть заданы две формулы / и /2. Напишите программу, проверяющую их эквивалентность.
Указание. Можно поступить следующим образом: по каждой из формул построить дерево операций, затем сравнить построенные деревья. Если формулы отличаются лишь избыточными скобками, то деревья операций у них должны совпадать.
Формат ввода: Формула 1 Формула 2
Формат вывода: Да/нет
Уровень 1. Опишите алгоритм про верки, является ли одно дерево поддере вом другого.
Немного усложним задачу сравнения формул. Будем рассматривать формулы, состоящие из малых латинских букв, круглых скобок, знаков операций «+» и «*», обладающих свойством коммутативности (перестановочности). Формулы будем считать эквивалентными, если на каждом уровне скобок они отличаются лишь порядком своих операндов. Следующие формулы эквивалентны: (а+Ь) и (Ь+а), ((а*Ь)+с) и (с+(Ь*а)).
Уровень 2. Напишите программу, проверяющую эквивалентность формул с учетом коммутативности операций.
Указание. Для того чтобы проверить, эквивалентны ли такого вида формулы, можно построить по ним деревья операций и далее сравнивать полученные деревья.
Формат ввода-вывода такой же, как в задаче 8.
Рассмотрим формулу, в которой встречаются целые константы (для простоты возьмем от 0 до 9), переменные, круглые скобки и знаки операций «+» и «*». Требуется по заданной формуле построить формулу, являющуюся ее производной по некоторой переменной. Для решения этой задачи представим формулу деревом операций. В результате действий над деревом операций, представляющим формулу, построим дерево операций для производной заданной формулы.
Если формула / представляет собой константу, то ее производная равна нулю. Если формула состоит из одной переменной х, по которой находится производная, то по дереву операндов (рису-
* Для учащихся 10-11 классов.
нок 20а) должно быть построено дерево (рисунок 20Ь).
Пусть теперь формула имеет вид: g+h. Тогда соответствующее формуле дерево операций изображено на рисунке 21а, где О, Н — деревья операций для формул g и h соответственно. Так как производная в этом случае равна g’+h’, то деревья операций для производных должны быть такими, как на рисунке 21Ь, где О’, Н’ — деревья операций для формул №. Для того, чтобы найти производную формулы /, требуется найти производные для составляющих ее формул g и h. Задача свелась к ней самой, но с более простыми параметрами.
Нам осталось рассмотреть случай, когда формула / имеет вид g*h. Дерево для такой формулы представлено на рисунке 22а. Производной является формула вида g’*h + g*h’. Ей соответствует дерево операций на рисунке 22б, где О, Н, О’, Н’ — деревья операций для формул g, Ь g’, М, соответственно. Для того, чтобы строить производную в этом случае, надо уметь строить копию дерева операций.
Уровень 2. Напишите программу, которая по формуле строит ее производную.
Указание. По формуле построить дерево операций, по нему построить дерево операций для производной, далее построить формулу-производную.
Формат ввода: Формула, содержащая переменные, представленные строчными буквами латинского алфавита, константы от 0 до 9, знаки операций +, *, круглые скобки.
Формат вывода: Формула-производная.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Пусть задана формула /=(а*х+Ь)*(х-2), где х — переменная, а, Ь — константы. Этой формуле будет соответствовать дерево операций, изображенное на рисунке 23.
«лпиииЛе программу, ко&оршя па формуле с&роиЛ ее прои^Зо^Мро.
ставленные строчными буквами латинского алфавита, константы от 0 до 9, знаки операций +, *, -, круглые скобки.
Формат вывода: Упрощенная формула.
Дерево, соответствующее производной по х, представлено на рисунке 24. Уже на этом примере видно, что построенная формула может быть значительно упрощена, если выполнить некоторые очевидные действия. Рассмотрим, поддеревья, показанные на рисунке 25. Поддерево 1 может быть преобразовано в поддерево 2, поддерево 3 — в поддерево 4, поддерево 5 — в поддерево 6.
Следующая наша цель — выполнить описанные преобразования и, тем самым, сократить полученное дерево операций.
Уровень 1. Опишите алгоритм, позволяющий выполнять частичные вычисления для формул, представленных деревом операций и содержащих константы.
Уровень 2. На основе предложенного алгоритма напишите программу частичных упрощений формулы.
Формат ввода: Формула, содержащая переменные, пред-
Црилер. Ввод: (а+х)*1+Ь*0-0 Вывод:
Например, после выполнения действий с константами формула, о которой говорилось выше, будет упрощена, дерево операций, представляющее упрощенную формулу, изображено на рисунке 26.
Уровень 2. Задано логическое выражение, состоящее из переменных, круглых скобок, знаков логических операций «I» (или), «&» (и), «~» (отрицание), логических констант И (истина) и Л (ложь). Имя любой переменной задается одной латинской буквой. Вычисление выражения производится согласно приоритетам операций. Операция отрицания имеет наивысший приоритет, приоритет операции «&» выше приоритета операции «I». Требуется упростить выражение, произведя константные вычисления и удалив лишние скобки. Упрощения должны производиться согласно правилам, приведенным в таблице, через а обозначено произвольное выражение.
ОпмкшЯе ллгориЛм, гас&игяш ёшислеЛия
ЗарлЛо мхгигеасое ёирафеЛие.
Программа должна применять указанные правила к заданному выражению до тех пор, пока это возможно. Порядок применения правил может быть произвольным.
Формат ввода: Выражение, состоящее из строчных букв латинского алфавита, круглых скобок, знаков логических операций «I» (или), «&» (и), «~» (отрицание), логических констант И (истина) и Л (ложь).
Формат вывода: Упрощенное выражение.
Ввод: а & И & И I Ь
Мы рассмотрели бинарное дерево и алгоритмы работы с ним. Представленные нами алгоритмы анализировали, в основном, структуру дерева и, в меньшей мере, элементы, из которых дерево строилось.
Дерево поиска использовали для работы с данными, на которых задан порядок. Многие алгоритмы, описанные для бинарных деревьев, применимы и в случае деревьев поиска. Некоторые алгоритмы для дерева поиска были изменены. Поиск элемента в дереве поиска можно делать эффективнее, чем просто в бинарном дереве. Были добавлены новые алгоритмы, присущие только деревьям поиска: добавление элемента в дерево поиска, построение дерева поиска, поиск с включением и др.
Ми рассмотрели биЛарЛое фереёх и алгоритмы, рабо&и с Лим. ‘Иреус&.аёмеЯЯые Лами алгсри&ми аЛами^ираёами, ё осЛсёЛсм,
фереёа и, ё меЛымш мере, злемеЛ&и, ко&срш дереёёс с&роилсс-ъ.
Дерево операций использовалось для представления формул. Многие алгоритмы, описанные для бинарных деревьев, применимы и для деревьев операций, причем, для деревьев операций алгоритмы имеют свою интерпретацию. Например, поиск числа листьев в бинарном дереве можно трактовать как поиск операндов в дереве операций. Соответствующие обходы бинарных деревьев позволяют получать формулы в бесскобочной записи. Специфичными для деревьев операций являются алгоритмы: построение по формуле дерева операций, вывод формулы в инфиксной записи с необходимыми скобками, вычисление значения формулы, дифференцирование формулы, выполнение частичных преобразований и др.
Следуя технологии объектно-ориентированного программирования, можно создать объект «бинарное дерево», который является родителем двух других объек-
тов: «дерево поиска» и «дерево операций». Потомки наследуют методы родителя. При необходимости методы родителя могут быть переопределены. Каждый потомок может иметь свои собственные методы. Объектно-ориентированное программирование — отдельная интересная тема, а мы заметим лишь, что и отношения между объектами отображаются с помощью дерева, например, изображенного на рисунке 27.
1. Вирт Н. Алгоритмы+структуры данных=программы. М.: Мир, 1985, 392 с.
2. Дмитриева М.В., Кубенский А.А. Элементы современного программирования. СПб., 1991.
3. Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. М., 1993.
4. Дмитриева М.В., Кубенский А.А. Турбо Паскаль и Турбо Си: построение и обработка структур данных. СПб., 1996.
5. Касьянов В.Н., Сабельфельд В.К. Сборник задач по практикуму на ЭВМ. М., 1986.
6. Черкасова П.Г. Компьютер и графы. Компьютерные инструменты в образовании, № 6, 1999 г.
7. Дмитриева М.В., Поздняков С.Н. Формулы, формулы, формулы. Компьютерные инструменты в образовании, № 2, 2000 г.
Дмитриева Марина Валерьевна, доцент кафедры информатики Санкт-Петербургского государственного университета.