Дерево (структура данных)
В информатике is tree (англ. Tree ) - это структура данных и абстрактный тип данных , который может быть сопоставлен с иерархическими структурами. Поскольку, с одной стороны, многие комбинаторные проблемы могут быть прослежены до деревьев или (в случае остовных деревьев ) являются результатами алгоритмов на графах (таких как поиск по широте или глубине ), деревья играют особую роль в информатике. Начиная с корня, несколько объектов одного типа могут быть связаны друг с другом, так что линейная структура списка разбивается и происходит ветвление. Поскольку деревья являются одной из наиболее часто используемых структур данных в информатике, существует множество специализаций.
Определения
Деревья могут быть определены разными способами, например Б.
- Дерево состоит из набора узлов и набора ребер , каждое из которых соединяет два узла. Конкретный узел дерева называется корнем . Каждый узел, за исключением корня, соединен ребром ровно с одним другим узлом, этот узел является родителем n. Уникальный путь проходит от корня до каждого узла. Если каждый узел в дереве имеет максимум два дочерних узла ( потомков ), дерево называется двоичным деревом .
- Дерево либо пусто, либо состоит из корня и 0 или более поддеревьев, каждое из которых также является деревом. Корень каждого поддерева соединен ребром с корнем родительского дерева. Это рекурсивное определение деревьев.
характеристики
Преимущество деревьев перед линейными структурами, такими как поля или списки, заключается в их эффективном доступе. Например, для полей поиск выполняется только в логарифмическом времени по сравнению с линейным временем (подробности см. В статье о двоичном поиске ). Преимущество деревьев как структуры данных по сравнению с сетевыми структурами заключается в небольшом количестве ребер (соединений), которые необходимо сохранять или учитывать. Количество ребер полного графа соответствует номеру треугольника . С другой стороны, количество ребер в дереве с одинаковым количеством узлов (объектов) составляет всего .
Деревья, как и другие структуры графа , могут храниться через список смежности или матрицу или через матрицу инцидентности .
терминология
В общем, все мыслимые термины заимствованы из теории графов . Объекты, указанные в иерархии, называются узлами . Обычно, начиная с первого узла, корня , каждый узел хранит список ссылок на его подчиненные узлы. Эти ссылки называются ребрами . Ребро соединяет два узла , чтобы указать , что они связаны между собой . Каждый узел, кроме корня, связан ровно одним входящим ребром от другого узла. Корень дерева - единственный узел в дереве, у которого нет входящих ребер. Каждый узел может иметь несколько исходящих ребер.
Это обычная практика , чтобы говорить о детях для дочерних узлов и родителя для ссылающегося узла . Набор узлов, которые имеют входящие ребра от одного и того же узла, называются дочерними узлами этого узла. Узел является родителем всех узлов, с которыми он связан исходящими ребрами. Узлы в дереве, которые являются потомками одного и того же родителя, называются одноуровневыми . Также используются другие имена, заимствованные из генеалогии . Если узел не имеет собственных дочерних элементов, он называется листом .
Термины корневые деревья особенно актуальны: корни этих деревьев четко определены. После того, как вы записали корень, в дополнение к терминам, которые у вас уже есть в теоретико-графовых деревьях, можно определить следующее: расстояние , поддерево , степень узла , изоморфизм : глубина узла указывает, сколько ребер он удален от корень. Корень имеет глубину 0. Узлы с одинаковой глубиной вместе образуют плоскость или уровень . Тогда высота дерева равна максимальной глубине узла.
Узел является фундаментальной частью дерева. У него может быть имя, называемое ключом . Узел также может содержать дополнительную информацию. Эта дополнительная информация называется полезной нагрузкой . Хотя полезная информация не является центральной для многих древовидных алгоритмов, она часто имеет решающее значение для приложений, использующих деревья.
Путь представляет собой упорядоченный список узлов , соединенных ребрами. Поддерево является когерентным множеством узлов и ребер , которые состоят из узла вышестоящего и всех потомков этого вышестоящего узла и который сами по себе образует дерево. Дочерние элементы каждого узла являются корнями поддерева.
Двоичное дерево
Важным частным случаем является двоичное дерево , в котором каждый узел может иметь не более двух дочерних элементов. В бинарных деревьях, например, количество дочерних элементов не превышает двух, а в деревьях со сбалансированной высотой также верно, что высоты левого и правого поддерева в каждом узле не слишком сильно различаются.
В случае упорядоченных деревьев, особенно деревьев поиска , элементы хранятся в древовидной структуре упорядоченным образом, так что элементы могут быть быстро найдены в дереве. Дальнейшее различие между здесь бинарных деревьев поиска с АВЛ деревьев , как сбалансированной версии и B деревьев и вариант, B * деревьев . Специализация B-деревьев - это снова 2-3-4-деревья , которые часто реализуются как красно-черные деревья .
Частным случаем деревьев AVL являются деревья Фибоначчи . В основном они используются в качестве крайних случаев и объектов сравнения при рассмотрении эффективности деревьев со сбалансированной высотой, особенно деревьев AVL.
Геометрические древовидные структуры, такие как R-дерево и его варианты , не сортируются, а «вложены» . Здесь ищутся только те поддеревья, которые перекрываются с запрошенной областью.
Хотя деревья многомерны по своей структуре, взаимосвязь объектов часто бывает однонаправленной. Объединение сохраненных объектов начинается в корне дерева и оттуда в направлении узлов дерева.
программирование
В следующем примере на языке программирования C # показана реализация неориентированного графа со списками смежности . Ненаправленный граф объявлен как класс UndirectedGraph . При выполнении программы используется метод Main , который выводит на консоль, является ли граф деревом.
using System;
using System.Collections.Generic;
using System.Linq;
// Deklariert die Klasse für die Knoten des Graphen
class Node
{
public int index;
public string value;
public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten
}
// Deklariert die Klasse für den ungerichteten Graphen
class UndirectedGraph
{
public HashSet<Node> nodes = new HashSet<Node>();
// Diese Methode verbindet die Knoten node1 und node2 miteinander.
public void ConnectNodes(Node node1, Node node2)
{
node1.adjacentNodes.Add(node2);
node2.adjacentNodes.Add(node1);
}
// Diese rekursive Methode prüft, ob der Graph Zyklen enthält
public bool IsCyclic(Node node, Dictionary<Node, bool> areConnected, Node parentNode)
{
areConnected[node] = true; // Setzt den aktuellen Knoten als durchlaufen
foreach (Node nextNode in node.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des aktuellen Knotens durchläuft
{
if (!areConnected[nextNode]) // Wenn der benachbarten Knoten noch nicht durchlaufen wurde
{
if (IsCyclic(nextNode, areConnected, node)) // Rekursiver Aufruf der Methode mit dem benachbarten Knoten als aktuellen Knoten
{
return true; // Wenn der rekursive Aufruf true zurückgibt
}
}
else // Wenn der benachbarten Knoten schon durchlaufen wurde ...
{
if (nextNode != parentNode) // ... und der benachbarte Knoten nicht der Elternknoten ist, bilden die durchlaufenen Knoten einen Zyklus
{
return true;
}
}
}
return false; // Sonst enthält der Graph keinen Zyklus
}
// Diese Methode prüft, ob der Graph ein Baum ist.
public bool IsTree()
{
Dictionary<Node, bool> areConnected = new Dictionary<Node, bool>();
foreach (Node node in nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
{
areConnected.Add(node, false); // Setzt alle Knoten als nicht durchlaufen
}
if (IsCyclic(nodes.ElementAt(0), areConnected, null)) // Wenn die Komponente mit dem ersten Knoten Zyklen enthält, false zurückgeben
{
return false;
}
foreach (Node node in nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
{
if (!areConnected[node]) // Wenn ein Knoten nicht verbunden ist, dann false zurückgeben
{
return false;
}
}
return true; // Sonst ist der Graph ein Baum
}
}
class Program
{
// Hauptmethode, die das Programm ausführt
public static void Main(string[] args)
{
// Deklariert und initialisiert 5 Knoten
Node node1 = new Node{index = 0, value = "A"};
Node node2 = new Node{index = 1, value = "B"};
Node node3 = new Node{index = 2, value = "C"};
Node node4 = new Node{index = 3, value = "D"};
Node node5 = new Node{index = 4, value = "E"};
// Deklariert und initialisiert ein Array mit den Knoten
Node[] nodes = {node1, node2, node3, node4, node5};
// Erzeugt einen ungerichteten Graphen
UndirectedGraph undirectedGraph = new UndirectedGraph();
int numberOfNodes = nodes.Length;
for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
{
undirectedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu
}
// Verbindet Knoten des Graphen miteinander
undirectedGraph.ConnectNodes(node2, node1);
undirectedGraph.ConnectNodes(node1, node3);
undirectedGraph.ConnectNodes(node1, node4);
undirectedGraph.ConnectNodes(node4, node5);
if (undirectedGraph.IsTree()) // Aufruf der Methode, die prüft, ob der Graph ein Baum ist
{
Console.WriteLine("Der Graph ist ein Baum."); // Ausgabe auf der Konsole
}
else
{
Console.WriteLine("Der Graph ist kein Baum."); // Ausgabe auf der Konsole
}
Console.ReadLine();
}
}
Смотри тоже
- Поле (тип данных)
- Список (структура данных)
- Количество (структура данных)
- Хранение стека
- Очередь (структура данных)
Индивидуальные доказательства
- ^ Runestone Interactive LLC: Словарь и определения
- ↑ GeeksforGeeks: Проверьте, является ли данный граф деревом или нет
литература
- Хартмут Эрнст, Йохен Шмидт, Герд Бенекен: Базовый курс информатики. Основы и концепции успешной ИТ-практики - всестороннее практическое введение , 5-е издание, Springer, Wiesbaden 2015, стр. 523-596
- Хайнц-Петер Гумм, Манфред Зоммер: Введение в информатику , 10-е издание, Ольденбург, Мюнхен, 2013 г., стр. 372–398