Tries as an Abstract Data Type

As an abstract data type, a trie supports three fundamental operations:

• FIND(k)

  Determine whether k is present in the trie. Depending on the application of the ADT, FIND may either simply indicate whether or not k is present, or it may return a value v associated with the key k.

• INSERT(k, v)

  Add the key k to the trie. Depending on the application, a value v may or may not be supplied.

• DELETE(k)

  Remove the key k from the trie.

The domain of k (that is, the set of types that satisfy the constraints on k) is the set of finite strings from a specific alphabet. The domain of v is unrestricted.

The notion of strings used here is more general than the definition of strings in C, and is worth investigating. A string is defined to be to be a finite, ordered sequence of elements (called characters of a finite set (called the alphabet). In C, for example, the alphabet is the set of all possible chars, with the exception of the char 0, which is used to denote the end of a C string but is not considered part of the string), and each character is simply a non-zero char. However, other kinds of strings are quite useful and common (in the context of tries, but also in other contexts). For example, strings of bits (which have an alphabet of , and each character is a single bit) or strings of decimal numbers are often useful. For all of the examples in this section, we will use strings that have an alphabet consisting of the lowercase letters 'a' through 'z'. In the code samples, we will use the C convention of using a zero ('\0') character to mark the end of a string, but note again that this character is not considered to be part of the string itself.

Note that the keys must be unique; while it is relatively easy to adapt most of the data structures that we have seen so far to work with multiple elements that have the same key, the same is not true for tries.

As we will see later, most implementations of tries work best when the alphabet of their strings is small, although from the perspective of the ADT, there is no limitation placed on the size of the alphabet, as long as it is finite.

Tries also readily support some other operations, which will be discussed in section 5.6.