Структуры_данных_дерево_лес

3. Деревья

Полезной нелинейной структурой данных является дерево (или лес).

3.1. Определения дерева, леса, бинарного дерева. Скобочное представление

Дадим формальное определение дерева, следуя [10].

Дерево – конечное множество Т, состоящее из одного или более узлов, таких, что

а) имеется один специально обозначенный узел, называемый корнем данного дерева;

б) остальные узлы (исключая корень) содержатся в m  0 попарно не пересекающихся множествах Т₁, Т₂, . Т_m, каждое из которых, в свою очередь, является деревом. Деревья Т₁, Т₂, . Т_m называются поддеревьями данного дерева.

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

Каждый узел дерева является корнем некоторого поддерева. В том случае, когда множество поддеревьев такого корня пусто, этот узел называется концевым узлом, или листом. Уровень узла определяется рекурсивно следующим образом: 1) корень имеет уровень 1; 2) другие узлы имеют уровень, на единицу больший их уровня в содержащем их поддереве этого корня. Используя для уровня узла а дерева T обозначение уровень (a, T), можно записать это определение в виде

где T_i – поддерево корня дерева T, такое, что a  T_i.

Говорят, что каждый корень является отцом корней своих поддеревьев и что последние являются сыновьями своего отца и братьями между собой. Говорят также, что узел n – предок узла m (а узел m – потомок узла n), если n – либо отец m, либо отец некоторого предка m.

Если в определении дерева существен порядок перечисления поддеревьев Т₁, Т₂, . Т_m, то дерево называют упорядоченным и говорят о «первом» (Т₁), «втором» (Т₂) и т. д. поддеревьях данного корня. Далее будем считать, что все рассматриваемые деревья являются упорядоченными, если явно не оговорено противное. Отметим также, что в терминологии теории графов определенное ранее упорядоченное дерево более полно называлось бы «конечным ориентированным (корневым) упорядоченным деревом».

Лес – это множество (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев. Используя понятие леса, пункт б в определении дерева можно было бы сформулировать так: узлы дерева, за исключением корня, образуют лес.

Традиционно дерево изображают графически, например так, как на рис. 3.1.

Error: Reference source not foundРис. 3.1. Графическое изображение дерева

В графическом представлении для изображения структуры дерева используется двухмерность рисунка. При машинной обработке часто удобнее использовать текстовое представление дерева. Например, таким представлением может быть так называемый уступчатый список. Здесь «двухмерность» проявляется за счет того, что текст разбит на строки и фиксируется позиция символа узла в строке. На рис. 3.2, а, б представлено в виде уступчатого списка дерево, изображенное на рис. 3.1.

Другой вид текстового (и принципиально одномерного) представления дерева  это так называемая скобочная запись (ср. с записью иерархических списков в 1.7). Определим скобочное представление дерева и леса:

a ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ а b i b ▓▓▓▓▓▓▓▓▓▓▓▓▓▓

i ▓▓▓▓▓▓▓▓▓▓ j j ▓▓▓▓▓▓▓▓▓▓ c ▓▓▓▓▓▓▓▓▓▓▓▓▓▓ c h h ▓▓▓▓▓▓▓▓▓▓ d ▓▓▓▓▓▓▓▓▓▓▓▓▓▓ d e e ▓▓▓▓▓▓▓▓▓▓ f ▓▓▓▓▓▓▓▓▓▓ f k k ▓▓▓▓▓▓▓ g ▓▓▓▓▓▓▓▓▓▓ g

Рис. 3.2. Представление дерева: а – в виде уступчатого списка; б – в виде «упрощенного» уступчатого списка

В скобочном представлении дерево, изображенное на рис. 3.1, запишется как

(a (b (i) (j)) (c (h)) (d (e) (f (k)) (g))).

Наиболее важным типом деревьев являются бинарные деревья. Удобно дать следующее формальное определение. Бинарное дерево  конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев, называемых правым поддеревом и левым поддеревом. Так определенное бинарное дерево не является частным случаем дерева. Например, бинарные деревья, изображенные на рис. 3.3, различны между собой, так как в одном случае корень имеет пустое правое поддерево, а в другом случае правое поддерево непусто. Если же их рассматривать как деревья, то они идентичны.

Рис. 3.3. Бинарные деревья из двух узлов

Определим скобочное представление бинарного дерева (БД):

Здесь пустое дерево имеет специальное обозначение  .

Например, бинарное дерево, изображенное на рис. 3.4, имеет скобочное представление

(a (b (d Λ (h Λ Λ)) (e Λ Λ)) (c (f (i Λ Λ) (j Λ Λ)) (g Λ (k (l Λ Λ) Λ)))).

Error: Reference source not foundError: Reference source not foundРис. 3.4. Бинарное дерево

Можно упростить скобочную запись бинарного дерева, исключив «лишние» знаки  по правилам:

Тогда, например, скобочная запись бинарного дерева, изображенного на рис. 3.4, будет иметь вид

(a (b (d  (h) (e)) (c (f (i) (j)) (g  (k (l))))).

Источник

3.2. Деревья и леса

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

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

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

3.2.1. Определения

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

Особый вид иерархических структур — бинарные деревья — будут рассмотрены отдельно.

Формально дерево можно рекурсивно определить следующим образом[8].

Дерево (tree) — конечное множество T одного или более узлов (nodes) со следующими свойствами:

1. Существует один выделенный узел, называемый корнем (root) этого дерева T. Дерево может состоять и из одного корня.
2. Остальные узлы (если они есть) распределены среди k непересекающихся множеств T1, Т2, . Tk, и каждое их этих множеств, в свою очередь, является деревом. Деревья T1, Т2, . Tk называются поддеревьями (subtrees) этого корня.

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

Совокупность нескольких непересекающихся деревьев называется лесом (forest —иногда переводится как бор). Например, все потомки одного узла дерева образуют лес. Лес всегда можно преобразовать в дерево, добавив один единственный корневой элемент и связав его с корнями всех деревьев, из которых состоит лес. Поэтому лес и дерево — это два неразрывно сязанных понятия. Для того, чтобы подчеркнуть общность этих понятий, лес из n деревьев иногда называют деревом с n-кратным корнем.

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

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

Рис.3.2. Графическое изображение дерева

Традиционно деревья изображают графически, располагая корень вверху (т. е. дерево растет вниз), как показано на рис. 3.2. Очевидно, такое представление связано с тем, что человеку привычнее рисовать и читать рисунок сверху вниз. Узлы дерева обычно изображают с помощью окружностей, соединяя каждый узел с его сыновьями линиями (связями). Связи обычно изображают без стрелки на конце.

Другим представлением может быть так называемый уступчатый список. На рис.3.3,а,б так представлено дерево из рис.3.2.

Рис.3.3. Представление дерева: а – в виде уступчатого списка; б – в виде “упрощенного”уступчатого списка

Здесь двухмерность рисунка поддерживается посредством отступов.

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

1.a, 1.1.b, 1.1.1.i, 1.1.2.j, 1.2.c, 1.2.1.h,

Другой вид одномерного представления дерева — это так называемая скобочная запись, в которой отношения иерархии представляются с помощью вложенности скобок. Один из возможных вариантов скобочной записи [8] для дерева (рис.3.2) выглядит так:

Можно немного сократить количество скобок:

a ( b ( i, j ), c ( h ), d ( e, f ( k ), g ) )

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

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

Например, представим дерево из рис. 3.2. в виде таблицы, содержащей для каждого узла обозначение его родителя. Для экономии места расположим таблицу горизонтально, хотя логичнее представить дерево в виде таблицы из двух столбцов— «узел»-«его родитель».

Предствление дерева из рис. 3.2 с помощью ссылок на родителей

Источник

Деревья

Дерево — это нелинейная иерархическая структура данных. Она состоит из узлов и ребер, которые соединяют узлы.

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

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

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

Части дерева

• Узел — это объект, в котором есть ключ или значение и указатели на дочерние узлы.
  Узлы, у которых нет дочерних узлов, называют листами или терминальными узлами.
  Узлы, у которых есть хотя бы один дочерний узел, называются внутренними.
• Ребро связывает два узла.
• Корень — это самый верхний узел дерева. Его ещё иногда называют корневым узлом.

Другие понятия

• Высота узла — это максимальная длина пути от этого узла к самому нижнему узлу (листу).
• Глубина вложенности узла — длина пути от корня до этого узла.
• Высота дерева — это высота корневого узла или глубина самого глубокого узла.
• Степень узла — это общее количество ребер, которые соединены с этим узлом.

• Лес — множество непересекающихся деревьев. Например, если «срезать» корень, получится лес.

Виды деревьев

Обход дерева

Чтобы выполнить какую-либо операцию с деревом, нужно добраться до определенного узла. Для этого и существуют алгоритмы обхода дерева. Они помогают «дойти» до необходимого узла.

Где используются

• Деревья двоичного поиска помогают быстро проверить наличие элемента в наборе.
• Куча — это тоже своеобразное дерево. Кучи используют в алгоритме сортировки кучей.
• Префиксные деревья используются в маршрутизаторах, они хранят информацию о маршруте.
• Большинство популярных баз данных основаны на B-деревья и T-деревья.
• Компиляторы используют абстрактное синтаксическое дерево, чтобы находить синтаксические ошибки в ваших программах.

СodeСhick.io — простой и эффективный способ изучения программирования.

2023 © ООО «Алгоритмы и практика»

Источник