Конечно можем. Всё-таки и 2+2=5, если взять достаточно большой 2.
Radix trie, оно же префиксное дерево II
Спойлер - radix trie это compressed m-way trie.
Спойлер 2 - этот принцип прекрасно применим к вообще всем остальным описанным деревьям. Помимо, наверное, АСТ. Radix trie - это скорее обобщённый термин для сжатых деревьев в принципе.
Давайте предположим, у нас строки формируют нормальное распределение. Это хороший кейс, потому что в множестве ключей довольно много общих префиксов, следовательно - больше потенциальной экономии. А дополнительная сладость здесь - если строки в субдеревьях чаще имеют длинный общий префикс (от 4 символов), то мы можем сразу по нескольку символов за раз и сверять, что сильно уменьшает глубину. То есть - заменить
char c на char* c. Это и меньше обращений к памяти, и меньше ветвлений, и АЛУ больше работы производят - больше байт за такт перелопачивается. Получится что-то вроде:struct Radix{
bool term;
char clen;
char* prefix;
struct Radix* c[];
}
bool search(struct Radix* node, char* str) {
loop: while (*str) {
for (int i = 0; i < node->clen; i++)
if (int p = lcp(str, node->c[i]->prefix)) {
node = node->c[i];
str = str[p:];
continue loop;
}
return false;
}
// str isn't in the trie if the last-visited
// node isn't terminal.
return node->term;
}(Где
lcp(s1,s2) - это старая-добрая длина общего префикса двух строк).Кстати, то самое моё дерево для динамического роутинга в индиге примерно так же и устроено.
Поиск стал ещё обскурнее, но суть осталась прежней: спускаемся по дереву, откусывая общий префикс и беря субдерево из наследников (каждый наследник является самодостаточным корневым узлом для своего дерева). Но самое классное, что нам больше необязательно держать NULL'ы в children, теперь у нас есть просто динамический массив с линейным поиском по оному. Что, конечно, бьёт для "широких" деревьев, когда в массиве будут все 256 элементов (каждая строка начинается с уникального байта). Но если есть возможность держать массив упорядоченным, то мы обратно возвращаемся к бинарному поиску. Словно змея, поедающая саму себя.
Вставка, в общем-то, может тоже выглядеть слегка обскурной, однако иронично, что с поиском у них есть общий "префикс": сначала мы ищем, на каком узле строка перестаёт входить в дерево. То есть, какая её часть уже находится в дереве. И потом уже остаётся либо прибавить наследника существующему узлу (как же это пошло), либо, если префикс узла не полностью совпадает с префиксом строки, то разбить такой узел надвое. И будет у него два наследника: исходный узел, просто с чутка более коротким префиксом, и новый, который будет держать остаток нашей строки и являться терминальным.
Храня сразу по несколько символов в одном узле, одновременно сильно уменьшается глубина дерева, что по всем параметрам хорошо. Но увы, так хорошо на практике выходит далеко не всегда. Если строки распределены достаточно униформно, чтобы их общий префикс был в среднем пару символов, тогда мы сильно теряем в эффективности по пространству, храня чрезмерно информации. Ну и инструкций выполняется больше, чем нужно. Поэтому существуют и другие способы.
Ternary Search Tree (TST)
Предикат в тернарном дереве, отвечающий за то, в какую сторону дальше идти, определён как "больше/равно/меньше" (в противовес просто "больше/равно" у бинарного). По аналогии с
strcmp(s1,s2) в С, которая возвращает не логический двоичный флаг, а тернарный - {-1, 0, 1} для s1<s2, s1==s2, s1>s2 соответственно.Весь фокус здесь - это взять наш исходный
struct Trie, но заменить children на такое тернарное дерево. Пустые вхождения в children - это, следовательно, несуществующие пути в дереве - а, значит, и память на них расходоваться не будет. В этом случае тернарное дерево показывает себя идеально, потому что может составлять равенства символов - в дополнение к бинарному, которое предоставляет только неравенства. С бинарным пришлось бы заниматься не самой приятной разновидностью акробатики.