Дерево ван Эмде Боаса: следующий ключ за log log U

Если ты знаешь, как дерево ван Эмде Боаса делит диапазон на кластеры и сводку и почему поиск следующего стоит log log U, листай до «Теперь сам».

Как думаешь, можно ли искать следующий ключ быстрее логарифма

Задача: множество целых чисел из 0..U−1, запросы «вставить» и «найти наименьший ключ больше x». Так работает таймер событий в ядре ОС, маршрутизатор с таблицей адресов, планировщик с приоритетами из фиксированного диапазона. Сбалансированное дерево даёт O(log n), и сравнениями лучше не сделать.

Прежде чем читать дальше, ответь себе: что мы знаем о ключах, чего не знает дерево сравнений? Подсказка была в уроке про сортировку подсчётом: если ключ - небольшое целое, его можно использовать как адрес.

На что это похоже

Поиск ближайшего занятого места в огромном кинозале. Можно идти вдоль ряда кресло за креслом. А можно устроить так: у каждого ряда на входе табличка «в этом ряду кто-то есть, крайний справа - кресло 17», а у входа в зал - список непустых рядов. Тогда ищешь так: если в твоём ряду правее тебя кто-то есть - ищи в ряду; если нет - смотри по списку следующий непустой ряд и бери в нём самого левого. Никогда не приходится делать и то, и другое подробно. А если внутри ряда тоже устроить «секции» с табличками, и внутри секций ещё - получится дерево ван Эмде Боаса.

Механизм: кластеры, сводка и отдельный минимум

структура для диапазона 0..u−1 (u - квадрат, например 2^16):
    min, max      - хранятся прямо в узле
    кластер[h]    - структура для диапазона 0..√u−1, «ряд» номер h
    сводка        - структура для 0..√u−1: какие кластеры непусты

ключ x  →  h = x // √u   (номер кластера, «старшая половина цифр»)
           l = x %  √u   (место внутри кластера, «младшая половина»)

ВАЖНО: min узла в кластеры НЕ кладётся

Поиск следующего за x:

если x < min:                         ответ min
если в кластере h есть ключ > l:      ищем в кластере h  (1 спуск)
иначе:  h2 = следующий непустой кластер после h - ищем в сводке (1 спуск)
        ответ = h2·√u + min кластера h2   (min хранится, спуск не нужен)

Вставка тоже делает ровно один рекурсивный спуск: если кластер был пуст, ключ становится его min за O(1) (в глубину не идём - вот зачем min не кладут в кластер), а спуск уходит в сводку; если кластер не пуст - сводка уже знает о нём, и спуск идёт только в кластер.

Сколько уровней? Размер задачи u превращается в √u. Если u = 2^m, то √u = 2^(m/2): показатель степени делится пополам на каждом уровне. А число делений пополам до единицы - это логарифм. Значит, уровней log₂ m = log₂ log₂ u:

T(u) = T(√u) + O(1)        u = 2^64 → 2^32 → 2^16 → 2^8 → 2^4 → 2^2
                           шесть уровней: log₂ 64 = 6

Правило

Дерево ван Эмде Боаса для ключей из 0..U−1 хранит √U кластеров-поддеревьев размера √U, сводку непустых кластеров и min, max прямо в узле; min в кластеры не кладётся. Поиск следующего и вставка делают по одному рекурсивному спуску на уровень - либо в кластер, либо в сводку (удаление устроено так же: второй спуск у него возможен, только когда кластер опустел и стоит O(1)), - а размер задачи на уровне падает с u до √u. Отсюда O(log log U) на операцию: 6 уровней для 64-битных ключей. Полная структура требует памяти Θ(U); если заводить кластеры только по мере надобности (словарём), память - O(n · log log U).

Разбор: поиск следующего на 16 числах

U = 16, √U = 4. Ключи: 2 3 4 5 7 14 15
min = 2 - хранится только наверху, в кластеры не идёт
кластер 0 (числа 0..3):    {3}       → места {3}
кластер 1 (числа 4..7):    {4 5 7}   → места {0 1 3}
кластер 3 (числа 12..15):  {14 15}   → места {2 3}
сводка: непусты кластеры {0 1 3}

следующий после 5:  h = 1, l = 1. В кластере 1 max = 3 > 1 →
    ищем в кластере 1 следующий после 1: это 3  →  ответ 1·4 + 3 = 7

следующий после 7:  h = 1, l = 3. В кластере 1 max = 3, больше нет →
    сводка: следующий непустой после 1 - кластер 3
    ответ 3·4 + min(кластер 3) = 12 + 2 = 14

Во втором запросе сводка дала номер кластера, а сам ключ нашёлся без спуска в кластер - его min хранится в узле. Ровно поэтому спуск всегда один.

Разбор: от 2⁸ до 2⁶⁴

Программа строит структуру для диапазонов от 2⁸ до 2⁶⁴, кластеры заводит словарём по мере надобности, делает по 5000 запросов «следующий» и сверяет каждый ответ с двоичным поиском по отсортированному списку. Считается число вызовов на запрос.

import bisect
import random

vyzovy = 0


class VEB:                          # ключи 0..u−1, u = 2^(2^k)
    def __init__(self, u):
        self.u, self.min, self.max = u, None, None
        if u > 2:
            self.kor = int(round(u ** 0.5))   # √u: и число, и размер
            self.klastery = {}                # заводим по требованию
            self.svodka = None                # какие кластеры непусты

    def vstavit(self, x):
        global vyzovy
        vyzovy += 1
        if self.min is None:                  # пустая - O(1), вглубь
            self.min = self.max = x           # не спускаемся
            return
        if x < self.min:
            x, self.min = self.min, x         # min живёт только здесь
        if self.u > 2:
            h, l = divmod(x, self.kor)        # номер кластера, место
            c = self.klastery.get(h)
            if c is None:
                c = self.klastery[h] = VEB(self.kor)
            if c.min is None:                 # кластер был пуст:
                if self.svodka is None:       # один рекурсивный вызов -
                    self.svodka = VEB(self.kor)
                self.svodka.vstavit(h)        # в сводку,
                c.min = c.max = l             # а в кластер - O(1)
            else:
                c.vstavit(l)                  # иначе только в кластер
        if x > self.max:
            self.max = x

    def sleduyushchij(self, x):               # наименьший ключ > x
        global vyzovy
        vyzovy += 1
        if self.u == 2:
            return 1 if x == 0 and self.max == 1 else None
        if self.min is not None and x < self.min:
            return self.min
        h, l = divmod(x, self.kor)
        c = self.klastery.get(h)
        if c is not None and c.max is not None and l < c.max:
            return h * self.kor + c.sleduyushchij(l)   # внутри кластера
        if self.svodka is None:
            return None
        h2 = self.svodka.sleduyushchij(h)     # или в следующем кластере
        if h2 is None:
            return None
        return h2 * self.kor + self.klastery[h2].min


rng = random.Random(2)
for bity in (8, 16, 32, 64):
    U = 2 ** bity
    klyuchi = rng.sample(range(U), 100) if bity == 8 else \
        [rng.randrange(U) for _ in range(5000)]
    v, spisok = VEB(U), sorted(set(klyuchi))
    for k in spisok:                          # без повторов
        v.vstavit(k)
    vyzovy = 0
    for _ in range(5000):
        x = rng.randrange(U)
        i = bisect.bisect_right(spisok, x)
        otvet = spisok[i] if i < len(spisok) else None
        assert v.sleduyushchij(x) == otvet
    print(f"U = 2^{bity:<2}  вызовов на поиск следующего:"
          f" {vyzovy / 5000:.1f}")

U = 2^8   вызовов на поиск следующего: 3.4
U = 2^16  вызовов на поиск следующего: 4.0
U = 2^32  вызовов на поиск следующего: 4.9
U = 2^64  вызовов на поиск следующего: 6.0

Все ответы совпали с двоичным поиском. Число вызовов растёт на единицу при каждом ВОЗВЕДЕНИИ диапазона в квадрат: 2⁸ → 2¹⁶ → 2³² → 2⁶⁴ дают в среднем 3.4 → 4 → 4.9 → 6, и выше log₂ log₂ U вызовов не бывает. Сбалансированное дерево на тех же пяти тысячах ключей прошло бы около 12 уровней, и каждый - со сравнением.

Что ломается без этого

Самая частая ошибка - класть min в кластер, как все остальные ключи. Тогда вставка в пустой кластер спускается и в кластер, и в сводку - два рекурсивных вызова на уровень, и время становится O(log U): вся выгода пропала. Вторая - завести полную структуру на 64-битный диапазон: массив кластеров на верхнем уровне - 2³² ссылок, это 32 ГБ до первого ключа; без словаря структура годится только для U до миллионов. Третья - ждать от неё чудес на малом числе ключей: константы у неё большие, и на тысяче ключей двоичный поиск по списку или обычное дерево быстрее.

Зачем это в работе

Сама структура встречается редко, но её идея - «разделить ключ на старшую и младшую части и держать сводку непустых групп» - везде. Иерархические битовые карты в аллокаторах памяти и планировщиках ОС (битовая маска непустых очередей приоритетов плюс маски внутри групп) - это два-три уровня того же дерева. Префиксные деревья для таблиц маршрутизации делят адрес на куски по 8-16 бит. Алгоритм Дейкстры на графах с целыми весами использует такие очереди, чтобы обойти логарифм кучи. Когда ключи - целые из известного диапазона, граница log n для поиска следующего перестаёт быть пределом.

Теперь сам

U = 16, ключи 1 6 9 10 13. Разложи их по кластерам (с учётом того, что min наверху), запиши сводку и найди следующий после 10.