Изменения
→Структура
'''Дерево ван Эмде Боаса'''(англ. ''Van Emde Boas tree, vEB tree'') {{---}} структура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^k)</tex> и осуществлять над ними все соответствующие дереву поиска операции.
Проще говоря, данная структура позволяет хранить <tex>k</tex>-битные числа и производить над ними операции <tex>\mathrm{find}</tex>, <tex>\mathrm{insert}</tex>, <tex>\mathrm{remove}</tex>, <tex>\mathrm{next}</tex>, <tex>\mathrm{prev}</tex>, <tex>\mathrm{\min}</tex>, <tex>\mathrm{max}</tex> и некоторые другие операции, которые присущи всем деревьям поиска.
Для удобства работы с деревом будем использовать <tex> k </tex>, равные степени двойки.
Как уже было сказано выше, <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'''
=== Недостатки ===
*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <tex> k </tex>-битные числа, занимает <tex> O\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>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.
==См. также==
