Прочие вкусные разновидности деревьев

Я не договорил.


Judy array
Как я и говорил, если дерево не устраивает - его нужно привить с другим, чтобы устроило. Селекция, ёпта. А Judy array - это как раз буквально такая ядерная смесь:
— Обычное 256-арное дерево (покрывает все значения одного байта).
— Префиксное (сжатое) 256-арное дерево - когда путь состоит из нескольких узлов подряд с единственным наследником. Я бы здесь вставил картинку, но мы в телеграмме, а поэтому могу визуализировать только так: дерево {"Х"} -> {"У"} -> {"Й"} скукоживается до кондиции {"ХУЙ"}.
— AMT - когда префиксов особо нет (тогда хранить строку на порядок дороже, чем просто символ), но и наследников тоже немного. Dense array - массив из только non-NULL узлов, рядом всегда битмапа, всё как я и рассказывал ранее. Кстати, можно сказать, что это не столько самостоятельный концепт, сколько оптимизация для sparse arrays.

Тип узла помечается соответствующим енумом. Из интересного - Judy array скорее вполне конкретная реализация, потому что там ещё думают про кэшлинии, чтобы всё красивенько лежало. Штука, правда, очень ситуативная, да и заточена под чтение, а не вставку, и потому андерграунд.

Hash Array Mapped Trie (HAMT)
Абсолютно тот же AMT, только вместо строк хранятся их хэши. Это круто, потому что хэш всегда одинаковой длины, а значит, и глубина дерева - константная. Тогда и ресайз довольно дешёвый, растёт-то только в ширину - просто побольше слотов массиву докинуть надо.

Идея не поменялась: имея n-арное дерево, берём от числа-ключа log(n) нижних бит и индексируем ими следующую ветвь. Например, обычно берут n=32, и теперь мы храним по 5 бит хэша в каждом узле. Меняем char sym на char bits:5. Ну и битмапа 32-битная, соответственно. Поиск будет выглядеть примерно так:

struct HAMT{
  char bits:5;
  uint32 bitmap;
  struct HAMT* c[];
}

bool search(struct HAMT* node, char* s) {
  return search_(node, strhash(s));
}

bool search_(struct HAMT* node, uint64 hash) {
  for (int i = 0; i < 13; i++) {
    uint32 b = 1 << (hash & 0b11111);
    if (node->bitmap & mask == 0)
      return false;
    uint preceding = node->bitmap & (mask-1);
    uint next = __builtin_popcount(preceding);
    node = node->c[next];
    hash >>= 5;
  }
  // if reached, the hash is in the trie.
  return true;
}

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

И даже терминальный флаг не нужен! Глубина-то константная, с n=32 любой узел на ⌈64 / log32⌉ = 13 уровне будет сам по себе терминальным. И поэтому, если мы не успели сделать возврат в цикле, то после него мы точно знаем, что в node у нас лежит терминальный. Если бы мы добавили что-нибудь полезное туда, тогда после цикла было бы просто return node->value;

И сейчас я ещё до кое-чего допёр: если в структуре будет ещё лежать какое-нибудь значение (чтобы search был полезным), тогда в терминальном узле нам не нужен массив наследников. Можно сделать а-ля:

union{
  struct HAMT* c[];
  SomeType   value;
} 

А если ещё и значение тоже размером с указатель, тогда фактически вообще бесплатно храним! Ну не прелесть ли?

Кстати, применимо вообще ко всем деревьям. Сумтип - сила.

Но главная прелесть - число итераций константно, компилятор даже может развернуть цикл. Так ещё и по скорости сопоставимо с хэшмапами, при том используя память гораздо более экономно (не надо держать кучу лишних слотов). Даже Clojure и Scala его используют для своих дефолтных мап. Правда, персистентную версию - т.е. просто иммутабельную, при вставке возвращается целое новое дерево. Даже есть Ctrie - thread-safe lock-free вариация HAMT. Звучит круто, правда? А это по факту круто. Вот прям очень. Когда-нибудь и я углублюсь в такое.

В общем, это пока самое практичное дерево среди всех ранее перечисленных.