前面，我們介紹了Trie樹結(jié)構(gòu)，它的實現(xiàn)簡單但空間效率低。如果要支持26個英文字母，每個節(jié)點就要保存26個指針，假若我們還要支持國際字符、標點符號、區(qū)分大小寫，內(nèi)存用量就會急劇上升，以至于不可行。
由于節(jié)點數(shù)組中保存的空指針占用了太多內(nèi)存，我們遇到的困難與此有關(guān)，因此可以考慮改用其他數(shù)據(jù)結(jié)構(gòu)去代替，比如用hash map。然而，管理成千上萬個hash map肯定也不是什么好主意，而且它使數(shù)據(jù)的相對順序信息丟失，所以我們還是去看看另一種更好解法吧——Ternary Tree。
接下來，我們將介紹三叉搜索樹，它結(jié)合字典樹的時間效率和二叉搜索樹的空間效率優(yōu)點。
Ternary Tree的實現(xiàn)
三叉搜索樹使用了一種聰明的手段去解決Trie的內(nèi)存問題（空的指針數(shù)組）。為了避免多余的指針占用內(nèi)存，每個Trie節(jié)點不再用數(shù)組來表示，而是表示成“樹中有樹”。Trie節(jié)點里每個非空指針都會在三叉搜索樹里得到屬于它自己的節(jié)點。
接下來，我們將實現(xiàn)三叉搜索樹的節(jié)點類，具體實現(xiàn)如下：
/// <summary>
/// The node type.
/// Indicates the word completed or not.
/// </summary>
public enum NodeType
{
COMPLETED,
UNCOMPLETED
};
/// <summary>
/// The tree node.
/// </summary>
public class Node
{
internal char Word { get; set; }
internal Node LeftChild, CenterChild, RightChild;
internal NodeType Type { get; set; }
public Node(char ch, NodeType type)
{
Word = ch;
Type = type;
}
}由于三叉搜索樹包含三種類型的箭頭。第一種箭頭和Trie里的箭頭是一樣的，也就是圖2里畫成虛線的向下的箭頭。沿著向下箭頭行進，就意味著“匹配上”了箭頭起始端的字符。如果當(dāng)前字符少于節(jié)點中的字符，會沿著節(jié)點向左查找，反之向右查找。
接下來，我們將定義Ternary Tree類型，并且添加Insert()，F(xiàn)ind()和FindSimilar()方法。
/// <summary>
/// The ternary tree.
/// </summary>
public class TernaryTree
{
private Node _root;
////private string _prefix;
private HashSet<string> _hashSet;
/// <summary>
/// Inserts the word into the tree.
/// </summary>
/// <param name="s">The word need to insert.</param>
/// <param name="index">The index of the word.</param>
/// <param name="node">The tree node.</param>
private void Insert(string s, int index, ref Node node)
{
if (null == node)
{
node = new Node(s[index], NodeType.UNCOMPLETED);
}
if (s[index] < node.Word)
{
Node leftChild = node.LeftChild;
this.Insert(s, index, ref node.LeftChild);
}
else if (s[index] > node.Word)
{
Node rightChild = node.RightChild;
this.Insert(s, index, ref node.RightChild);
}
else
{
if (index + 1 == s.Length)
{
node.Type = NodeType.COMPLETED;
}
else
{
Node centerChild = node.CenterChild;
this.Insert(s, index + 1, ref node.CenterChild);
}
}
}
/// <summary>
/// Inserts the word into the tree.
/// </summary>
/// <param name="s">The word need to insert.</param>
public void Insert(string s)
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentException("s");
}
Insert(s, 0, ref _root);
}
/// <summary>
/// Finds the specified world.
/// </summary>
/// <param name="s">The specified world</param>
/// <returns>The corresponding tree node.</returns>
public Node Find(string s)
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentException("s");
}
int pos = 0;
Node node = _root;
_hashSet = new HashSet<string>();
while (node != null)
{
if (s[pos] < node.Word)
{
node = node.LeftChild;
}
else if (s[pos] > node.Word)
{
node = node.RightChild;
}
else
{
if (++pos == s.Length)
{
_hashSet.Add(s);
return node.CenterChild;
}
node = node.CenterChild;
}
}
return null;
}
/// <summary>
/// Get the world by dfs.
/// </summary>
/// <param name="prefix">The prefix of world.</param>
/// <param name="node">The tree node.</param>
private void DFS(string prefix, Node node)
{
if (node != null)
{
if (NodeType.COMPLETED == node.Type)
{
_hashSet.Add(prefix + node.Word);
}
DFS(prefix, node.LeftChild);
DFS(prefix + node.Word, node.CenterChild);
DFS(prefix, node.RightChild);
}
}
/// <summary>
/// Finds the similar world.
/// </summary>
/// <param name="s">The prefix of the world.</param>
/// <returns>The world has the same prefix.</returns>
public HashSet<string> FindSimilar(string s)
{
Node node = this.Find(s);
this.DFS(s, node);
return _hashSet;
}
}和Trie類似，我們在TernaryTree 類中，定義了Insert()，F(xiàn)ind()和FindSimilar()方法，它包含兩個字段分別是：_root和_hashSet，_root用來保存Trie樹的根節(jié)點，我們使用_hashSet保存前綴匹配的所有單詞。
由于三叉搜索樹每個節(jié)點只有三個叉，所以我們在進行節(jié)點插入操作時，只需判斷插入的字符與當(dāng)前節(jié)點的關(guān)系（少于，等于或大于）插入到相應(yīng)的節(jié)點就OK了。
我們使用之前的例子，把字符串AB，ABBA，ABCD和BCD插入到三叉搜索樹中，首先往樹中插入了字符串AB，接著我們插入字符串ABCD，由于ABCD與AB有相同的前綴AB，所以C節(jié)點都是存儲到B的CenterChild中，D存儲到C的CenterChild中；當(dāng)插入ABBA時，由于ABBA與AB有相同的前綴AB，而B字符少于字符C，所以B存儲到C的LeftChild中；當(dāng)插入BCD時，由于字符B大于字符A，所以B存儲到C的RightChild中。
圖4三叉搜索樹
我們注意到插入字符串的順序會影響三叉搜索樹的結(jié)構(gòu)，為了取得最佳性能，字符串應(yīng)該以隨機的順序插入到三叉樹搜索樹中，尤其不應(yīng)該按字母順序插入，否則對應(yīng)于單個Trie
節(jié)點的子樹會退化成鏈表，極大地增加查找成本。當(dāng)然我們還可以采用一些方法來實現(xiàn)自平衡的三叉樹。
由于樹是否平衡取決于單詞的讀入順序，如果按排序后的順序插入，則該方式生成的樹是最不平衡的。單詞的讀入順序?qū)τ趧?chuàng)建平衡的三叉搜索樹很重要，所以我們通過選擇一個排序后數(shù)據(jù)集合的中間值，并把它作為開始節(jié)點，通過不斷折半插入中間值，我們就可以創(chuàng)建一棵平衡的三叉樹。我們將通過方法BalancedData()實現(xiàn)數(shù)據(jù)折半插入，具體實現(xiàn)如下：
/// <summary>
/// Balances the ternary tree input data.
/// </summary>
/// <param name="file">The file saves balanced data.</param>
/// <param name="orderList">The order data list.</param>
/// <param name="offSet">The offset.</param>
/// <param name="len">The length of data list.</param>
public void BalancedData(StreamWriter file, IList<KeyValuePair<int, string>> orderList, int offSet, int len)
{
if (len < 1)
{
return;
}
int midLen = len >> 1;
// Write balanced data into file.
file.WriteLine(orderList[midLen + offSet].Key + " " + orderList[midLen + offSet].Value);
BalancedData(file, orderList, offSet, midLen);
BalancedData(file, orderList, offSet + midLen + 1, len - midLen - 1);
}上面，我們定義了方法BalancedData()，它包含四個參數(shù)分別是：file，orderList，offSet和len。File寫入平衡排序后的數(shù)據(jù)到文本文件。orderList按順序排序后的數(shù)據(jù)。offSet偏移量。Len插入的數(shù)據(jù)量。
同樣我們創(chuàng)建一棵三叉搜索樹，然后把兩千個英語單詞插入到三叉搜索樹中，最后我們查找前綴為“ab”的所有單詞包括前綴本身。
public class Program
{
public static void Main()
{
// Creates a file object.
var file = File.ReadAllLines(Environment.CurrentDirectory + "//1.txt");
// Creates a trie tree object.
var ternaryTree = new TernaryTree();
var dictionary = new Dictionary<int, string>();
foreach (var item in file)
{
var sp = item.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
ternaryTree.Insert(sp.LastOrDefault().ToLower());
}
Stopwatch watch = Stopwatch.StartNew();
// Gets words have the same prefix.
var similarWords = ternaryTree.FindSimilar("ab");
foreach (var similarWord in similarWords)
{
Console.WriteLine("Similar word: {0}", similarWord);
}
watch.Stop();
Console.WriteLine("Time consumes: {0} ms", watch.ElapsedMilliseconds);
Console.WriteLine("Similar word: {0}", similarWords.Count);
Console.Read();
}
}
圖5匹配結(jié)果
我們在1.txt文本文件中通過正則表達式（^:z ab+）查找前綴為ab的所有單詞，剛好就是上面9個單詞。
本文導(dǎo)航
- 第1頁: 首頁
- 第2頁: Trie樹的實現(xiàn)
- 第3頁: Ternary Tree的定義和實現(xiàn)
- 第4頁: Ternary Tree的應(yīng)用
喜歡 
頂
難過
囧
圍觀
無聊
