Изменения
→Структура
'''Дерево ван Эмде Боаса'''(англ. ''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>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.Это делает дерево достаточно компактным, если оно содержит много элементов, потому что новые поддеревья не создаются пока что-то не будет добавлено к нему. Первоначально каждый добавленный элемент, создает <tex> O(\log k)</tex> новых деревьев, содержащих около <tex>k/2</tex> элементов всего. По мере роста дерева, все больше и больше поддеревьев используются повторно, особенно крупные. В полном дереве из <tex>2^k</tex> элементов, используется только <tex> O(2^k)</tex> памяти. Кроме того, в отличие от двоичного дерева поиска, большинство из этой памяти используется для хранения данных.
==См. также==
* [[Поисковые структуры данных]]
