如何有效地实现三元搜索尝试的 floor() 和 ceil() 操作？

Question

我一直在研究 Robert Sedgewick 的书中的 TST（三元搜索尝试），这是他的实现的 link：http://algs4.cs.princeton.edu/52trie/TST.java.html

因此，由于 TST 是 BST 的修改版，我想知道如何有效地实施下限和上限操作。（它们没有在他的代码中的任何地方实现）。我想过的所有方法都是乱七八糟的，效率不高。

Answer 1

是的，您可以在 TST 上高效地执行这些操作。

暂时将 TST 视为普通的 trie 树可能会有所帮助。我们可以弄清楚如何在 trie 中执行前驱和后继搜索（你称之为下限和上限），然后调整这些方法以在 TST 中工作。为简单起见，我只讨论后继搜索，尽管这也可以很容易地适用于先行搜索。

假设你想找到不晚于某个单词 w 的字典序第一个单词。首先在 trie 中搜索单词 w。如果你发现 w 是 trie 中的一个词，你就大功告成了。

否则，可能会发生一些事情。首先，您可能会发现您最终到达了 trie 中对应于不是单词的 w 的某个节点。在这种情况下，您知道 w 是 trie 中某个单词的前缀，因此要找到后继者，您需要找到字典序上第一个以 w 作为前缀的字符串。要做到这一点，请继续沿着 trie 查找，始终尽可能向左走，直到您最终找到与单词对应的节点。

其次，您可能会在尝试搜索 w 时掉出 trie。在这种情况下，您将在路径中读取一些 w 前缀。在那种情况下，你一定已经在你试图读取字符 c 的某个节点处结束，但没有标记为 c 的边。在这种情况下，查看此节点的其他边并找到第一个字符在 c 之后的边。如果存在，就接受它，然后通过始终尽可能向左移动来找到该 subtrie 中按词典顺序排列的第一个单词。如果不是，备份trie中的一个节点，重复这个过程。

总而言之，递归算法如下所示：

function findSuccessor(root, remainingChars) {
    /* If we walked off the trie, we need to back up. Return null
     * to signal an error.
     */
    if (root == null) return null;

    /* If we're on the trie and out of characters, we're either done
     * or we need to find the cheapest way to extend this path.
     */
    if (remainingChars == "") {
        if (root is a word) {
            return root;
        } else {
            return goLeftUntilYouFindAWord(root);
        }
    }

    /* Otherwise, keep walking down the trie. */
    let nextLetter = remainingChars[0];

    /* If there is a child for this letter, follow it and see
     * what happens.
     */
    if (root.hasChildFor(nextLetter)) {
        let result = findSuccessor(root.child(nextLetter), nextLetter.substring(1));

        /* If we found something, great! We're done. */
        if (result != null) return result;
    }

    /* If we're here, we either (a) have no transition on this
     * character or (b) we do, but the successor isn't there. In
     * either case, figure out which child we have that comes right
     * after nextLetter and go down there if possible.
     */
    char letterAfter = node.firstChildAfter(nextLetter);

    /* If no such child exists, there is no successor in this
     * subtrie. Report failure.
     */
    if (letterAfter == null) return null;

    /* Otherwise, get the first word in that subtrie. */
    return goLeftUntilYouFindAWord(node.child(letterAfter));
}

那么这究竟是如何转化为 TST 案例的呢？好吧，我们需要能够检查 child 是否存在 - 这是我们可以通过常规 BST 查找来做的事情 - 我们还需要能够找到特定级别的字符之后的第一个字符- 我们可以通过 BST 中的后继搜索来做到这一点。我们还需要能够找到子树中的第一个单词，我们可以通过始终在 child 指针的 BST 中向左走来做到这一点。

总的来说，这里的运行时间为 O(L log |Σ|)，其中 L 是 trie 中最长字符串的长度，Σ 是允许字符集。这样做的原因是，在最坏的情况下，我们必须沿着 TST 一直下降以找到后继者，并且每次我们这样做时，我们都会进行恒定数量的 BST 操作，每个操作都需要时间 O(log |Σ |) 因为至多有|Σ| child 每个节点的指针。

如果您想查看具体的实现，我有一个 C++ implementation of a TST 实现了 lower_bound 和 upper_bound，它们与您要执行的操作密切相关描述。

如何有效地实现三元搜索尝试的 floor() 和 ceil() 操作？

How to implement floor() and ceil() operations for ternary search tries efficiently?

algorithm

tree

time-complexity

binary-search-tree

data-structures