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

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

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

    Дерево ван Эмде Боаса (van Emde Boas tree) — ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2k, проще говоря, числа, состоящие не более чем из 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; 2k), то есть, состоящие из k бит. При этом само число k будет степенью двойки, позже будет понятно, зачем нам необходимо такое условие. Тогда очевидно, как построить 1-дерево, оно будет лишь хранить информацию о том, существуют ли числа 0 или 1 в нем или нет.

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

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

    image

    Разобъем наше число на две равных части high и low, каждая по (k / 2) бит. Вспоминаем, что в нашем дереве содержится 2k / 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-дереве не только 2k / 2 штук (k / 2)-деревьев, но минимум в нём, максимум и еще одно вспомогательное (k / 2)-дерево, назовем его aux (от англ. auxiliary — вспомогательный). Чем же оно будет нам так помогать?

    Возьмем k-дерево с его поддеревьями children[0..2k / 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++. Она не претендует на безупречность, но свою работу должна выполнять. Дополнения и комментарии приветствуются.

    Всем спасибо за внимание!
    Поделиться публикацией
    Комментарии 39
    • НЛО прилетело и опубликовало эту надпись здесь
        +1
        действительно хорошая статья
          +3
          Ух ты, впервые о таком слышу. Спасибо большое за информацию, может пригодиться.
            +5
            Хотелось бы увидеть реальные тесты скорости работы данного алгоритма и привычных методов, которые работают за O(log(N)). Действительно, O(LOG(LOG(N))) не намного лучше чем просто O(LOG(N)) при больших N, и тут важен константный множитель, который не учитывается оператором О.
            Например, скорость вставки/поиска в массив данных размером 0,1 млн, 1млн, 10млн, 100млн и объем использованной памяти
              +2
              Если я правильно понял, то в данном случае N*log(N) надо сравнивать не с N*log(log(N)), а с N*log(log(U)), где log(U) — это количество бит в числах.
              Т.е. для 32х разрядных чисел это будет просто N*5 для любого числа элементов (правда, потребление памяти будет эпичнейшим, ну да не суть).
                0
                Да, вы абсолютно правы. Но тесты все-равно хотелось бы увидеть что бы понять имеет смысл этот алгоритм в реальных проектах, или нет
                  +1
                  Википедия утверждает, что для маленьких деревьев — очень большие накладные расходы получаются, и предлагает использовать trie, y-fast tries, x-fast tries:

                  Van_Emde_Boas_tree

                  However, for small trees the overhead associated with vEB trees is enormous: on the order of 2m/2. This is one reason why they are not popular in practice. One way of addressing this limitation is to use only a fixed number of bits per level, which results in a trie. Other structures, including y-fast tries and x-fast tries have been proposed that have comparable update and query times but use only O(n) or O(n log M) space where n is the number of elements stored in the data structure.
                  +1
                  >> где U = 2k
                  Т.е. для 32х разрядных чисел это будет 2^32 = 4294967296

                  O(log(log(U))) будет порядка O(log(k)) вместо «обычных» O(log(n)).
                0
                Спасибо за статью!

                > …скажем, мы будем хранить в дереве номера каких-то товаров и по номеру сможем узнавать имя товара…

                Но ведь соответствие номер-имя всё равно будет храниться в обычном дереве, со временем выборки N log N?
                  +1
                  Эта информация будет храниться в дереве вместе с минимумом (то есть T.min и, скажем, T.min_value) и ничего больше нам для этого не будет нужно.
                    0
                    Вместо булева T.exists[] будет структура с доп. информацией.
                    А те же проверки заменятся на равно (не равно) null.
                      0
                      Поясню, а то два разных ответа. Я ответил про простой случай, в котором нет возможности FindNext и FindPrevios, а Invizory выше про дерево уже с такими возможностями.

                      Такие соотношения вообще можно держать в хеше, и получится быстродействие O(N) (если грубо), что оптимальнее данного алгоритма, особенно на практике.
                      Но чаще держат в B-деревьях, так как они оптимизированы под работу блочной структурой диска со сложность N log N.
                    0
                    А что с памятью? Вроде в статье есть беглая оценка в O(U) — это странно.
                    Ведь если каждая операция log(log(U)) времени, то памяти займем не более чем n * log(log(U)), если не делать зверских предобработок.
                      0
                      Я правильно понимаю, что при больших k (>18-20) мы улетаем за границы кешей процессора, и все начинает так тормозить, что никакое log(log()) не поможет?
                        0
                        Мне кажется это проблема присуща большинству структур данных.
                        — двоичный поиск будет попадать мимо кеша поначалу
                        — AVL и RB -деревья тоже могут попадать мимо кеша

                        А большинство сортировок похоже будут хорошо ложится в кеш:)
                          +2
                          Во-первых, k у нас является степенью двойки (по очевидным причинам) и немного неправильно писать «k > 18-20».
                          Во-вторых, могу сказать, что при N >= 10^6, дерево ван Эмде Боаса начинает ощутимо перегонять двоичные деревья поиска, в том числе и красно-черное дерево. Если же нужны красивые графики, большие таблички и конкретные числа — тут нужно уже делать отельный крутой бенчмарк.
                          Если же все-таки нужны конкретные цифры, то, скажем, на тесте N = 10^7, K = 32 всеми нами любимый STL'ный set (а STL, как известно, не индусы писали — чего только стоит их хитрый sort) работает за 4.856 секунд, когда дерево ван Эмде Боаса (в моей реализации) за 1.471. Вот как-то так.
                            0
                            «STL'ный set… работает за 4.856 секунд» что это значит? Какие операции? Какие данные? Как время замерялось? Какая погрешность? Да и поиск в сортированном векторе почти в 4 раза быстрее чем в set. habrahabr.ru/blogs/cpp/114518/
                              0
                              Я же сказал, что надо делать нормальный бенчмарк. Это я предоставил в качестве примера того, что дерево ван Эмде Боаса работает быстрее сеты в некоторых условиях.
                              Поиск в отсортированном векторе (и да, раз мы уж о производительности — к черту вектора, используем обычные массивы) бинарным поиском конечно тоже можно применить, но пока еще никто не научился вставлять элемент в середину вектора быстрее, чем за O(n).
                              +1
                              Да, STL не индусы писали, но всё-таки у сета довольно большая константа. Мне кажется, что дерево ван Эмде Боаса стоит сравнивать по времени работы с деревом отрезков. У дерева отрезков время работы O(N*log(N)), причём константа не сильно большая, а так же оно поддерживает все необходимые вам операции. Что касается памяти, так вроде полностью заполненное дерево вад Эмде Боаса будет хранить более 2*N памяти (размер дерева отрезков) из-за хранения этих дополнительных aux k/2-деревьев.

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

                              Не понятно, почему в случае вставки в aux следующий за ним insert работает за O(1). Ведь нам всё равно при выполнении insert придётся пройти те же самые log(k) уровней до 1-дерева, значит и функция T(k) время работы будет более сложно пересчитываться, разве нет?
                                +1
                                Насчет дерева отрезков могу сказать следующее. При K = 32 ось попросту отказалась выделять мне столько памяти для него, ну оно и понятно, поэтому U было снижено до 108. После чего RMQ отработала N = 107 запросов вставки и нахождения следующего за 5.24 секунды, тогда как дерево ван Эмде Боаса за 3.112. Ну как бы понятно, что все бенчмарки, проводимые мною, не совсем честные, поэтому надо делать нормальный, но уже можно видеть, что преимущество дерево ван Эмде Боаса таки дает.

                                К вопросу об асимптотике. Следующий insert будет работать за асимптотику O(1) по той простой причине, что

                                if T.children[high(x)].is_empty():
                                    insert(T.aux, high(x))

                                по условию дерево T.children[high(x)] — пустое, а вставка в пустое дерево

                                if T.is_empty():
                                    T.min = T.max = x

                                как можно видеть, работает за константу.

                                P. S. Привет команде посвята :)
                                  +1
                                  Да, теперь видно преимущество этого дерева перед остальными при больших U. Код, правда, чуть более сложный, но при написании больших проектах, где быстродействие важно, это дерево полезно использовать.
                                  Спасибо за уточнение. Что-то я пропустил строки вставки элемента в пустое дерево.

                                  P. S. Мда, мир тесен. Про это дерево вам рассказали в параллели A, или где ты натолкнулся на эту структуру?
                                    0
                                    По иронии судьбы про это дерево я узнал где-то за неделю до того, как его рассказали, но не обратил должного внимания, как сейчас. Как-то так.
                            –1
                            спасибо за статью.
                            плюсовать не хватает кармы ((
                              +2
                              Не к чему придраться. Хорошо написано и код качественный! Нужно больше таких авторов на хабре.
                              Хотелось бы спросить какое отношение имеет автор к этой теме (работа, научная деятельность, олимпиадное программирование или что-то другое)?
                                0
                                Ваша реализация падает в деструкторе. linux, gcc version 4.5.2.
                                  0
                                  Да, было такое, пофиксил. Спасибо.
                                  0
                                    +10
                                    Имею честь быть с Петером ван Эмде Босом знакомым лично. Писал в со-авторстве с его женой книгу…
                                      0
                                      Интересно, что не все добавившие статью в избранное, поставили плюс этой статье :)
                                        +1
                                        Это очень частое явление…
                                          0
                                          Обычно это значит что не у всех, добавивших в избранное, есть возможность ставить плюсы.
                                            +1
                                            Или что человек поставит плюс, когда прочитает статью, я обычно добавляю статью в избранное, чтобы когда появится время — посидеть и спокойно почитать и разобраться.
                                              0
                                              Только плюсы можно ставить в течение двух дней с момента публикации. Часто у хороший статей плюсов меньше, чем число человек, добавивших статью в избранное.
                                              Я обычно плюсую статью уже за то, что она заинтересовала меня. А если была полезной, то автору плюс и в карму поставлю (благо, это можно сделать всегда).
                                                +3
                                                К сожалению несколько раз натыкался на то, что статья с хорошим заголовком на интересную тему содержит внутри настолько яростный бред, что даже стыдно как-то за поставленный впопыхах плюс (:
                                        0
                                        Спасибо за статью.
                                        Видимо я что-то не понял в подсчёте сложности. Поясните, пожалуйста. Вопрос по простому алгоритму. Что мы считаем элементарной операцией? Считаете ли вы любую функции high и low требующими одну операцию? Обращение по индексу длины k/2 является одной операцией?
                                          0
                                          Конечно, у нас же обращение к массиву за O(1).
                                          По поводу high и low — вот их реализация битовыми сдвигами:

                                          high(x) = x >> (k / 2)
                                          low(x) = x & (~(1 << (k / 2)))
                                            0
                                            Не очень понял. Поместить индекс длины k/2 это тоже одна операция? Деление числа k на 2, сдвиг на k/2 бит — одна операция?
                                              0
                                              Я имею в виду, почему Вы не считаете битовую сложность? Если Вы говорите о числах длины k, то нужно операции над числами длины k считать не константными.
                                                0
                                                Не 1 операция, а O(1), это важно.

                                                Далее, все эти операции, будь то сдвиг или еще что выполняются за одну процессорную операцию и ему абсолютно по-барабану какое там k.

                                                Например, вот такой сдвиг влево

                                                shl eax, 1

                                                и вот этот

                                                shl eax, 8

                                                вообще ничем не отличаются и выполняются за одно и то же число процессорных тактов.

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое