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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Дерево'''([[Tree|Tree]]) - связный граф без циклов. Чаще всего этот термин используется как
'''Дерево'''([[Tree|Tree]]) — [[связный граф|связный граф]] без циклов. Чаще всего этот термин используется как краткая форма термина [[корневое дерево|''корневое дерево'']], т.е. конечное множество одной или нескольких [[вершина|вершин]] таких, что, во-первых, среди них
краткая форма термина [[корневое дерево|''корневое дерево'']], т.е. конечное множество
одной или нескольких вершин таких, что, во-первых, среди них
существует только одна особая вершина, называемая ''корнем'', и,
существует только одна особая вершина, называемая ''корнем'', и,
во-вторых, остальные вершины делятся на <math>d</math> непересекающихся множеств
во-вторых, остальные вершины делятся на <math>d</math> непересекающихся множеств
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math> каждое из которых само является
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math> каждое из которых само является
деревом. Множества
деревом. Множества
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются ''поддеревьями''
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченное дерево|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким
корня. Если порядок в этих деревьях существен, дерево называется {\it
образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево это [[бесконтурный орграф|ориентированный бесконтурный
упорядоченным деревом}, в противном случае оно иногда называется
граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.
неупорядоченным деревом. Дерево может быть представлено как граф, в
котором корневая вершина представлена вершиной, соединенной дугами с
вершинами, представляющими корни каждого из ее поддеревьев. Таким
образом, в терминах теории графов можно дать другое определение ({\it
ориентированного}) дерева: дерево --- это ориентированный бесконтурный
граф такой, что, во-первых, существует единственная вершина, в которую
не входит ни одна дуга (эта вершина называется корнем), во-вторых, в
каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих,
существует единственный путь из корня в любую другую вершину.


2. Любая древовидная структура данных (в смысле сделанных выше
2. Любая древовидная структура данных (в смысле сделанных выше определений). Например, корневое дерево может быть представлено как указатель представления корневой вершины. Представление вершины должно содержать указатели на поддеревья этой вершины, так же как и на данные, связанные с самой этой вершиной. Поскольку число поддеревьев данной вершины может изменяться, на практике обычно используют представление в виде [[двоичное дерево|двоичного дерева]]. Терминология, связанная с
определений). Например, корневое дерево может быть представлено как
деревьями, взята или из ботаники, как, например, термины [[лес|лес]], [[лист|лист]],
указатель представления корневой вершины. Представление вершины должно
корень, или из генеалогии, как, например, термины [[предок вершины|вершина-предок]],
содержать указатели на поддеревья этой вершины, так же как и на
[[потомок вершины|вершина-потомок]], [[сын|вершина-сын]], [[отец вершины ордерева|вершина-отец]], [[брат вершины v|вершина-брат]] и т.д.
данные, связанные с самой этой вершиной. Поскольку число поддеревьев
 
данной вершины может изменяться, на практике обычно используют
[[Файл:Tree.png|700px]]
представление в виде двоичного дерева. Терминология, связанная с
деревьями, взята или из ботаники, как, например, термины лес, лист,
корень, или из генеалогии, как, например, термины вершина-предок,
вершина-потомок, вершина-сын, вершина-отец, вершина-брат и т.д.


==См. также==  
==См. также==  
[[АВЛ-дерево|''АВЛ-дерево'']], [[Асимметричное дерево|''Асимметричное дерево'']], [[Бесконечное дерево|''Бесконечное дерево'']], [[Бинарное дерево|''Бинарное дерево'']], [[Бинарное дерево сортировки|''Бинарное дерево сортировки'']], [[Бицентральное  дерево|''Бицентральное  дерево'']], [[Братское дерево|''Братское дерево'']], [[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.
 
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 


[Евстигнеев-Касьянов/94]
[[Категория:Деревья]]

Текущая версия от 13:35, 3 февраля 2011

Дерево(Tree) — связный граф без циклов. Чаще всего этот термин используется как краткая форма термина корневое дерево, т.е. конечное множество одной или нескольких вершин таких, что, во-первых, среди них существует только одна особая вершина, называемая корнем, и, во-вторых, остальные вершины делятся на [math]\displaystyle{ d }[/math] непересекающихся множеств [math]\displaystyle{ T_{1}, \, T_{2}, \ldots, \, T_{d} }[/math] каждое из которых само является деревом. Множества [math]\displaystyle{ T_{1}, \, T_{2}, \ldots, \, T_{d} }[/math]называются поддеревьями корня. Если порядок в этих деревьях существен, дерево называется упорядоченным деревом, в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как граф, в котором корневая вершина представлена вершиной, соединенной дугами с вершинами, представляющими корни каждого из ее поддеревьев. Таким образом, в терминах теории графов можно дать другое определение (ориентированного) дерева: дерево — это ориентированный бесконтурный граф такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.

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

Tree.png

См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.