混淆關於PATRICIA

Question

根據點3和的libstdc++ documentation 4，PATRICIA嘗試有兩種類型的節點：

A（PATRICIA）線索類似於樹，但具有下列 差異：

1. 它明確地將鍵視爲一系列元素。例如，特里可以將字符串視爲一系列字符;特里可以將一個 號碼視爲一個比特序列。

2. 它不是（必然）是二​​元的。每個節點都有扇出n + 1，其中n是不同元素的數量。

3. 它只存儲葉節點的值。

4. 內部節點具有以下特性：A）每個至少有兩個孩子; B）每個孩子與其任何一個孩子都有相同的前綴 後代。

這本書我一直在讀（算法在C，1-4部分由羅伯特·塞奇威克）似乎描述PATRICIA線索存儲與僅n個節點的n值，使用內部節點的存儲值：

與DST類似，patricia試圖允許在僅有 N個節點的樹中搜索N個密鑰。 ......我們通過另一個簡單的裝置，避免外部節點：在內部節點，我們 存儲數據，並與 鏈接指向向上返回到正確的內部節點線索

我猜我更換鏈接到外部節點我擔心我的資源的準確性（編輯：...並且這些並不是這個話題中唯一引起爭議的兩個參考）。哪些參考文獻是正確的？

Answer 1

我繼續尋找從過去的有信譽的來源明確的定義，以確認我所懷疑的，我正在寫，提供我的發現。也許最顯著是官方給出定義PATRICIA，由DR莫里森1968s月出版的「ACM學報」：

PATRICIA從「一庫自動機」 [3]等研究中發展。 ... 在這個進化的早期，它決定字母應該是 限制爲二進制。一個強烈影響這個決定的定理是以另一種形式歸因於歐拉的定理。定理 指出，如果字母表是二進制的，那麼分支的數量是 恰好比結束的數量少一個。推論表明，隨着圖書館的發展，每一個新的結局都會帶着它進入圖書館，其中 恰恰就是一個新的分支，而每個分支恰好有兩個出口。這些事實在索引的存儲分配中非常有用。他們 意味着所需的總空間完全被 數字結尾的確定，以及所有所需的存儲實際上會被使用。

這肯定與libstdC++參考的第2和第3點相矛盾。本文中還有更多的證據，例如具體的算法細節，但上面的引用應該足夠了。

似乎沒有從在塞奇威克報價官方描述的任何偏差，但是。基於此，libstdC++資源當然不如Sedgewick資源有效。

Answer 2

雖然這兩個定義看起來都是正確的，但第一個更詳細，對我來說似乎更好。也看看this answer，我試圖描繪一個帕特里夏和普通Trie之間的區別。