在 .NET 中實現 Trie 的明智方法是什麼？

我得到了trie背後的概念。但是在實現方面我有點困惑。

我能想到的最明顯的構造Trie類型的方法是Trie維護一個 internal Dictionary<char, Trie>。事實上，我已經以這種方式編寫了一個，並且它有效，但是……這似乎有點矯枉過正。我的印像是 trie 應該是輕量級的，並且每個節點Dictionary<char, Trie>都有一個單獨的節點對我來說似乎不是很輕量級。

有沒有更合適的方法來實現我所缺少的這種結構？

---

更新：好的！根據 Jon 和 leppie 的非常有用的意見，這是我迄今為止提出的：

(1) 我有Trie類型，它有一個私有_nodes成員 type 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
{
   const int MaximumSize = 8; // ?

   internal readonly List<KeyValuePair<char, Trie>> _nodes;

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

   // Add adds to the list and returns the current instance until MaximumSize,
   // after which point it returns a LargeNodeCollection.
}

class LargeNodeCollection : INodeCollection
{
   private readonly Dictionary<char, Trie> _nodes;

   public LargeNodeCollection(SmallNodeCollection nodes, char key, Trie trie)
   { /*...*/ }

   // Add adds to the dictionary and returns the current instance.
}

(4) 當 aTrie被第一次構造時，它的_nodes成員是null。根據上述步驟，第一次呼叫Add創建一個SingleNode，隨後呼叫從那裡開始。Add

這有意義嗎？從某種意義上說，這感覺像是一種改進，它在一定程度上減少了 a 的“體積” （節點在擁有足夠數量的子節點之前Trie不再是成熟的對象）。Dictionary<char, Trie>然而，它也變得更加複雜。是不是太糾結了？我是否採取了一條複雜的路線來實現本應直截了當的事情？

好吧，您需要每個節點都有一些可以有效實現IDictionary<char, Trie>. 您可以編寫自己的自定義實現，根據它有多少子節點來改變其內部結構：

• 對於單個子節點，只使用 achar和 aTrie
• 對於較小的數字，請使用 aList<Tuple<char, Trie>>或 aLinkedList<Tuple<char,Trie>>
• 對於較大的數字，請使用Dictionary<char, Trie>

（剛剛看過 leppie 的回答，我相信這是他所說的那種混合方法。）

如果您的字元來自有限的集合（例如只有大寫拉丁字母），那麼您可以儲存一個 26 元素數組，每次查找只是

Trie next = store[c-'A']

其中 c 是目前查找字元。

引用自：https://stackoverflow.com/questions/3665317