Дерево ван Эмде Боаса

:

Всем доброго времени суток!

Сегодня я расскажу вам об одной интересной структуре данных, про которую слышали лишь немногие и про которую очень незаслуженно мало написано в рунете, да и в англоязычном информации, в общем-то, тоже негусто. Решено было исправить ситуацию и поделиться с общественностью в доступной форме этой достаточно экзотической структурой данных.

Дерево ван Эмде Боаса (van Emde Boas tree) — ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2 k, проще говоря, числа, состоящие не более чем из k бит. Казалось бы, зачем нужно еще какое-то дерево, да еще позволяющее хранить только целые числа, когда существует множество различных сбалансриованных двоичных деревьев поиска, позволяющих выполнять операции вставки, удаления и прочие за O(log n), где n — количество элементов в дереве?

Главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

Собственно, вот небольшой список поддерживающихся операций:

  • Insert(x) — Вставка числа в дерево
  • Remove(x) — Удаление числа
  • GetMin(), GetMax() — Нахождение минимума и максимума в дереве
  • Find(x) — Поиск числа в дереве
  • FindNext(x) — Поиск следующего числа после x, которое содержится в дереве
  • FindPrevious(x) — Поиск предшествующего x числа
При этом, конечно, можно связать с каждым из чисел какую-нибудь информацию, скажем, мы будем хранить в дереве номера каких-то товаров и по номеру сможем узнавать имя товара, то есть Find(x) будет возвращать не просто True/False — существует ли товар или нет, а имя товара с номером x. Мы рассмотрим реализацию, в которой хранятся просто числа, без дополнительной информации. Прикрутить же эту фичу не составит никакого труда.

Итак, приступим к построению нашей структуры, причем строить ее будем рекурсивно.

Пусть k-дерево будет хранить числа в интервале [0; 2 k), то есть, состоящие из k бит. При этом само число k будет степенью двойки, позже будет понятно, зачем нам необходимо такое условие. Тогда очевидно, как построить 1-дерево, оно будет лишь хранить информацию о том, существуют ли числа 0 или 1 в нем или нет.

Теперь построим k-дерево. В нем будет храниться:

  • 2k / 2 штук (k / 2)-дервьев
  • Вспомогательное (k / 2)-дерево
  • Минимальное и максимальное число, содержащееся в этом дереве (если оно не является пустым)
Становится непонятно, зачем нам это все нужно?

Представим теперь, что мы пытаемся вставить число x, состоящее из k бит в k-дерево, содержащее поддеревья children[0..2 k / 2 — 1]. Например, пусть x = 93. Посмотрим на его двоичное представление:

image

Разобъем наше число на две равных части high и low, каждая по (k / 2) бит. Вспоминаем, что в нашем дереве содержится 2 k / 2 деревьев, которые хранят числа из (k / 2) бит. А теперь возьмем из всех этих деревьев high-тое по счету (т. е. children[high]) и рекурсивно вставим в него число low.

Таким образом получаем простой алгоритм вставки и поиска в дереве T числа x, псевдокод:

insert(T, x):
    if T.k == 1:
        T.exist[x] = True # обрабатываем отдельно случай вставки в 1-дерево
    else:
        insert(T.children[high(x)], low(x))

find(T, x):
    if T.k == 1:
        return T.exist[x]
    else:
        return find(T.children[high(x)], low(x))

Оценим асимптотически время работы этих функций. Пусть T(k) — количество операций, требующихся для вставки/поиска числа в k-дереве. Для вставки/поиска в 1-дереве нам необходимо O(1) операций, получаем, что T(1) = O(1). Если же мы рассмотрим k-дерево (k > 1), то получим, что распил числа с помощью битовых операций в нем происходит за O(1), после чего мы выполняем операцию вставки/поиска для (k / 2)-дерева, получаем, что T(k) = O(1) + T(k / 2). Очевидное решение этого уравнения T(k) = O(log(k)) = O(log(log(U)). Получается, что мы добились требуемой асимптотики для вставки и поиска.

К сожалению, такая структура с одними лишь операциями вставки, поиска и удаления, мягко говоря, в большинстве случаев бессмысленна, учитывая то, что в данном случае проще было создать обычный массив A, в x-ом элементе которого хранится, существует ли число x в нашем множестве или нет.

Пришло время исправлять ситуацию! Для этого реализуем, скажем, операцию FindNext(x). Напомню, что эта операция ищет минимальное число q, содержащееся в нашем дереве, такое, что q >= x.

Для этого немного дополним нашу структуру. Напомню, что в самом начале я сказал, что мы будем хранить в k-дереве не только 2 k / 2 штук (k / 2)-деревьев, но минимум в нём, максимум и еще одно вспомогательное (k / 2)-дерево, назовем его aux (от англ. auxiliary — вспомогательный). Чем же оно будет нам так помогать?

Возьмем k-дерево с его поддеревьями children[0..2 k / 2 — 1] и вспомогательным деревом aux. В aux мы будем хранить все такие числа p, что дерево children[p] не является пустым, т. е. содержит хотя бы одно число. Соответственно, если p-ое дерево children[p] является пустым, то число p не содержится в aux.

Также, произведем незначительную модификацию: для любого дерева T мы не будем хранить минимальное число в его поддеревьях T.children, будем просто записывать его в переменную T.min. Когда в запросе вставки нам придется вставить в него число x, меньшее, чем T.min, то так как T.min не содержится в наших поддеревьях, вставим его в поддеревья, после чего присвоим T.min = x.

Заметим, что теперь мы не будем отдельно рассматривать случай k = 1, так как у нас присутствуют переменные T.min и T.max. И если, скажем, 1-дерево содержало числа 0 и 1, то у него просто будет T.min = 0, а T.max = 1. Если же, например, оно содержало только число 1, то у него будет T.min = T.max = 1.

Теперь рассмотрим алгоритм вставки в дерево с учетом всего вышеперечисленного:

insert(T, x):
    if T.is_empty():
        T.min = T.max = x
    else:
        if x < T.min:
            swap(x, T.min) # мы не храним минимум в поддеревьях, придется вставить старый минимум
        if x > T.max:
            T.max = x
        if T.k != 1: # если это 1-дерево, то не имеет смысла дальше что-то пропихивать
            if T.children[high(x)].is_empty():
                insert(T.aux, high(x)) # если так, то следующий insert выполнится за O(1)
            insert(T.children[high(x)], low(x))

Асимптотика времени его работы будет все так же O(log(log(U))), она оценивается аналогично предыдущей версии функции insert. Необходимо лишь заметить, что если мы выполним вставку в aux, то следующий за ним insert будет работать за O(1), так как это поддерево будет пустым.

Функция поиска немного поменяется:

find(T, x):
    if T.is_empty():
        return False
    else if T.min == x or T.max == x: # условие T.max == x можно было и не добавлять
        return True
    else:
        return find(T.children[high(x)], low(x))

Теперь рассмотрим функцию FindNext(x), вот её псевдокод с комментариями:

find_next(T, x):
    if T.is_empty() or x > T.max: 
        return None # следующего числа за x в этом дереве не существует
    if x <= T.min:
        return T.min # так как оно минимальное, оно и будет следующим
    if T.k == 1: # рассмотрим случай 1-дерева
        if T.max == x:
            return T.max
        else:
            return None
    if not T.children[high(x)].is_empty() and low(x) <= T.children[high(x)].max:
        # случай, когда число, которое мы ищем, начинается на high(x)
        return merge(high(x), find_next(T.children[high(x)], low(x)))
    else:
        # иначе найдем первое возможное начало числа, которое мы ищем
        next_high = find_next(aux, high(x) + 1) # найдем следующее непустое поддерево
        if next_high != None:
            return merge(next_high, T.children[next_high].min) # дерево непусто, возьмем его минимум
        return None

merge(high, low):
    return результат склеивания (k / 2)-битовых чисел high и low

Асимптотика её работы, очевидно, O(log(log(U)).

Думаю, написание таких функций как Remove, FindPrevious и прочих не должно вызвать особого труда, ибо пишутся они все аналогично, поэтому их псевдокод я опущу.

Применение


Кроме очевидного применения дерева ван Эмде Боаса можно придумать множество неожиданных, например:
  • Сортировка последовательности из N чисел за O(n * log(log(U)))
    Действительно, вставим все наши числа в дерево. После чего возьмем минимальное число в дереве и будем последовательно выполнять операцию x = FindNext(x + 1), в результате чего в переменной x побывают все наши числа в отсортированном порядке. Заметим, что можно написать различные реализации этой сортировки, в том числе и те, которая заодно удаляет повторяющиеся элементы. Основное приемущество этой сортировки в том, что по асимптотике этот алгоритм обгоняет даже цифровую сортировку.
  • Нахождение наидлиннейшей возрастающей подпоследовательности за O(n * log(log(U)))
    Некоторые наверняка слышали о такой задаче, как нахождение НВП и ее решении за O(n * log(n)). Для тех, кто не слышал, могут прочитать об этом здесь. Основная идея оптимизации заключается в том, что бинарный поиск в массиве можно заменить на операцию FindPrevious в дереве ван Эмде Боаса.
  • Алгоритм Дейкстры за O(E * log(log(U)))
    Для тех, кто не знаком с алгоритмом Дейкстры поиска кратчайшего пути во взвешенном графе, предлагаю ознакомиться с этой, а также с этой статьей. Реализация алгоритма Дейкстры с помощью кучи, как известно, работает за O(E * log(V)), где V — количество вершин, а E — количество ребер. Но если теперь вместо кучи применить всем нам уже известную структуру данных, то получим асимптотику O(E * log(log(U))), что не может не радовать.
  • И еще много-много задач, количество которых ограничено лишь вашей фантазией :)

Минус всех этих алгоримтов заключается в том, что для слишком больших U дерево ван Эмде Боаса будет занимать большее количество памяти (грубая оценка — O(U)), чего, впрочем, можно попытаться частично избежать, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.

Вместо заключения


Здесь находится моя реализация дерева ван Эмде Боаса на C++. Она не претендует на безупречность, но свою работу должна выполнять. Дополнения и комментарии приветствуются.

Всем спасибо за внимание!