Нелинейные_структуры_данных_лес

AlgStr / Библиотека / ЛЕКЦИИ / POSIBNIK / Нелинейные структуры данных

К нелинейным структурам относятся многоуровневые списки, деревья, сети. Среди нелинейных структур данных наиболее важными являются деревья, поэтому начнем рассмотрение нелинейных С.Д. с деревьев. Понятие деревьев естественно возникает при попытке классифицировать или структурировать какое – то подмножество объектов. Деревья очень важны при хранении информации. Теперь дадим определение дереву. Деревом называется конечное множество Т, состоящее из одного или более узлов, таких, что имеется один специально выделенный узел, называемый корнем этого дерева и остальные узлы (исключая корень) содержатся в m>=0 попарно непересекающихся множествах Т₁, Т₂, Т₃,…..Т_m, каждое из которых в свою очередь является деревом. Деревья Т₁, Т₂, Т₃,…..Т_m называются поддеревьями данного корня. Это рекурсивное определение непустого дерева. Рекурсивность является естественной характеристикой деревьев как в информатике так ив природе. При работе с деревьями используется своя терминология. Степень узла – кол-во поддеревьев. Степень дерева – мах степень узлов. Концевой узел (лист) – узел нулевой степени. Регулярное дерево – все узлы разветвления имеют одну и ту же степень. Пустое дерево также будем считать деревом и обозначать его NIL. Высотой дерева называется мах уровень узла –1, т.е. мах разность уровней. Если имеет значение относительный порядок поддеревьев, то дерево называется упорядоченным. Если порядок расположения поддеревьев данного узла не существенен, то дерево ориентированное, иначе – упорядоченное. Упорядоченные деревья, в которых для каждого узла м.б. 0,1,2 сына называется бинарным. Изображение деревьев. Существует много способов представления деревьев. Приведем самые распространенные.

5)ABD.E..CF.GK..I… Такое изображение удобно при вводе из внешних носителей. Здесь точка ставится когда закончилось поддерево какого – то уровня. 6)Использование индексации F-дерево; F[1]-первое поддерево; F[1][1]-первое поддерево первого поддерева. Представление дерева. 1)На базе массива или вектора. Это так называемое сплошное представление. Здесь удобно описывать плотные статические деревья (не имеющие внутри никаких пробелов). В случае, когда все же есть пустоты, то на место пустот в массиве ставится признак пустоты, но тогда теряется преимущество в экономии памяти. 2)Ссылочное представление. здесь возможны 2 варианта а)ссылка – относительный адрес б)ссылка – абсолютный адрес. Предположим, что мы имеем дерево

При описании обходов будем ссылаться на него, как на пример. Под обходом будем понимать обработку всех элементов дерева. Классифицируем обходы бинарных деревьев. 1)Левосторонний (инфиксный, обратный, симметричный).Сначала обходим левое поддерево, затем корень и правое поддерево. В нашем случае 2-10-5-1-6-3-7. 2)Правосторонний (инфиксный, обратный, симметричный). В нашем случае 7-3-6-1-5-10-2. 3)Прямой обход (обход в глубину сверху вниз или префиксный). В нашем случае 1-2-5-10-3-6-7 либо при обходе справа 1-3-7-6-2-5-10. 4)Концевой (обход снизу или постфиксный) 10-5-2-6-7-3-1 либо при обходе справа 7-6-3-10-5-2-1. 5)Горизонтальный обход. В нашем случае 1-2-3-5-6-7-10. Рассмотрим еще оду нелинейных структур данных – сеть. Введем понятие сети. Имеется сеть мелких объектов (узлов) и они соединены между собой дугами – это и есть С.Д. сеть. В математике сеть принято представлять как граф. Граф =, где V – множество узлов, E – множество дуг = V*V. Граф может быть ориентированным и не ориентированным. Это ориентированный граф, если любому ребру l=(v,w) в графе есть ребро l’=(w,v). Если эти пары считать за одну, то такой граф принято называть неориентированным. Представление графов (сетей). 1)Матрицы смежности. 2)Списки смежности. Под обходом, как и ранее, будем понимать обработку всех элементов графа. Существует два основных способа обхода графа. 1)Обход в глубину. 2)Обход в ширину. Оба способа ориентированы на то, чтобы сначала обходить близкие вершины, а потом уже дальше.

Источник

Нелинейные структуры данных. Графы. Реализация.

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

– Матрица смежности – это двумерный массив размером n×n. Пространственная сложность этого способа V(n)~O(n2). Способ очень хорош, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

– Матрица инцидентности – это двумерный массив размером n×m.

Пространственная сложность этого способа V(n, m)~O(n×m). Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».

– Списки смежных вершин – это одномерный массив размером n, содержащий для каждой вершины указатели на списки смежных с ней вершин.

Пространственная сложность этого способа Vmax(n)~O(n2). Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин, смежных с x».

– Список ребер – это одномерный массив размером m, содержащий список пар вершин, инцидентных с одним ребром графа.

Пространственная сложность этого способа V(m)~O(m). Этот способ хранения графа особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.

Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

Нелинейные структуры данных. Деревья. Общие понятия.

Деревом называется орграф, для которого:

1) существует узел, в который не входит ни одной дуги (корень);

2) в каждую вершину, кроме корня, входит одна дуга.

Вершины дерева подразделяют на следующие три группы:

– корень – вершина, в которую не входит ни одной дуги;

– узлы – вершины, в которые входит одна дуга и выходит одна или более дуг;

– листья – вершины, в которые входит одна дуга и не выходит ни одной дуги.

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

Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – потомки потомков корня и т. д.

Поддеревом называется вершина со всеми ее потомками.

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

По величине степени дерева часто различают два типа деревьев:

– двоичные – степень дерева не более двух;

– сильноветвящиеся – степень дерева произвольная.

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

Существует несколько способов обхода (просмотра) всех вершин дерева. Три наиболее часто используемых способа обхода называются:

– в симметричном (внутреннем) порядке.

Все три способа обхода рекурсивно можно определить следующим образом:

1) если дерево Tree является пустым деревом, то в список обхода заносится пустая запись;

2) если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;

3) если Tree – дерево с корнем n и поддеревьями Tree1, Tree2, …, Treek, то:

– при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева Tree1, далее в прямом порядке вершины поддерева Tree2 и т. д. Последними в прямом порядке посещаются вершины поддерева Treek;

– при прохождении в обратном порядке сначала посещаются в обратном порядке вершины поддерева Tree1, далее последовательно в обратном порядке посещаются вершины поддеревьев Tree2, …, Treek. Последним посещается корень n;

– при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева Tree1, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев Tree2,…, Treek.

Источник

Деревья

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

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

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

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

Части дерева

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

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

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

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

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

Обход дерева

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

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

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

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

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

Источник