Fast and Space Efficient Trie Searches

Разберём поиск построчно:
1. Нулевой элемент - это абсолютный корень. Из него мы берём наш первичный XBase.
2. Получаем численное значение буквы, эксплуатируя факт, что в ASCII алфавит идёт по порядку. Прибавляя его к имеющемуся XBase, получаем индекс нужного нам следующего узла.
3. Если Parent у полученного узла не совпадает с нашим base, относительно которого мы искали - значит, этот узел принадлежит другому субдереву. Следовательно, это место пустовало - наша строка не входит в дерево. В противном же случае - берём XBase этого узла как наш новый "якорь".
4. Повторяем цикл до тех пор, пока строка не кончится. Когда строка кончилась - у последнего выбранного узла XBase обязан быть NULL, что указывает на то, что такой узел - терминальный.

Рассмотрим на конкретном примере ср строками BEAR и BEG.
1. Первая буква в BEAR - B, первая буква по порядку (счёт идёт с нуля). Начинаем с нулевого узла. Его XBase - 1. Складываем 1+1=2. Узел под номером 2 действительно соответствует букве B. Его Parent=0, что соответствует нашему XBase=1. Пока всё правильно.
2. У узла под номером два XBase=4. Вторая буква в слове - E - четвёртая по порядку. Складываем, получаем узел под номером 8. Его Parent=2, значит, тут тоже всё правильно.
3. Новый XBase=9, "А" нулевая буква по счёту. У 9го узла Parent=8, правильно.
4. 9й узел даёт нам XBase=1. R - 17ая по счёту, складываем и оказываеся на узле 18. Parent=9, всё совпадает. Слово кончилось, смотрим - у 19го узла XBase=NULL, значит, строка полностью входит в дерево. Возвращаем истину.

С BEG мы повторяем первые два шага. Но теперь, мы складываем G (шестая буква по счёту) с XBase=9. У 15го узла вообще нет Parent, что явно не совпадает с Parent=8. Следовательно, такой строки в дереве нет.

Сама таблица может и выглядеть нетривиальной, однако поиск по ней всё же достаточно прост. Зато вставка заставляет искать решение для knapsack problem, что часто вычислительно дорого. Но вариация этой проблемы всплывает всегда, когда рассматривается эффективность по пространству. Правда, имея заранее известное распределение ключей, можно избежать чрезмерных трат и составить алгоритм вставки, по производительности сопоставимый с остальными разновидностями префиксных деревьев. В таком случае, мы можем заведомо размещать как минимум на расстоянии алфавита друг от друга узлы с наибольшим количеством ветвей. И, наоборот, чуть более плотно размещать те, у которых ветвей ожидается меньше.

Но такое дерево очень экономно в расчёте на размер узла: int в С всегда занимает 32 бита, и потому структура в моём примере будет весить восемь байт, что на 64-битной архитектуре - одно машинное слово. Правда, присутствует крайне весомый минус: моё дерево не умеет одновременно хранить две строки, где одна целиком является префиксом другой. То есть, узел не может хранить одновременно и EOL, и продолжение. Это можно решить либо однобитным флагом Term, либо, если всё-таки дерево сопоставляет строкам произвольные значения, выбрать из множества наш местный NULL (или одолжить у множества один бит). Но вне зависимости от выбора, выравнивание докинет ещё одно машинное слово, а это уже суммарно 16 байт (или 3 машинных слова = 12 байт на 32х битной архитектуре). Что, в прочем, всё ещё весьма экономно. Да и для ускорения вставки можно добавить дополнительных пару полей. Ну, или всё-таки уговорить компилятор не выравнивать, хотя я бы тогда уже использовал новое пространство с честью.