【きすうぎ】
基数木（Radix Tree） とは？
公開:
💡 分かれ道のない文字の一本道を、ひとまとめに
キーの文字やビットをたどって探す木構造。ここでは、トライ木の分岐しない経路をまとめ、共通の接頭辞を省スペースで扱う圧縮基数木を説明する。
📌 このページのポイント
- 共通の接頭辞を共有し、分岐しない経路を圧縮する
- 途中まで同じキーの追加では、必要な場所で経路を分割する
- 検索の仕事量はキーの長さや子ノードの探し方にも依存する
ひよこ トライ木とは別物なの？
ひよこ どんなふうにまとめるの？
ペンギン先生 carとcatだけなら、共通の「ca」をひとまとめにし、その先を「r」と「t」に分けられるよ。各経路の文字をつなぐと元のキーになる。単語の終わりを示す情報も持つので、carとcartのように一方が他方の接頭辞でも区別できるんだ。
ひよこ あとから別の単語を追加したら？
ペンギン先生 たとえばcaの途中で分かれるキーが来たら、圧縮した経路をその位置で分割するよ。削除後に分岐がなくなれば再びまとめる実装もある。節約できる一方で、こうした更新処理は単純なトライ木より複雑になりやすいんだ。
ひよこ キーの件数が増えても検索は一瞬？
ペンギン先生 一瞬とは限らないよ。圧縮した文字列も照合する必要があり、子ノードの選び方にもコストがある。キー長をLとしたO(L)という説明も、その照合や分岐選択の前提を置いたものなんだ。接頭辞検索や辞書順の走査が必要な場面で検討したいね。
もっと詳しく知りたい人へ
基数木という名前なら、すべて同じ実装ですか？
いいえ。文献やライブラリにより、何ビットずつ分岐するか、経路を圧縮するか、ノードをどう表すかが異なります。このページの図は文字列キーを使う圧縮形の例です。
まとめ：ざっくりこれだけ覚えればOK！
「基数木（Radix Tree）」って出てきたら「共通の書き出しを共有し、一本道をまとめる検索の木」と思えればだいたいOK！