Trie是K-ary树吗？

Question

如果查看简单Trie和简单K-ary树的节点定义,它们看起来是一样的.

(使用C++表示法)

template <size_t K>
trieNode
{
    trieNode *[K]
};

template <size_t K>
KaryNode
{
    KaryNode *[K]
};

最简单的一个K-ary树每个节点有多个子节点(2个用于二叉树)

特里有"每个节点多个孩子"

似乎K-ary树基于Keys的比较(<或>)使它成为孩子的选择

虽然Trie根据Key的子跨度的(一元)平等使其成为孩子的选择

既然数据结构都没有成为任何标准,那么每种标准的最佳定义是什么,以及它们将如何区分？

Answer 1

从数据结构的形态来看，trie显然是一棵N叉树，就像平衡二叉搜索树是一棵二叉树一样，区别在于数据结构如何管理数据。

二叉搜索树是一种具有额外约束的二叉树，即节点中的键是有序的，平衡二叉树在此基础上添加了对不同分支长度之间差异的约束。

类似地，trie 是一个 N 叉树，具有决定如何管理键的附加约束。

让我们尝试一下什么是 trie 的定义：

trie 是一种高效的数据结构，用于实现字典，其中键是按字典顺序排列的序列。该实现使用 N 叉树，其中分支因子是键序列中每个元素的有效值范围^[1]，每个节点可能保存或不保存值，但始终保存所存储键的子序列^{[2] ]}。对于树中的每个节点，如果节点保存有值，则存储在节点中从根到任何给定节点的键子序列的串联表示存储的值的键，和/或所有节点的公共前缀这个子树。

这种数据布局允许对键的大小进行线性查找，并且共享前缀允许对许多自然语言进行紧凑表示（例如西班牙语，其中每个动词的不同形式仅在最后几个后缀字符上有所不同）。

¹：密钥是序列是一个重要的前提，因为尝试的主要优点是它们将密钥沿路径分割成不同的节点。

²：根据实现，每个节点可能会维护序列或组合中的单个元素（字符）。