1632
правки
Изменения
м
rollbackEdits.php mass rollback
Как уже было сказано выше, <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>
'''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'''
=== Недостатки ===
*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает сужает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <tex> k </tex>-битные числа, занимает <tex> \Theta(2^k) </tex> памяти, что несложно доказывается индукцией, учитывая, что <tex> S(2^k)=(2^{k/2} + 1) \cdot S(2^{k/2}) + O(2^{k/2})</tex>, где <tex> S(2^i) </tex> {{---}} количество памяти, занимаемое деревом, в котором хранятся <tex> i </tex>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.
