stringtranslate.com

Дерево (абстрактный тип данных)

Это несортированное дерево имеет неуникальные значения (например, значение 2 существует в разных узлах, а не только в одном узле) и является небинарным (только до двух дочерних узлов на родительский узел в бинарном дереве). Корневой узел наверху (со значением 2 здесь) не имеет родителя, поскольку он является самым высоким в иерархии дерева.

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

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

Абстрактный тип данных (ADT) может быть представлен несколькими способами, включая список родителей с указателями на детей, список детей с указателями на родителей или список узлов и отдельный список родительско-дочерних отношений (определенный тип списка смежности ). Представления также могут быть более сложными, например, с использованием индексов или списков предков для производительности.

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

Приложения

Деревья обычно используются для представления или обработки иерархических данных в таких приложениях, как:

Деревья можно использовать для представления и манипулирования различными математическими структурами, такими как:

Древовидные структуры часто используются для отображения взаимосвязей между вещами, например:

Документы JSON и YAML можно рассматривать как деревья, но обычно они представлены вложенными списками и словарями .

Терминология

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

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

Высота узла — это длина самого длинного нисходящего пути к листу от этого узла. Высота корня — это высота дерева. Глубина узла — это длина пути к его корню (т. е. его корневой путь ). Таким образом, корневой узел имеет глубину нулевую, листовые узлы имеют высоту нулевую, а дерево только с одним узлом (следовательно, и корень, и лист) имеет глубину и высоту нулевую. Традиционно пустое дерево (дерево без узлов, если таковые допускаются) имеет высоту −1.

Каждый некорневой узел можно рассматривать как корневой узел своего собственного поддерева , которое включает этот узел и всех его потомков. [a] [2]

Другие термины, используемые с деревьями:

Сосед
Родитель или ребенок.
Предок
Узел, достижимый путем повторного перехода от дочернего узла к родительскому.
Потомок
Узел, достижимый путем повторного перехода от родителя к потомку. Также известен как подребенок .
Степень
Для данного узла, его количество потомков. Лист, по определению, имеет нулевую степень.
Степень дерева
Степень дерева — это максимальная степень узла в дереве.
Расстояние
Количество ребер на кратчайшем пути между двумя узлами.
Уровень
Уровень узла — это количество ребер вдоль уникального пути между ним и корневым узлом. [3] Это то же самое, что и глубина.
Ширина
Количество узлов на уровне.
Ширина
Количество листьев.
Лес
Набор из одного или нескольких непересекающихся деревьев.
Упорядоченное дерево
Корневое дерево, в котором указан порядок для потомков каждой вершины.
Размер дерева
Количество узлов в дереве.

Примеры деревьев и не-деревьев

Обычные операции

Методы обхода и поиска

Прохождение элементов дерева посредством связей между родителями и детьми называется обходом дерева , а действие — обходом дерева. Часто операция может быть выполнена, когда указатель достигает определенного узла. Обход, при котором каждый родительский узел обходит раньше своих детей, называется обходом в прямом порядке ; обход, при котором дети обходят раньше своих родителей, называется обходом в обратном порядке ; обход, при котором обходят левое поддерево узла, затем сам узел и, наконец, его правое поддерево, называется обходом в прямом порядке . (Этот последний сценарий, ссылающийся ровно на два поддерева, левое поддерево и правое поддерево, предполагает конкретно бинарное дерево .) Обход в порядке уровней эффективно выполняет поиск в ширину по всему дереву; Узлы обрабатываются уровень за уровнем, причем сначала посещается корневой узел, затем его прямые дочерние узлы и их братья, затем его внучатые узлы и их братья и сестры и т. д., пока не будут обработаны все узлы в дереве.

Представления

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

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

Бинарное дерево может быть реализовано как список списков: голова списка (значение первого члена) является левым потомком (поддеревом), а хвост (список второго и последующих членов) является правым потомком (поддеревом). Это можно изменить, чтобы разрешить также значения, как в Lisp S-выражениях , где голова (значение первого члена) является значением узла, голова хвоста (значение второго члена) является левым потомком, а хвост хвоста (список третьего и последующих членов) является правым потомком.

Упорядоченные деревья могут быть естественным образом закодированы конечными последовательностями, например, натуральными числами. [4]

Теория типов

В качестве абстрактного типа данных абстрактный тип дерева T со значениями некоторого типа E определяется с использованием абстрактного типа леса F (списка деревьев) с помощью функций:

значение: ТЕ
дети: ТЖ
ноль: () → F
узел: E × FT

с аксиомами:

значение(узел( е , f )) = е
дети(узел( е , f )) = f

С точки зрения теории типов дерево — это индуктивный тип , определяемый конструкторами nil (пустой лес) и node (дерево с корневым узлом с заданным значением и дочерними узлами).

Математическая терминология

Рассматриваемая в целом структура данных дерева представляет собой упорядоченное дерево , как правило, со значениями, прикрепленными к каждому узлу. Конкретно, это (если требуется, чтобы оно было непустым):

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

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

Смотрите также

Примечания

  1. ^ Это отличается от формального определения поддерева, используемого в теории графов, которое является подграфом, образующим дерево – он не обязательно должен включать всех потомков. Например, корневой узел сам по себе является поддеревом в смысле теории графов, но не в смысле структуры данных (если только нет потомков).

Ссылки

  1. ^ Subero, Armstrong (2020). "3. Структура данных дерева". Codeless Data Structures and Algorithms . Berkeley, CA: Apress. doi :10.1007/978-1-4842-5725-8. ISBN 978-1-4842-5724-1. Родитель может иметь несколько дочерних узлов. ... Однако дочерний узел не может иметь несколько родителей. Если дочерний узел имеет несколько родителей, то это то, что мы называем графом.
  2. ^ Вайсштейн, Эрик В. «Поддерево». MathWorld .
  3. ^ Сюзанна С. Эпп (август 2010 г.). Дискретная математика с приложениями. Пасифик-Гроув, Калифорния: Brooks/Cole Publishing Co. стр. 694. ISBN 978-0-495-39132-6.
  4. ^ Л. Афанасьев; П. Блэкберн; И. Димитриу; Б. Гайфф; Э. Горис; М. Маркс; М. де Рейке (2005). «PDL для упорядоченных деревьев» (PDF) . Журнал прикладной неклассической логики . 15 (2): 115–135. дои : 10.3166/jancl.15.115-135. S2CID  1979330.
  5. ^ Левин, Оскар. Дискретная математика: открытое введение (3-е изд.). С. 247. ISBN 978-1792901690.

Дальнейшее чтение

Внешние ссылки