algorithm - Trie 迭代器，后缀排序

Question

我需要为 trie 实现一个迭代器。假设我有

    a
    /\
   b  c
  /\
 d  e

如果当前的iterator.state="abd"，我想有iterator.next.state="abe"，然后是"ac"。在每一层，节点按字典顺序排序（例如，在第 2 层，c在 之后b）。这也应该在 log(n) 时间内发生，其中 n 是节点数。

我能想到的一个解决方案是：考虑一个特殊情况，当每个分支具有相同的高度时。我认为一个相当酷的实现是为每个“级别”维护一个平衡的树。在询问：“abd 之后的字符串”时，当定位在 b 上时，可以在与第三级关联的树中搜索大于“b”的第一个元素，给出“abe”。

然而，由于必须创建树，这可能是不切实际的。

Answer 1

如果我正确理解了这个问题，迭代器状态可能是当前字符串和指向树中当前位置的指针。然后，移动到下一个元素：

1. 如果您当前的位置有兄弟，移动到它并用当前位置的字符替换当前字符串中的最后一个字符。

2. 否则，删除最后一个字符并上树。如果你试图从根部向上，你就完成了。否则，转到步骤 1。

因此，例如，当您在 abd（在您的示例中）时，当前字符串是“abd”并且指针指向“d”。要移动到下一个元素，请将字符串更改为“ab”，移动到兄弟节点（'e'）并将其添加到字符串中，产生“abe”。在那之后，你会因为没有兄弟姐妹而上升，然后到 b 的兄弟姐妹，产生正确的下一个值'ac'。

如您所见，最坏的情况是，这些步骤中的每一个都需要一直回到根目录才能找到兄弟节点。这就是您要的日志（n）。