Структуры данных. Деревья

Аннотация

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

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

Что такое деревья?

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

В некоторых книгах, посвященным разработке алгоритмов, деревья определяются рекурсивно. Дерево является либо пустым, либо состоит из узла (корня), являющегося родительским узлом для некоторого количества деревьев (это количество определяет арность дерева) [1, 2].

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

На рисунке 1 приведен пример произвольного двоичного дерева, состоящего из 5 узлов. Дерево, с корнем в узле «1» состоит из двух поддеревьев – левого, также представляющего собой дерево с двумя поддеревьями, и правого, являющегося листом.

Рис. 1 пример двоичного дерева

Рис. 1 пример двоичного дерева

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

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

Зачем нужны деревья?

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

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

  • при разработке парсеров или трансляторов полезным может оказаться дерево синтаксического разбора (синтаксическое дерево) [ 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.г, 2.д) необходимо учитывать в каком поддереве (левом или правом) расположен удаляемый узел.

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

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

Заключение:

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

Список использованных источников:

  1. Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.
  2. Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.
  3. Судоплатов С. В., Овчинникова Е. В. Дискретная математика.: Учебник. 2-е изд., перераб. — М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2007. — 256с.
  4. Макоха А.Н., Сахнюк П.А., Червяков Н.И. Дискретная математика: Учебное пособие. – М.: ФИЗМАТЛИТ, 2005. — 368 с.
  5. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект, 2001. – 352 с.
  6. Кормен Т. и др. Алгоритмы: построение и анализ, М.: МЦНМО, 2002.
  7. Вставская Е. Структуры данных: деревья, [Электронный ресурс] – режим доступа: https://prog-cpp.ru/data-tree/. Дата обращения: 25.05.2014.

Добавить комментарий