K-Дерево малой высоты

[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] --- число листьев.

Литература

[Евстигнеев/85],

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