トライ木

古典的な用途はオートコンプリート、スペルチェック、IPルーティングテーブル（最長一致）。圧縮版の基数木（radix tree）という変種もある。nginxのルーティング、Linuxカーネルの経路表、各種データベースのインデックスなどで現役だ。