相关疑难解决方法(0)

我得到了一个trie背后的概念.但是在实施方面我有点困惑.

我认为构建Trie类型最明显的方法是Trie维护内部Dictionary<char, Trie>.事实上,我已经用这种方式编写了一个,并且它可以工作,但是......这看起来有点过分了.我的印象是trie应该是轻量级的,并且每个节点都有一个单独的Dictionary<char, Trie>对我来说似乎不是很轻量级.

有没有更合适的方法来实现我缺少的这种结构？

更新:好的!基于Jon和leppie的非常有用的输入,这是我到目前为止所提出的:

(1)我有Trie类型,它有一个_nodes类型的私有成员Trie.INodeCollection.

(2)Trie.INodeCollection界面有以下成员:

interface INodeCollection
{
    bool TryGetNode(char key, out Trie node);
    INodeCollection Add(char key, Trie node);
    IEnumerable<Trie> GetNodes();
}

(3)此接口有三种实现方式:

class SingleNode : INodeCollection
{
    internal readonly char _key;
    internal readonly Trie _trie;

    public SingleNode(char key, Trie trie)
    { /*...*/ }

    // Add returns a SmallNodeCollection.
}

class SmallNodeCollection : INodeCollection …