差分
このページの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次元配列で持つのはできない。 | ||
| 行 18: | 行 19: | ||
| Pythonではクラスは読みやすいコードにはなるが生成コストが重い（と思う、要確認だが）ので、速度を気にするなら配列や辞書をインスタンス替わりに使う実装となる。 | Pythonではクラスは読みやすいコードにはなるが生成コストが重い（と思う、要確認だが）ので、速度を気にするなら配列や辞書をインスタンス替わりに使う実装となる。 | ||
| + | |||
| + | 目的によって、ノードに持たせる値や実装方法は変化する。 | ||
| =====Binary Trie===== | =====Binary Trie===== | ||
