"Сопротивление бесполезно!" Крикнули 40000 вольт. А теперь представьте, какие были остальные варианты вступления, если в конце я выбрал именно этот.
Radix trie, оно же префиксное дерево
Арность (несмешно) - в общем случае описывает количество аргументов либо операндов, принимаемых функцией или оператором. (Технически, ранг матрицы тоже сюда косвенно относится, да.)
В случае деревьев, арность сообщает число исходящих рёбер из узла (не забываем, что узел есть дерево, дерево есть узел; играет роль только тот узел, который мы прямо сейчас воспринимаем за корень). В случае бинарных, логично, это фиксировано два исходящих ребра. Тернарных - три. Можно произвольно много тоже, такое называется variable-arity, или же просто variadic (откуда оно и пошло в С). Но смысл здесь - с арностью можно весело играться. Например, взять дерево с арностью, равной размеру алфавита - и вот мы уже можем искать следующий узел, чей порядковый номер соответствует оному искомой литеры в алфавите. Такое дерево называется m-way trie.
Рассмотрим примитивный пример с деревом, определённом для английского алфавита в нижнем регистре:
struct Trie{
char c;
struct Trie* children[26];
}
bool search(struct Trie* trie, char* str) {
for (; *str; str++)
if ((trie = trie->children[*str-'a']) == NULL)
return false;
return trie->children[0] != NULL;
}Поиск здесь отвечает лишь за существование строки в дереве и останавливается, либо когда у текущего узла нет наследников, соответствующих нужной букве в строке (вербозный иф), либо когда строка кончается (тогда у узла должен быть non-NULL наследник для 0, он же стандартный терминатор С-строки, он же в роли флага term). Чтобы ассоциировать значения, достаточно просто добавить атрибут с нужным типом, и возвращать его значение у терминальных узлов. Для обобщения поиска, дабы возвращать произвольное ассоциированное значение со строкой, а не просто проверять её вхождение - достаточно лишь добавить соответствующий атрибут к структуре, и возвращать в конце поиска именно его.
Вставка тривиальна: мы траверсим дерево до тех пор, пока в строке не встретится символ, для которого пути дальше уже нет, т.е. точку строки, в которой она отличается от всех остальных вхождений.
Но тут я бы остановился и сделал передышку. При такой вставке, я неявно предполагаю аллоцировать отдельно каждый отдельный узел. Если дерево динамическое (после построения ключи в него могут добавляться или удаляться), тогда такая вставка может быть крайне неприятной по производительности, особенно если нужно вставлять много новых символов. Тут сразу интуитивно приходит мысль аллоцировать сразу по 128-1024 узлов за раз, и потом их постепенно оттуда брать для вставки, коль уж дорог сам факт выделения памяти, а не её количество. Сразу развивая идею, приходим к тому, что дерево в принципе можно целиком всунуть в один большой массив. Всё, что изменится - это вместо
struct Trie* у нас будет uint index, хранящий индекс на следующий узел в массиве. int/uint в С занимают фиксировано 32 бита что на х32, что на х64 архитектуре - а это значит, что с исчерпывающим потолком в 4.2млрд узлов в дереве, мы выигрываем лишние 4 байта. Размер структуры на х64 архитектуре, конечно, от этого не уменьшится, потому что выравнивание - но в них взамен можно хранить дополнительную информацию, которая в противном случае занимала бы дополнительное машинное слово. А для деревьев с бОльшим количеством ветвей, даже такая мелочь уже может срезать очень много потребления памяти.Ещё из плюсов деревьев в массивах - узлы лежат в ОЗУ последовательно, благодаря чему они лучше умещаются в кэшлинии. Вот только, имея узел, в котором массив из 26 чисел - даже один такой в кэшлинию едва ли влезет. И тогда стоит задуматься о том, как хранить именно этот массив более эффективно, а не о том, как выиграть лишних 4-8 байт.
Имеем: статический массив, частично состоящий из нулей. Как потом окажется, очень многие будут состоять преимущественно из нулей. Это точно можно как-то соптимизировать.