Простой пример неупорядоченного дерева
В информатике дерево - одна из наиболее широко распространённых структур данных, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Узлы[]
Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья 'растут' вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла - это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла (т.е. его корневому пути).
Корневые узлы[]
Самый верхний узел дерева называется корневым узлом. 'Быть самым верхним узлом' подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с "листов" и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, "растущего" из этого узла.
Листовые узлы[]
Узлы самого нижнего уровня дерева называются листовыми узлами или листьями. Так как они находятся на самом нижнем уровне, они не имеют никаких потомков.
Внутренние узлы[]
Внутренний узел - любой узел дерева, имеющий потомков, и таким образом не являющийся листовым узлом.
Поддеревья[]
Поддерево - часть деревообразной структуры данных, которая может быть представлено в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. Т.е. поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином "соответствующее подмножество").
Упорядочивание деревьев[]
Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска - одно из разновидностей упорядоченного дерева.
Представление деревьев[]
Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Деревья как графы[]
В теории графов дерево - связанный ациклический граф. Корневое дерево - это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения "родитель-потомок". Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.
Методы обхода[]
Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерева, а сам процесс называется обходом по дереву. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем - правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.
Общие операции[]
- Перебор всех элементов дерева
- Перебор ветви дерева
- Поиск элемента
- Вставка нового элемента в определённую позицию
- Удаление элемента
- Удаление ветви дерева (называется обрезкой)
- Добавление ветви дерева (называется прививкой)
- Нахождение корневого элемента для любого узла
Общее применение[]
- Управление иерархией данных
- Упрощение поиска информации (смотри обход дерева)
- Управление сортированными списками данных
- В качестве технологии компоновки цифровых картинок для получения различных визуальных эффектов
Смотри также[]
- Двоичное разбиение пространства
- Куча
- Дерево (теория графов)
- Дерево (теория наборов)
- Древовидная структура
- Префиксное дерево
- Экспоненциальное дерево
Распространённые древовидные структуры[]
- Двоичное дерево
Самобалансирующиеся двоичные деревья поиска[]
Самобалансирующиеся двоичные деревья поиска:
- АА-дерево
- АВЛ-дерево
- Красно-чёрное дерево
- Расширяющееся дерево
- Дерево со штрафами
Прочие деревья[]
- B-дерево (2-3 дерево, B+ дерево, B*-дерево, UB-дерево)
- DSW-алгоритм
- Пляшущее дерево
- Анфилада
- Смешанное дерево
- k-мерное дерево
- Октодерево
- Квадродерево
- R-дерево
- Дерево остатков
- Сегментное дерево
- Список с пропусками
- T-дерево
- T-пирамида
- Верхнее дерево
- Дерево ван Емде Боаса
Ссылки[]
- Дональд Кнут. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp.308–423.
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, and Клиффорд Штайн. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.