K-Дерево малой высоты: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''<math>k</math>-Дерево малой высоты''' (''[[k-Tree with small height|<math>k</math>-Tree with small height]]'') - [[бинарное дерево|бинарное выровненное дерево]], у которого [[вершина]] с одним [[потомок вершины|потомком]] имеет по крайней мере одного правого [[соседние вершины|соседа]] и первые <math>k</math> правых соседей (или все правые соседи, если их число меньше <math>k</math>) этой вершины имеют двух потомков. 1-[[дерево]] малой высоты есть в точности [[H-Дерево|<math>H</math>-дерево]].
'''<math>k</math>-Дерево малой высоты''' (''[[k-Tree with small height|<math>k</math>-Tree with small height]]'') [[бинарное дерево|бинарное выровненное дерево]], у которого [[вершина]] с одним [[потомок вершины|потомком]] имеет по крайней мере одного правого [[соседние вершины|соседа]] и первые <math>k</math> правых соседей (или все правые соседи, если их число меньше <math>k</math>) этой вершины имеют двух потомков. 1-[[дерево]] малой высоты есть в точности [[H-Дерево|<math>H</math>-дерево]].
Имеет место следующее утверждение: для любого <math>\epsilon > 0</math> существует такое <math>k</math>, что класс <math>k</math>-деревьев малой высоты есть класс выровненных бинарных деревьев высоты <math>h \leq (1 + \epsilon) \log n + 1</math>, где <math>n</math> --- число [[лист|листьев]].
Имеет место следующее утверждение: для любого <math>\epsilon > 0</math> существует такое <math>k</math>, что класс <math>k</math>-деревьев малой высоты есть класс выровненных бинарных деревьев высоты <math>h \leq (1 + \epsilon) \log n + 1</math>, где <math>n</math> число [[лист|листьев]].
==Литература==
==Литература==
[Евстигнеев/85],  
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
 
[Евстигнеев-Касьянов/94]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

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

[math]\displaystyle{ k }[/math]-Дерево малой высоты ([math]\displaystyle{ k }[/math]-Tree with small height) — бинарное выровненное дерево, у которого вершина с одним потомком имеет по крайней мере одного правого соседа и первые [math]\displaystyle{ k }[/math] правых соседей (или все правые соседи, если их число меньше [math]\displaystyle{ k }[/math]) этой вершины имеют двух потомков. 1-дерево малой высоты есть в точности [math]\displaystyle{ H }[/math]-дерево. Имеет место следующее утверждение: для любого [math]\displaystyle{ \epsilon \gt 0 }[/math] существует такое [math]\displaystyle{ k }[/math], что класс [math]\displaystyle{ k }[/math]-деревьев малой высоты есть класс выровненных бинарных деревьев высоты [math]\displaystyle{ h \leq (1 + \epsilon) \log n + 1 }[/math], где [math]\displaystyle{ n }[/math] — число листьев.

Литература

  • Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.