trie和radix trie数据结构之间有什么区别？

Question

是 特里 和 基数特里 数据结构是一回事吗？

如果它们相同，那么基数特里（AKA Patricia trie）是什么意思？

Answer 1

基数树是trie的压缩版本。在特里树中，在每个边上都写一个字母，而在PATRICIA树（或基数树）中则存储整个单词。

现在，假设你有话hello，hat和have。要将它们存储在一个 trie中 ，它看起来像：

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

您需要九个节点。我将字母放置在节点中，但实际上它们标记了边缘。

在基数树中，您将具有：

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

而且您只需要五个节点。在上图中，节点是星号。

因此，总的来说，基数树占用 更少的内存 ，但是很难实现。否则，两者的用例几乎相同。