Что такое дерево в программировании
Перейти к содержимому

Что такое дерево в программировании

  • автор:

Деревья как концепция — Алгоритмы на деревьях

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

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

Что такое деревья и для чего они нужны

Деревья используют, чтобы отразить в памяти компьютера иерархические взаимосвязи. Их применяют для реестра 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 = value
parent = $parent; $this->value = $value; > >

Чтобы организовать из узла дерево, нужно добавить методы, которые заполняют ссылки на поддеревья child1 и child2 . Как реализуются деревья в коде, разберем подробно в следующих уроках.

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

Дерево как структура данных

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

Основные термины

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

Дерево как структура данных

Каждый элемент — это вершина или узел дерева. Узлы, соединенные направленными дугами, называются ветвями. Начальный узел — это корень дерева (корневой узел). Листья — это узлы, в которые входит 1 ветвь, причем не выходит ни одной.

Общую терминологию можно посмотреть на левой и правой части картинки ниже:

Дерево как структура данных

Какие свойства есть у каждого древа:

— существует узел, в который не входит ни одна ветвь;

— в каждый узел, кроме корневого узла, входит 1 ветвь.

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

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

Ниже изображен графический вывод древа с 4-мя уровнями (дерево имеет глубину, равную четырем):

Дерево как структура данных

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

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

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

— двоичные (степень не больше двух);

— сильноветвящиеся (степень больше двух).

Деревья — это рекурсивные структуры, ведь каждое поддерево тоже является деревом. Каждый элемент такой рекурсивной структуры является или пустой структурой, или компонентом, с которым связано конечное количество поддеревьев.

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

Обход древа

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

В процессе обхода все узлы должны посещаться в некотором, заранее определенном порядке. Есть ряд способов обхода, вот три основные:

— прямой (префиксный, preorder);

— симметричный (инфиксный, inorder);

— обратный (постфиксный, postorder).

Существует много древовидных структур данных: двоичные (бинарные), красно-черные, В-деревья, матричные, смешанные и пр. Поговорим о бинарных.

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

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

Дерево как структура данных

У бинарного древа каждый текущий узел — это структура, которая состоит из 4-х видов полей. Какие это поля:

— информационное (ключ вершины);

— служебное (включена вспомогательная информация, однако таких полей может быть несколько, а может и не быть вовсе);

— указатель на правое поддерево;

— указатель на левое поддерево.

Самый удобный вид бинарного древа — бинарное дерево поиска.

Что значит древо в контексте программирования?

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

В каких случаях древовидные структуры могут быть полезны при программировании:

Дерево как структура данных

  1. Когда данная иерархия существует в предметной области разрабатываемой программы. К примеру, программа должна обрабатывать генеалогическое древо либо работать со структурой каталогов. В таких ситуациях иногда есть смысл сохранять между объектами программы существующие иерархические отношения. В качестве примера можно вывести древо каталогов операционной системы UNIX:
  • Когда между объектами, которые обрабатывает программа, отношения иерархии не заданы явно, но их можно задать, что сделает обработку данных удобнее. Как тут не вспомнить разработку парсеров либо трансляторов, где весьма полезным может быть древо синтаксического разбора?
  • А сейчас очевидная вещь: поиск объектов более эффективен, когда объекты упорядочены, будь то те же базы данных. К примеру, поиск значения в неструктурированном наборе из тысячи элементов потребует до тысячи операций, тогда как в упорядоченном наборе может хватить всего дюжины. Вывод прост: раз иерархия — эффективный способ упорядочивания объектов, почему же не использовать древовидную иерархию для ускорения поиска узлов со значениями? Так и происходит: если вспомнить бинарные деревья, то на практике их можно применять в следующих целях:

— поиск данных в базах данных (специально построенных деревьях);

— сортировка и вывод данных;

— вычисления арифметических выражений;

— кодирование по методу Хаффмана и пр.

Деревья поиска

Дерево — одна из наиболее распространенных структур данных в программировании.

Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.

  • Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
  • Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
  • Предки — родители родителей, их родители, и так далее.
  • Потомки — дети детей, их дети, и так далее.
  • Лист (терминальная вершина) — вершина, не имеющая детей.
  • Поддерево — вершина дерева вместе со всеми её потомками.
  • Степень вершины — количество её детей.
  • Глубина вершины — расстояние от корня до неё.
  • Высота дерева — максимальная из глубин всех вершин.

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

Деревья также используются в контексте графов.

Бинарные деревья поиска

Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:

  • У каждой вершины не более двух детей.
  • Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
  • У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
  • У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
  • Оба поддерева — левое и правое — являются двоичными деревьями поиска.

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

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

Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:
Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.

Что такое дерево в программировании

Наиболее простой и понятной структурой данных является обычный массив. С тем, как устроены массивы, редко возникают вопросы. Чего нельзя сказать о такой структуре данных, как деревья. Предлагаем разобраться с деревьями — нелинейной структурой, где данные упорядочиваются иерархически.

Немного об иерархии

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

Приложив чуточку воображения в этой картинке действительно можно увидеть перевёрнутое дерево.

Пример каталога

Как же устроены деревья?

Рассмотрим основные элементы дерева на примере картинки выше.

Дерево представляет собой набор объектов, называемых узлами. Каждый узел содержит значение или данные, и он может иметь или не иметь дочерний узел. Узлы, у которых нет дочерних узлов называются листьями.

На картинке узлами являются все представленные папки, при этом листьями являются только те, внутри которых нет папок, например «lib», «disc», «mail», «X11» и т. п.

Все узлы деревьев соединены рёбрами, рёбра показывают связи между узлами.

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

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

В нашем случае корнем является каталог «/».

Основные элементы дерева

Может возникнуть вопрос, почему же корень находится на вершине? Ответ прост: мы – программисты, мы так видим ��

Характеристики дерева

Есть две важные характеристики дерева, которые нужно знать при работе с ним:

  1. Высота дерева.
  2. Глубина узла.
Высота дерева – это длина самого длинного пути к листу. Глубина узла – это расстояние от узла до его корня.

Для дерева, представленного выше, высота дерева будет равняться трём. Глубина узла, например «local» будет равняться двум.

В чём преимущество деревьев?

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

А что вообще делать с деревьями?

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

Ещё больше полезностей о деревьях мы расскажем в наших следующих статьях!

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *