http://en.wikipedia.org/wiki/Compact_prefix_treeや http://en.wikipedia.org/wiki/Trieなどのトライと基数ツリーを調べる と、ノードの子。
したがって、たとえば、このトライ (ページの右上にある唯一の図) では、ルートの子は、左から右に「A」、「i」、「t」の順序で並べることができます。
試行/基数ツリーは検索用であり、頻繁な更新用ではありません。そのため、この種の順序付けは、特にまれなツリーの更新ではあまりコストがかからず、アルゴリズム的に簡単/簡単で、値の検索/取得中の速度にいくらか追加されます。
私は何が欠けていますか？
これに関する/反対の議論を探しています。
より迅速に検索できるように、子を並べ替えたいと思います。ただし、特定のノードの子の数はかなり少ないことがわかると思います。二分探索と逐次探索の違いが実際には問題にならないほど小さいのです。または、非常に小さいため、逐次検索は二分検索よりも高速です。
たとえば、文字 'q' の子を辞書順に並べてもまったく意味がありません。「q」に続く数文字のバイナリ検索は、順次検索よりも遅くなります。子を頻度順に並べた方がはるかに理にかなっています。'u' は最初の子であり、他のどの項目よりもはるかに頻繁に選択される項目です。
目の前にバイグラム頻度の表はありませんが、ほとんどの場合、特定の文字の可能性のある子の数は辞書式順序付けを正当化するものではなく、頻度による順序付けがはるかに優れていることがわかると思いますパフォーマンス。可能性のある例外は単語の先頭にありますが、その場合でも、頻度で並べた方がはるかに理にかなっていると思います.
このようなトライを作成して、ノードを調べることができます。典型的なノードが持つ子の数を確認し、頻度を確認します。