基數在基數樹中的含義是什麼？

Question

我想了解the radix tree (or compact prefix tree) data structure。

我理解查找，插入和刪除如何使用它。但我無法理解radix在基數樹中的含義。

這裏radix的用途是什麼？

Answer 1

正如@80在Wikipedia etymology link中提到的那樣，'radix'是您的trie的基礎。在這種情況下，我們指的是數字庫，我們會考慮存儲二進制數據。基數R = 2^x，其中x> = 1。

以二元（2元）樹的例子。基數爲2，所以在每個節點上，您可以比較一位。這兩個孩子會處理所有可能的結果：

• 該位爲0
• 該位爲1

複雜的一個新的水平將是4元線索。正如@Garrett在上面提到的那樣，基數必須是2的冪，以便它總能處理我們使用它的二進制數據的所有可能的排序結果。每個引線

這四個選項，以一個不同的子：A 4進制線索可以用四種可能的結果比較兩個二進制位節點。

現在，在回答你有關英文字母基數的問題。你想編碼從a到z（26個字母）的字母，所以需要有一個至少爲2^5 = 32的基數。這是最小的基數，它可以讓你在每個字母之間切換，並符合兩個冪' 規則。 2^4 = 16不會處理所有的字母。

舉個例子，假設下面的編碼：

• 00000代表 'A'，
• 00001代表 'B'，
• ...等
• 11001代表「Z」，
• 11010至11111未使用（還）

我們現在能做的五個位在樹中的每個節點的比較，所以每個節點現在可以在任何羅馬字母之間切換。如果你想要一個處理大寫字母的trie，那麼你將需要一個更大的基數。 2^6的基數將使你足夠做到這一點，但它的代價是更多的浪費空間（未使用的分支）的成本。

其他閱讀：Sedgewick, Ch 15.4, on Multiway Tries。 Algorithms by Cormen的第三版通常是優秀的，但對於多次嘗試並沒有太大的作用。

Answer 2

有上Wikipedia一些信息：

的結果是，每一個內部節點有多達基數線索，其中r是一個正整數，電源x的基數爲r的孩子的數量2，x≥1。

所以基數表示每個內部節點的孩子數量，該數字必須是2的冪。當基數爲2時，我們有一個熟悉的二叉樹。

Answer 3

我已經發布了一個回答，作爲對另一個線程的迴應 - What is the difference between trie and radix trie data structures?。特別是Radix Trie和這可能不是一個Radix Trie可能是特別感興趣的這個問題。