4194
правки
Дерево: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Дерево'''([[Tree|Tree]]) | '''Дерево'''([[Tree|Tree]]) — [[связный граф|связный граф]] без циклов. Чаще всего этот термин используется как краткая форма термина [[корневое дерево|''корневое дерево'']], т.е. конечное множество одной или нескольких [[вершина|вершин]] таких, что, во-первых, среди них | ||
существует только одна особая вершина, называемая ''корнем'', и, | существует только одна особая вершина, называемая ''корнем'', и, | ||
во-вторых, остальные вершины делятся на <math>d</math> непересекающихся множеств | во-вторых, остальные вершины делятся на <math>d</math> непересекающихся множеств | ||
| Строка 5: | Строка 5: | ||
деревом. Множества | деревом. Множества | ||
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченное дерево|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким | <math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченное дерево|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким | ||
образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево | образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево — это [[бесконтурный орграф|ориентированный бесконтурный | ||
граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину. | граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину. | ||
| Строка 16: | Строка 16: | ||
==См. также== | ==См. также== | ||
[[АВЛ-Дерево|''АВЛ-дерево'']], ''[[Асимметричное дерево]]'', ''[[Бесконечное дерево]]'', ''[[Бинарное дерево]]'', ''[[Бинарное дерево сортировки]]'', ''[[Бицентральное дерево]]'', ''[[Братское дерево]]'', [[1-2-Братское дерево|''1-2-братское дерево'']], ''[[Входящее дерево]]'', ''[[Выровненное дерево]]'', ''[[Вырожденное дерево]]'', ''[[Выходящее дерево]]'', ''[[Глубинное остовное дерево]]'', ''[[Гомеоморфно несводимое дерево]]'', ''[[Дерево | * [[АВЛ-Дерево|''АВЛ-дерево'']], | ||
''[[Постдоминаторное дерево]]'', ''[[Плоское дерево]]'', [[r-Плотное дерево|''<math>r</math>-плотное дерево'']], ''[[Пустое дерево]]'', ''[[Свободное дерево]]'', ''[[Сильно плотное дерево]]'', [[Сильное B-дерево|''Сильное <math>B</math>-дерево'']], [[Симметричное бинарное | * ''[[Асимметричное дерево]]'', | ||
* ''[[Бесконечное дерево]]'', | |||
* ''[[Бинарное дерево]]'', | |||
* ''[[Бинарное дерево сортировки]]'', | |||
* ''[[Бицентральное дерево]]'', | |||
* ''[[Братское дерево]]'', | |||
* [[1-2-Братское дерево|''1-2-братское дерево'']], | |||
* ''[[Входящее дерево]]'', | |||
* ''[[Выровненное дерево]]'', | |||
* ''[[Вырожденное дерево]]'', | |||
* ''[[Выходящее дерево]]'', | |||
* ''[[Глубинное остовное дерево]]'', | |||
* ''[[Гомеоморфно несводимое дерево]]'', | |||
* ''[[Дерево обязательного предшествования]]'', | |||
* ''[[Дерево обязательной преемственности]]'', | |||
* ''[[Доминаторное дерево]]'', | |||
* ''[[Конечное дерево]]'', | |||
* ''[[Корневое дерево]]'', | |||
* ''[[Левостороннее дерево]]'', | |||
* ''[[Линейное дерево]]'', | |||
* ''[[Многомерное дерево сортировки]]'', | |||
* [[Многомерное B-дерево|''Многомерное <math>B</math>-дерево'']], | |||
* ''[[Ориентированное дерево]]'', | |||
* ''[[Поисковое дерево]]'', | |||
* ''[[Постдоминаторное дерево]]'', | |||
* ''[[Плоское дерево]]'', | |||
* [[r-Плотное дерево|''<math>r</math>-плотное дерево'']], | |||
* ''[[Пустое дерево]]'', | |||
* ''[[Свободное дерево]]'', | |||
* ''[[Сильно плотное дерево]]'', | |||
* [[Сильное B-дерево|''Сильное <math>B</math>-дерево'']], | |||
* ''[[Симметричное бинарное дерево]]'', | |||
* ''[[Слабо плотное дерево]]'', | |||
* [[Слабое B-дерево|''Слабое <math>B</math>-дерево'']], | |||
* ''[[Сливаемое дерево]]'', | |||
* ''[[Упорядоченное дерево]]'', | |||
* [[B-Дерево|''<math>B</math>-дерево'']], | |||
* [[BB-Дерево|''<math>BB</math>-дерево'']], | |||
* [[H-Дерево|''<math>H</math>-дерево'']], | |||
* [[HB-Дерево|''<math>HB</math>-дерево'']], | |||
* [[HS-Дерево|''<math>HS</math>-дерево'']], | |||
* [[1-Дерево|''<math>1</math>-дерево'']], | |||
* [[k-Дерево малой высоты|''<math>k</math>-дерево малой высоты'']], | |||
* [[kB-Дерево|''<math>kB</math>-дерево'']], | |||
* [[k-d-Дерево|''<math>k-d</math>-дерево'']], | |||
* [[2-3-Дерево|''2-3-дерево'']]. | |||
== Литература == | == Литература == | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
[[Категория:Деревья]] | [[Категория:Деревья]] | ||