Изменения
→Структура
Как уже было сказано выше, <tex>k</tex>-дерево хранит числа в интервале <tex>[0;2^k)</tex>. Тогда при <tex>k = 1</tex> дерево хранит информацию, содержатся ли в нем <tex>0</tex> и <tex>1</tex>.
Построим <tex>k</tex>-дерево, при <tex>k \neq 1</tex>. В нем будут хранитсяхраниться:
*массив <tex>children</tex>, состоящий из <tex>2^{k/2}</tex> <tex>k/2</tex>-деревьев
*вспомогательное <tex>k/2</tex>-дерево, которое назовем <tex>aux</tex>
'''boolean''' empty(t: '''Tree'''):
'''if''' t.min == ''none''
'''return''''' true''
'''else'''
'''return''''' false''
</code>
'''boolean''' find(t: '''Tree''', x: '''int'''):
'''if''' empty(t)
'''return''''' false''
'''if''' t.min == x '''or''' t.max == x
'''return''''' true''
'''return''' find(t.children[high(x)], low(x))
</code>
'''return'''
x = merge(t.aux.min, t.children[t.aux.min].min)
'''if''' t.max == x
'''if''' empty(t.aux)
t.max = t.min
'''return'''
x = merge(t.aux.max, t.children[t.aux.max].max)
t.max = x
'''else''' <span style="color:#008000">// иначе найдем следующее непустое поддерево</span>
'''int''' nextHigh = next(t.aux, high(x));
'''if''' nextHigh == -1''none''
'''return''' t.max; <span style="color:#008000">// если такого нет, вернем максимум</span>
'''else'''
