訂購的線索/基數樹

Question

當我仰望嘗試次數和基數樹節點的孩子，如 http://en.wikipedia.org/wiki/Compact_prefix_tree和 http://en.wikipedia.org/wiki/Trie， 我看到一個節點的孩子們的字典排序沒有具體的事情。

所以，在this例如（唯一的數字在頁面上） 根的孩子可以更好地從左到右排序爲'A'，'我'，'噸'。

嘗試/基樹用於檢索 - 不適用於頻繁更新。所以，這種排序並不會花費太多，特別是在稀有樹更新上，算法上簡單/直接，並且在查找/檢索值時增加了一些速度。

我失蹤了什麼？

我正在尋找/反對這個論據。

Answer 1

我假設你想訂購孩子，以便你可以更快地搜索它們。不過，我想你會發現，給定節點的孩子數量非常少 - 足夠小，二進制搜索和順序搜索之間的差異並不重要。或者甚至可能很小，以至於順序搜索比二分搜索更快。

例如，按字母順序排列字母'q'的孩子是沒有意義的，因爲它的孩子很少。對'q'後面的幾個字母進行二進制搜索會比順序搜索慢。按頻率排序兒童更有意義。 '你'會是第一個孩子，而選擇的項目比其他任何人都要頻繁得多。

我沒有在我面前的兩個bigram頻率表，但我懷疑你會發現，在大多數情況下，某個特定字母的可能孩子的數量並不能證明詞典排序的正確性，並且按頻率排序導致更好的性能。可能的例外是在詞的開頭，但即使如此，我懷疑按頻率排序會更有意義。

你可以建立這樣一個trie並檢查節點。查看典型節點有多少個孩子，並查看頻率是多少。