STLish Radix/Patricia Trie的lower_bound函数

Question

最近我一直在研究Patricia尝试,并使用一个非常好的C++实现,可以用作STL Sorted Associative Container.Patricia尝试与普通二叉树不同,因为叶节点具有指向内部节点的后向指针.尽管如此,如果您只通过叶节点后向指针访问内部节点,则可以通过执行有序遍历来按字母顺序遍历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;

这会输出BLQ,当我希望它输出HCDA时.(std::set例如,肯定会在这里输出HCDA.)

我通过电子邮件发送了制作此库的开发人员,但从未收到回复.无论如何,我觉得我非常了解Patricia如何尝试工作,我无法弄清楚low_bound之类的东西是如何可行的.问题是lower_bound似乎依赖于按字母顺序比较两个字符串的能力.由于树中不存在"GG",我们需要找出哪个元素> =到GG.但Radix/Patricia尝试不使用词典比较从一个节点移动到另一个节点; 而是每个节点存储一个比特索引,用于对搜索关键字进行比特比较.位比较的结果告诉您是向左还是向右移动.这样可以很容易地在树中找到特定的前缀.但是如果树中不存在前缀,

我正在使用的C++实现似乎没有正确实现lower_bound的事实证实了我怀疑它可能是不可能的.尽管如此,你可以按字母顺序迭代树,这让我觉得可能有办法做到这一点.

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

Answer 1

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

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

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