.svg/1280px-Tree_(computer_science).svg.png)
В информатике дерево — это широко используемый абстрактный тип данных , представляющий собой иерархическую древовидную структуру с набором связанных узлов . Каждый узел в дереве может быть связан со многими дочерними узлами (в зависимости от типа дерева), но должен быть связан ровно с одним родителем, [1] за исключением корневого узла, у которого нет родителя (т. е. корневой узел как самый верхний узел в иерархии дерева). Эти ограничения означают, что нет никаких циклов или «петель» (ни один узел не может быть своим собственным предком), а также что каждый дочерний узел может рассматриваться как корневой узел своего собственного поддерева, что делает рекурсию полезным методом обхода дерева . В отличие от линейных структур данных , многие деревья не могут быть представлены отношениями между соседними узлами (родительскими и дочерними узлами рассматриваемого узла, если они существуют) на одной прямой линии (называемой ребром или связью между двумя соседними узлами).
Бинарные деревья — это часто используемый тип, который ограничивает число потомков для каждого родителя максимум двумя. Когда указан порядок потомков, эта структура данных соответствует упорядоченному дереву в теории графов . Значение или указатель на другие данные могут быть связаны с каждым узлом в дереве или иногда только с конечными узлами , которые не имеют дочерних узлов.
Абстрактный тип данных (ADT) может быть представлен несколькими способами, включая список родителей с указателями на детей, список детей с указателями на родителей или список узлов и отдельный список родительско-дочерних отношений (определенный тип списка смежности ). Представления также могут быть более сложными, например, с использованием индексов или списков предков для производительности.
Деревья, используемые в вычислениях, похожи, но могут отличаться от математических конструкций деревьев в теории графов , деревьев в теории множеств и деревьев в описательной теории множеств .
Деревья обычно используются для представления или обработки иерархических данных в таких приложениях, как:
Деревья можно использовать для представления и манипулирования различными математическими структурами, такими как:
Древовидные структуры часто используются для отображения взаимосвязей между вещами, например:
Документы JSON и YAML можно рассматривать как деревья, но обычно они представлены вложенными списками и словарями .
Узел — это структура, которая может содержать данные и соединения с другими узлами, иногда называемые ребрами или связями . Каждый узел в дереве имеет ноль или более дочерних узлов , которые находятся ниже его в дереве (по соглашению деревья рисуются с потомками , идущими вниз). Узел, у которого есть дочерний узел, называется родительским узлом дочернего узла (или вышестоящим ). Все узлы имеют ровно одного родителя, за исключением самого верхнего корневого узла , у которого их нет. Узел может иметь много предковых узлов , таких как родительский узел родителя. Дочерние узлы с одним и тем же родителем являются родственными узлами . Обычно родственные узлы имеют порядок, при этом первый из них традиционно рисуется слева. Некоторые определения позволяют дереву вообще не иметь узлов, в этом случае оно называется пустым .
Внутренний узел ( также известный как внутренний узел , inode для краткости или узел-ветвь ) — это любой узел дерева, имеющий дочерние узлы. Аналогично, внешний узел (также известный как внешний узел , листовой узел или конечный узел ) — это любой узел, не имеющий дочерних узлов.
Высота узла — это длина самого длинного нисходящего пути к листу от этого узла. Высота корня — это высота дерева. Глубина узла — это длина пути к его корню (т. е. его корневой путь ). Таким образом, корневой узел имеет глубину нулевую, листовые узлы имеют высоту нулевую, а дерево только с одним узлом (следовательно, и корень, и лист) имеет глубину и высоту нулевую. Традиционно пустое дерево (дерево без узлов, если таковые допускаются) имеет высоту −1.
Каждый некорневой узел можно рассматривать как корневой узел своего собственного поддерева , которое включает этот узел и всех его потомков. [a] [2]
Другие термины, используемые с деревьями:
Прохождение элементов дерева посредством связей между родителями и детьми называется обходом дерева , а действие — обходом дерева. Часто операция может быть выполнена, когда указатель достигает определенного узла. Обход, при котором каждый родительский узел обходит раньше своих детей, называется обходом в прямом порядке ; обход, при котором дети обходят раньше своих родителей, называется обходом в обратном порядке ; обход, при котором обходят левое поддерево узла, затем сам узел и, наконец, его правое поддерево, называется обходом в прямом порядке . (Этот последний сценарий, ссылающийся ровно на два поддерева, левое поддерево и правое поддерево, предполагает конкретно бинарное дерево .) Обход в порядке уровней эффективно выполняет поиск в ширину по всему дереву; Узлы обрабатываются уровень за уровнем, причем сначала посещается корневой узел, затем его прямые дочерние узлы и их братья, затем его внучатые узлы и их братья и сестры и т. д., пока не будут обработаны все узлы в дереве.
Существует множество различных способов представления деревьев. В рабочей памяти узлы обычно представляют собой динамически выделяемые записи с указателями на своих дочерних элементов, своих родителей или и то, и другое, а также любые связанные данные. Если узлы фиксированного размера, они могут храниться в списке. Узлы и связи между узлами могут храниться в отдельном специальном типе списка смежности . В реляционных базах данных узлы обычно представляются в виде строк таблицы с индексированными идентификаторами строк, упрощающими указатели между родителями и детьми.
Узлы также могут храниться как элементы в массиве , причем отношения между ними определяются их положением в массиве (как в двоичной куче ).
Бинарное дерево может быть реализовано как список списков: голова списка (значение первого члена) является левым потомком (поддеревом), а хвост (список второго и последующих членов) является правым потомком (поддеревом). Это можно изменить, чтобы разрешить также значения, как в Lisp S-выражениях , где голова (значение первого члена) является значением узла, голова хвоста (значение второго члена) является левым потомком, а хвост хвоста (список третьего и последующих членов) является правым потомком.
Упорядоченные деревья могут быть естественным образом закодированы конечными последовательностями, например, натуральными числами. [4]
В качестве абстрактного типа данных абстрактный тип дерева T со значениями некоторого типа E определяется с использованием абстрактного типа леса F (списка деревьев) с помощью функций:
с аксиомами:
С точки зрения теории типов дерево — это индуктивный тип , определяемый конструкторами nil (пустой лес) и node (дерево с корневым узлом с заданным значением и дочерними узлами).
Рассматриваемая в целом структура данных дерева представляет собой упорядоченное дерево , как правило, со значениями, прикрепленными к каждому узлу. Конкретно, это (если требуется, чтобы оно было непустым):
Часто деревья имеют фиксированный (точнее, ограниченный) фактор ветвления ( исходящую степень ), в частности, всегда имеют два дочерних узла (возможно, пустых, следовательно, максимум два непустых дочерних узла), отсюда «бинарное дерево».
Разрешение пустых деревьев делает некоторые определения проще, некоторые — сложнее: корневое дерево должно быть непустым, поэтому, если допускаются пустые деревья, приведенное выше определение становится «пустым деревом или корневым деревом, таким что ...». С другой стороны, пустые деревья упрощают определение фиксированного фактора ветвления: при разрешенных пустых деревьях бинарное дерево — это дерево, в котором каждый узел имеет ровно два дочерних элемента, каждый из которых является деревом (возможно, пустым).
Родитель может иметь несколько дочерних узлов. ... Однако дочерний узел не может иметь несколько родителей. Если дочерний узел имеет несколько родителей, то это то, что мы называем графом.
