7

「基数ツリー」の全会一致の定義を見つけることは困難ですが、最も受け入れられている基数ツリーの定義は、圧縮されたプレフィックス ツリーであることを示しています。私が理解するのに苦労しているのは、この場合の「基数」という用語の意味です。圧縮されたプレフィックス ツリーがそのように命名され (つまり、基数ツリー)、圧縮されていないプレフィックス ツリーが基数ツリーと呼ばれないのはなぜですか?

4

1 に答える 1

2

ウィキペディアはこれに答えることができます、https://en.wikipedia.org/wiki/Radix :

数学的数値システムでは、基数または基数は、ゼロを含む一意の桁数であり、位置数値システムで数値を表すために使用されます。たとえば、10 進法 (今日使用されている最も一般的なシステム) の場合、基数は 10 です。これは、0 から 9 までの 10 桁を使用するためです。

およびツリーhttps://en.wikipedia.org/wiki/Radix_tree :

唯一の子である各ノードがその親とマージされる空間最適化トライを表すデータ構造。その結果、すべての内部ノードの子の数は、少なくとも基数ツリーの基数 r になります。ここで、r は正の整数で、x は 2 の累乗であり、x ≥ 1 です。

最後に辞書をチェックします。

1.基数（名詞）

他の言葉が生まれる原始的な言葉。

基数ツリーの基数は、ツリーの子の量 (または深さ) と「まばらさ」のバランス、または固有のサフィックスの数を決定します。

編集 - 精緻化

すべての内部ノードの子の数は少なくとも基数 r です

「あば、異常、にきび、ひどい」という言葉について考えてみましょう。通常のプレフィックス ツリー (またはトライ) では、すべての弧が単語に 1 文字追加されるため、次のようになります。

-a-b-a-
   n-o-r-m-a-l-
   y-s-m-a-l-
  -c-n-e-

私の絵は少し誤解を招きやすいです - 文字は通常円弧上にあるので、'-' はノードで、文字はエッジです。多くの内部ノードには 1 つの子があることに注意してください。コンパクトな（そして明白な）形式は次のとおりです。

-a-b  -a-
       normal-
       ysmal-
   cne-

これで、3 つの子を持つ内部ノード (b の後ろ) ができました! 基数は 2 の正の累乗なので、この場合は 2 です。なぜ 3 と言わずに 2 なのですか？まず、ルートには 2 つの子があることに注意してください。さらに、単語を追加したいとします。オプション:

  • 接頭辞を共有しbます - まあ、4 は 2 より大きいです。
  • の子のエッジを共有していますb- 「異常に」と言います。さて、挿入が機能する方法では、共有部分が分割され、次のようになります。

関連するブランチ:

-normal-ly-
       -

現在、normal は内部ノードですが、2 つの子 (1 つは葉) があります。- もう 1 つのケースは、たとえばニキビの削除です。しかし今、compactness プロパティはb、それが唯一の子であるため、後のノードをマージする必要があることを示しているため、ツリーは次のようになります。

木：

-ab-a
   -normal-ly-
          -
   -ysmal

そのため、まだ children>2 を維持しています。

これが明確になることを願っています！

于 2016-10-28T20:16:53.900 に答える