Radix/Patricia Trie 的 STLish lower_bound 函数

Question

最近，我一直在研究 Patricia attempts，并使用一个非常好的 C++ 实现，它可以用作 STL 排序关联容器。帕特里夏尝试与普通二叉树不同，因为叶节点具有指向内部节点的反向指针。尽管如此，如果您仅通过叶节点反向指针访问内部节点，则可以通过进行中序遍历来按字母顺序遍历 Patricia trie。

这让我想到一个问题：是否可以使用 Patricia trie 实现 STL lower_bound 和 upper_bound 函数？事实上，我使用的实现确实实现了这些功能，但它们没有按预期工作。

例如：

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;

当我期望它输出 HCDA 时，它输出 BLQ。 （例如，std::set 肯定会在这里输出 HCDA。）

我给制作这个库的开发人员发了电子邮件，但从未得到回复。不管怎样，我觉得我对帕特里夏如何尝试工作有很好的理解，而且我无法弄清楚像 lower_bound 这样的东西是如何可能的。问题在于 lower_bound 似乎依赖于按字典顺序比较两个字符串的能力。由于树中不存在“GG”，因此我们需要找出哪个元素>= GG。但是 Radix/Patricia 尝试不使用字典比较来从一个节点移动到另一个节点；相反，每个节点存储一个位索引，用于对搜索关键字执行位比较。位比较的结果告诉您是向左移动还是向右移动。这使得在树中查找特定前缀变得容易。但是，如果树中不存在前缀（就像我搜索“GG”的情况一样），除了字典顺序比较之外，似乎没有任何方法可以获取 lower_bound。

我使用的 C++ 实现似乎没有正确实现 lower_bound ，这一事实证实了我的怀疑：这可能是不可能的。尽管如此，您可以按字母顺序迭代树这一事实让我认为可能有一种方法可以做到这一点。

有谁有这方面的经验，或者知道是否可以使用 Patricia Trie 实现 lower_bound 功能？

Answer 1

是的，这是可能的。我已经实现了一个变体来执行此操作，DJ Bernstein 的页面将其描述为快速操作之一。

http://cr.yp.to/critbit.html

原则上，你保持匹配前缀直到无法再匹配为止，然后转到下一个值，这就是您要查找的节点。