Изменения

<b>Переполненным</b> назовем узел, для которого для любой выбранного <tex>\alpha</tex> (<tex>1<\alpha<2</tex> ) выполнено <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. В листьях не хранится наличие переполненности, так как в листьях не может быть переполнения. В крайнем случае для листа: <tex> \dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}} = 1 \ngtr 1 = \dfrac{1}{\alpha^{0}} = \dfrac{1}{\alpha^{\mathrm{height(x)}}} </tex>.

Выбор <tex>\alpha</tex> сильно влияет на реализацию структуры, так как <tex>u</tex> зависит от выбранной <tex>\alpha</tex>. Увеличивая С увеличением <tex>\alpha</tex>, уменьшается стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличивается <tex>u</tex>, значит, требуется больше памяти, а, уменьшая <tex>\alpha</tex>, возникает получаем выигрыш в памяти, но проигрыш во времени операции добавления. Так как для реализации структуры используется <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex>, требуется <tex>O(n)</tex> памяти.