差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:trie [2019/02/27] – ikatakos | programming_algorithm:data_structure:trie [2019/02/27] – ikatakos | ||
|---|---|---|---|
| 行 13: | 行 13: | ||
| * 互いに似ている多数の短い文字列の管理に特に向く | * 互いに似ている多数の短い文字列の管理に特に向く | ||
| * 少数の長い文字列の管理もできるが、パフォーマンスは落ちる。それにはパトリシア木などを用いる | * 少数の長い文字列の管理もできるが、パフォーマンスは落ちる。それにはパトリシア木などを用いる | ||
| + | * 辞書的順序が変化しても最大最小や $k$ 番目を検索できる | ||
| 一方、二分探索木やBinaryIndexedTreeのようにindexと親子関係を綺麗に対応させることはできないので、データ全体を1次元配列で持つのはできない。 | 一方、二分探索木やBinaryIndexedTreeのようにindexと親子関係を綺麗に対応させることはできないので、データ全体を1次元配列で持つのはできない。 | ||
