はトライそして基数トライデータ構造は同じものですか?
同じでない場合、基数トライ (別名パトリシアトライ) の意味は何ですか?
ベストアンサー1
基数木はトライの圧縮バージョンです。トライでは各辺に 1 つの文字を書き込みますが、パトリシア木 (または基数木) では単語全体を格納します。
さて、単語hello、hat、 があると仮定しますhave。これらをトライ、次のようになります。
e - l - l - o
/
h - a - t
\
v - e
必要なノードは 9 個です。ノードに文字を配置しましたが、実際にはエッジにラベルを付けています。
基数ツリーでは、次のようになります。
*
/
(ello)
/
* - h - * -(a) - * - (t) - *
\
(ve)
\
*
必要なノードは 5 つだけです。上の図では、ノードはアスタリスクです。
つまり、基数木はメモリが少ないただし、実装はより困難です。それ以外では、両方の使用例はほぼ同じです。