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