Is a Trie a K-ary tree?

Question

If you look at the node definitions for a simple Trie and a simple K-ary tree, they look the same.

(using C++ notation)

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

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

At its simplest a K-ary tree has multiple children per node (2 for a binary tree)

And a Trie has "multiple children per node"

It seems that a K-ary tree makes it's choice of child based on comparison( < or > ) of Keys

While a Trie makes it's choice of child based on (unary) equality of sub-spans of the Key

Since neither data structure has made it into any standards, what would be best definition of each, and how would they be differentiated?

Answer 1

From the point of view of the shape of the data structure, a trie is clearly an N-ary tree, in the same way that a balanced binary search tree is a binary tree, the difference being in how the data structure manages the data.

A binary search tree is a binary tree with additional constraint that the keys in the nodes are ordered, a balanced binary tree adds on top of that a constraint on the difference between the lengths of different branches.

Similarly, a trie is a N-ary tree with additional constrains that determine how the keys are managed.

---

Let's try a definition of what a trie is:

A trie is an efficient data structure used to implement a dictionary in which keys are sequences lexicographically. The implementation uses an N-ary tree where the branching factor is the range of valid values for each element in the key sequence^[1] and each node may or not hold a value, but always holds a subsequence of the key being stored ^[2]. For each node in the tree, the concatenation of the subsequences of keys stored in the nodes from the root to any given node represent the key for the value stored, if the node holds a value, and/or a common prefix for all nodes in this subtree.

This layout of data allows for linear lookups on the size of the keys, and sharing the prefix allows for compact representations for many natural languages (like Spanish, where different forms of each verb differ only on the last few suffix characters).

¹: That keys are sequences is an important premise, as the main advantage of the tries is that they split the key into different nodes along the path.

²: Depending on the implementation each node might maintain a single element (character) from the sequence or a combination.