利点と欠点（2分探索木との比較）
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「利点と欠点（2分探索木との比較）」の解説
2分探索木と比較したトライ木の主な利点: キー検索が高速である。長さ m のキー検索の時間計算量は最悪でも O(m) である。2分探索木での時間計算量は O(log n) である。ただしn は木を構成するノード数である（木の深さに応じた時間がかかり、2分探索木の深さは n の対数となる）。トライ木が検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。 多数の短い文字列を格納する場合にはトライ木の方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーがノードが共有するためである。 トライ木は最も長いプレフィックスとマッチするよう探索を進められるので、最も長いプレフィックスが共通なキーを効率的に捜せる。また、そのような共通プレフィックスに対応したノードに新たな値を格納できる。 トライ木は木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある（平衡2分探索木参照）。 トライ木の欠点: トライ木はキーの順序を与えるが、辞書順でなければならない。 トライ木は入力ノード数に対して深さが極めて大きくなりうる。例えば、少数の非常に長い文字列を格納するトライ木などである（この場合、パトリシア木が適する）。 トライ木のアルゴリズムは単純な2分探索木よりも複雑である。 データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。 トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる（つまり偏りがある）。 トライ木はキーの長さが可変でキー検索が失敗する場合があるとき（そのキー文字列がキーとされていない場合）、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である（図の例で言えば、"i" のノードと "in" のノードをまとめる）。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。
※この「利点と欠点（2分探索木との比較）」の解説は、「トライ (データ構造)」の解説の一部です。
「利点と欠点（2分探索木との比較）」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
- 利点と欠点のページへのリンク
