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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''<math>k</math>-Дерево малой высоты''' (''<math>k</math>-Tree with small height'') - бинарное выровнен...)
 
Нет описания правки
Строка 1: Строка 1:
'''<math>k</math>-Дерево малой высоты''' (''<math>k</math>-Tree with small height'') -  
'''<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>k</math> правых
соседей (или все правые соседи, если их число меньше <math>k</math>) этой вершины
имеют двух потомков. 1-дерево малой высоты есть в точности <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> --- число листьев.
==Литература==
==Литература==
[Евстигнеев/85],  
[Евстигнеев/85],  


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

Навигация