В последнее время я изучаю попытки Патриции и работаю с действительно хорошей реализацией C ++ , которую можно использовать в качестве сортированного STL ассоциативного контейнера.Попытки Патрисии отличаются от обычных двоичных деревьев, потому что конечные узлы имеют обратные указатели, которые указывают на внутренние узлы.Тем не менее, можно пройти путь Патриции в алфавитном порядке, выполнив обход в порядке, если вы посещаете внутренние узлы только через указатели на листовые узлы.
Что подводит меня к вопросу: возможно лиреализовать функции STL lower_bound и upper_bound с помощью функции Patricia?Реализация, которую я использую , на самом деле реализует эти функции, но они не работают должным образом.
Например:
typedef uxn::patl::trie_set<std::string> trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");
trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;
Это выводит BLQ, когда я ожидаю, что он выведет HCDA.(Например, std::set, безусловно, будет выводить здесь HCDA.)
Я написал разработчику, который создал эту библиотеку, но не получил ответа.Несмотря на это, я чувствую, что у меня достаточно хорошее понимание того, как Патрисия пытается работать, и я не могу понять, как что-то вроде lower_bound было бы возможно.Проблема в том, что lower_bound полагается на способность лексикографически сравнивать две строки.Поскольку «GG» не существует в дереве, нам нужно выяснить, какой элемент> = для GG.Но Radix / Patricia пытается не использовать лексикографическое сравнение для перемещения от узла к узлу;скорее, каждый узел хранит битовый индекс, который используется для сравнения битов ключа поиска.Результат сравнения битов говорит вам, двигаться ли влево или вправо.Это позволяет легко найти определенный префикс в дереве.Но если префикс не существует в дереве (как в случае с моим поиском «GG»), кажется, нет никакого способа, кроме лексикографического сравнения, получить lower_bound.
Тот факт, что используемая мной реализация C ++, похоже, не реализует lower_bound должным образом, подтверждает мое подозрение, что это может быть невозможно.Тем не менее, тот факт, что вы можете перебирать дерево в алфавитном порядке, заставляет меня думать, что может быть способ сделать это.
Кто-нибудь имеет опыт с этим или знает, возможно ли реализовать функцию lower_boundс Патрицией Три?