libstdc++ ドキュメントのポイント 3 と 4 によると、PATRICIA の試行には 2 種類のノードがあります。
(PATRICIA) トライはツリーに似ていますが、次の違いがあります。
キーを一連の要素として明示的に表示します。たとえば、トライは文字列を一連の文字として見ることができます。トライは、数値を一連のビットとして表示できます。
（必ずしも）バイナリではありません。各ノードには n + 1 のファンアウトがあります。ここで、n は個別の要素の数です。
リーフ ノードにのみ値を格納します。
内部ノードには、A) それぞれに少なくとも 2 つの子があり、B) それぞれがその子孫のいずれかと同じプレフィックスを共有するというプロパティがあります。
私が読んでいる本 (Algorithms in C, Part 1-4 by Robert Sedgewick) は、内部ノードを使用して値を格納する、n 個のノードのみで n 個の値を格納する PATRICIA トライについて説明しているようです。
DST と同様に、パトリシアの試行では、N 個のノードのみを含むツリーで N 個のキーを検索できます。...別の単純なデバイスを介して外部ノードを回避します。データを内部ノードに保存し、外部ノードへのリンクをトライの正しい内部ノードに戻るリンクに置き換えます
ここには 2 つの信念のキャンプがあるようです。
- 一方では、厳密で具体的な定義があります (つまり、Sedgewick、Knuth、Morrison はすべて、PATRICIA を一方向分岐が排除されたプレフィックス圧縮されたバイナリ ツリーとしてのみ説明しているようです)。と
- 次に、この用語が「map」、「dictionary」、「trie」などの単語を使用することを意図しているように見える、あいまいで曖昧な定義を形成していると信じている人がいます (これらは実際にはすべて大まかに定義されています。つまり、libcstd++ ドキュメント)。
私は自分のリソースの正確性について心配していると思います。私が理解しているように、一般的なプレフィックスによって引き起こされる問題により、ツリーをバイナリツリーとして提示せずに N ノードだけで表現することはできません (libcstd++ ドキュメントのポイント 2 と、変数を扱うときのポイント 4 に違反しているようです)。 -width キー)、および厳密な一方向分岐の概念を失うことなく (「リーフ ノード」と「子」の概念をやや無効にすることにより、ポイント 3 と 4 に違反します)。この 2 つの機能は連携して動作し、このようなツリーが N 個を超えるノードを使用する原因となる "内部ノード" であるジレンマを排除します (思い出してください: N 個のアイテムと N 個のノードのみ)。
これら 2 つの参照グループが両方とも正しいとは限りません。相互排除が多すぎる。ある参考文献はパトリシアが二元的であると言い、別の参考文献はそうではないかもしれないと言っていますが、どちらも事実上正しいとは考えられません。これらの参照のうち、正しいものはどれですか?