Jump to content

Дерево (структура данных)

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

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

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

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

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

Приложения

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

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

[ редактировать ]
Не дерево : две несвязанные части : A→B и C→D→E. Имеется более одного корня.
Не дерево : ненаправленный цикл 1-2-4-3. 4 имеет более одного родительского узла (входящий край).
Не дерево : цикл B→C→E→D→B. B имеет более одного родителя (входящее ребро).
Не дерево : цикл A→A. A — это корень, но у него также есть родительский элемент.
Каждый линейный список тривиально дерево .

Общие операции

[ редактировать ]
  • Перечисление всех предметов
  • Перечисление части дерева
  • Поиск предмета
  • Добавление нового элемента в определенную позицию дерева
  • Удаление элемента
  • Обрезка : удаление целой части дерева.
  • Прививка : добавление целой секции к дереву.
  • Нахождение корня для любого узла
  • Нахождение наименьшего общего предка двух узлов

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

[ редактировать ]

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

Представительства

[ редактировать ]

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

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

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

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

Теория типов

[ редактировать ]

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

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

с аксиомами:

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

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

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

[ редактировать ]

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

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

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

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

См. также

[ редактировать ]

Примечания

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

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 00b45ddab7c86b5ee031ed0d91bccfec__1720770180
URL1:https://arc.ask3.ru/arc/aa/00/ec/00b45ddab7c86b5ee031ed0d91bccfec.html
Заголовок, (Title) документа по адресу, URL1:
Tree (data structure) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)