トライ構造

trieと書く

https://gyazo.com/3e1f97a8f340bbb6892f8442a4c060c8

既に述べたようにトライ木は2分探索木に比較して様々な利点がある。トライ木はハッシュテーブルの代替としても使用でき、次のような利点がある:

実測すると2分探索木より速いのと、ハッシュ関数とか衝突とか考えなくていいのと、キーの辞書順を自動生成できるのと

デメリットは、言語にデフォで用意されていない、メモリ効率悪い、keys()みたいなキー一覧の取り出しがキツイ

応用

トライ木の典型的な応用として辞書の格納がある。例えば、携帯電話などで使われている