c# - 在 C# 中自动完成所有建议的三元搜索树

Question

我想知道是否可以修改三元搜索树来检查该词是否存在并找到所有以该词开头(或以该词结尾？)的词？ 例如 do => dog dogs 等

从这里site是示例代码。首先将所有单词加载到三叉树，然后我们可以使用方法检查单词是否存在。

public class TernaryTree
{
    private Node m_root = null;

    private void Add(string s, int pos, ref Node node)
    {
        if (node == null) { node = new Node(s[pos], false); }

        if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
        else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
        else
        {
            if (pos + 1 == s.Length) { node.m_wordEnd = true; }
            else { Add(s, pos + 1, ref node.m_center); }
        }
    }

    public void Add(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        Add(s, 0, ref m_root);
    }

    public bool Contains(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        int pos = 0;
        Node node = m_root;
        while (node != null)
        {
            int cmp = s[pos] - node.m_char;
            if (s[pos] < node.m_char) { node = node.m_left; }
            else if (s[pos] > node.m_char) { node = node.m_right; }
            else
            {
                if (++pos == s.Length) return node.m_wordEnd;
                node = node.m_center;
            }
        }

        return false;
    }
}

class Node
{
    internal char m_char;
    internal Node m_left, m_center, m_right;
    internal bool m_wordEnd;

    public Node(char ch, bool wordEnd)
    {
        m_char = ch;
        m_wordEnd = wordEnd;
    }
}

这让我在脑海中浮现:(
任何获得该词的方法都可以。但是我在那个级别的算法方面很弱..
我希望我不会重复有关此的任何问题。 如果有任何建议，我将不胜感激。

Answer 1

可以为此使用三叉树，但我不建议这样做(这样做不容易)。

我认为您可以使用两种不同的方法:

A., 使用标准的 Trie 而不是三元树，因此无论 Trie 中有多少项目，您的查找时间都将被视为常数。 C# 实现是可以实现的，但请记住，Trie 需要中等/高水平的算法知识。

B., 使用标准的排序数组 (string[])。由于您的要求只是根据前缀创建自动完成，因此将所有单词存储在 string[] 中并启动 binary search 上。 查找时间不是常数而是对数，但即使您在该数组中存储了数百万个单词，每次查找也可以在几分之一毫秒内进行测量(例如，如果您在该数组中有一百万个单词，则只有 20 次操作需要找到您正在寻找的那个)。即使二分搜索不成功，你也会有一个最接近匹配的索引(但索引将是一个负值，表明匹配不成功)。所以，在这个数组中:

A 
C
D 
E

如果您搜索 B，您将获得指向 A 的索引 0。如果您开始向上，您将看到“B”(或您的示例中的“狗”)之后的项目。

因此，即使您在二分查找后得到了完全匹配或部分匹配，也要继续列出数组中的项目，直到搜索到的关键字是 at the beginning 的字典词。