最近我一直在研究 Patricia 的尝试，并使用了一个非常好的C++ 实现，它可以用作 STL 排序关联容器。Patricia 尝试与普通二叉树不同，因为叶节点具有指向内部节点的反向指针。尽管如此，如果您只通过叶节点反向指针访问内部节点，则可以通过按字母顺序遍历 Patricia trie。
这让我想到了一个问题：是否可以使用 Patricia trie实现 STLlower_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。）
我给制作这个库的开发人员发了电子邮件，但从未得到回复。无论如何，我觉得我对 Patricia 如何尝试工作有很好的理解，而且我无法弄清楚像 lower_bound 这样的东西是如何可能的。问题在于，lower_bound 似乎依赖于按字典顺序比较两个字符串的能力。由于树中不存在“GG”，我们需要找出哪个元素 >= 到 GG。但是 Radix/Patricia 尝试不使用字典比较来从一个节点移动到另一个节点；而是每个节点存储一个位索引，用于对搜索键执行位比较。位比较的结果告诉您是向左还是向右移动。这使得在树中找到特定前缀变得容易。但是如果树中不存在前缀，
我正在使用的 C++ 实现似乎没有正确实现 lower_bound 的事实证实了我的怀疑，即它可能是不可能的。尽管如此，您可以按字母顺序遍历树的事实让我认为可能有一种方法可以做到这一点。
有没有人有这方面的经验，或者知道是否可以使用 Patricia Trie 实现 lower_bound 功能？