[解決済み] トライ式と基幹トライ式のデータ構造の違いは何ですか？

質問

このような場合 トライ と 底面トライ のデータ構造は同じものですか？

同じものでないとすると、radix trie (別名 Patricia trie)の意味は何ですか？

どのように解決するのですか？

基数木はトライ（trie）を圧縮したものです。トライ式では各辺に1文字ずつ書きますが、PATRICIA木（または基数木）では単語全体を格納します。

今、次のような単語があったとします。 hello , hat と have . に格納するには トライ に格納する場合、次のようになります。

    e - l - l - o
  /
h - a - t
      \
       v - e

そして、9つのノードが必要です。ノードに文字を配置しましたが、実際はエッジにラベルを付けています。

基数木では

            *
           /
        (ello)
         /
* - h - * -(a) - * - (t) - *
                 \
                 (ve)
                   \
                    *

で、必要なノードは5つだけです。上の図では、アスタリスクがノードです。

つまり、全体として、基数木は より少ないメモリ しかし、実装するのはより困難です。それ以外の点では、両者のユースケースはほとんど同じです。