Дерево: различия между версиями

Перейти к навигации Перейти к поиску

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

Версия от 13:35, 3 февраля 2011

789 байт убрано ,  3 февраля 2011
нет описания правки
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии 2 участников)
Строка 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-братское дерево'']], [[Входящее дерево|''Входящее дерево'']], [[Выровненное дерево|''Выровненное дерево'']], [[Вырожденное дерево|''Вырожденное дерево'']], [[Выходящее дерево|''Выходящее дерево'']], [[Глубинное остовное дерево|''Глубинное остовное дерево'']], [[Гомеоморфно несводимое дерево|''Гомеоморфно несводимое дерево'']], [[Дерево обязательных предшественников|''Дерево обязательных предшественников'']], [[Дерево обязательных преемников|''Дерево обязательных преемников'']], [[Доминаторное дерево|''Доминаторное дерево'']], [[Конечное дерево|''Конечное дерево'']], [[Корневое дерево|''Корневое дерево'']], [[Левостороннее дерево|''Левостороннее дерево'']], [[Линейное дерево|''Линейное дерево'']], [[Многомерное дерево сортировки|''Многомерное дерево сортировки'']], [[Многомерное B-дерево|''Многомерное <math>B</math>-дерево'']], [[Ориентированное дерево|''Ориентированное дерево'']], [[Поисковое дерево|''Поисковое дерево'']],
* [[АВЛ-Дерево|''АВЛ-дерево'']],
[[Постдоминаторное дерево|''Постдоминаторное дерево'']], [[Плоское дерево|''Плоское дерево'']], [[r-плотное дерево|''<math>r</math>-плотное дерево'']], [[Пустое дерево|''Пустое дерево'']], [[Свободное дерево|''Свободное дерево'']], [[Сильно плотное дерево|''Сильно плотное дерево'']], [[Сильное B-дерево|''Сильное <math>B</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>-дерево'']], [[I-дерево|''<math>I</math>-дерево'']], [[k-дерево малой высоты|''<math>k</math>-дерево малой высоты'']], [[kB-дерево|''<math>kB</math>-дерево'']], [[k-d-дерево|''<math>k-d</math>-дерево'']], [[2-3-дерево|''2-3-дерево'']].
* ''[[Асимметричное дерево]]'',
* ''[[Бесконечное дерево]]'',
* ''[[Бинарное дерево]]'',
* ''[[Бинарное дерево сортировки]]'',
* ''[[Бицентральное  дерево]]'',
* ''[[Братское дерево]]'',
* [[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.


[Евстигнеев-Касьянов/94]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 
 
[[Категория:Деревья]]
Источник — http://pco.iis.nsk.su/grapp/index.php/Служебная:Сравнение_версий/2772...6070

Навигация