Searching a trie for a key value x requires breaking up x into its constituent characters and following the branches determined by these characters. -me function Trie::Search (Program 10.16) assumes that p = 0 is not a branch node and that p -+ key is the key
value represented in p if p is an element node
template <class Ke.\Type>
TrieNode<KeyType>* Trie<KeyType>::Search (const Element<KeyType>& x)
II Search a trie for key value x.key, It is assumed that branching on
1/ the ith level is determined by the ith character of the key value.
/I Assume we can always concatenate at least one trailing blank ~ox. key.
k = XA. ‘key; concatenate (k, •• );
TrieNode<KeyType> »p = root;
for(int i = I; p is a branch node; p = p -+link [c), i++)
c = ith character of k;
if (p == 0 II p -+key != x) return 0;
else return p;
} /I end of Trie::Search
Analysis of trie Search
The search algorithm for tries is very straightforward, and one may readily verify that the worst-case search time is O(/), where I is the number of levels in the trie (including both branch and element nodes).
In the case of an index, all trie nodes will reside on disk, so at most I disk accesses will be made during search. When the nodes reside on disk, the C++ pointer type cannot be used, as C++ does not allow input/output of pointers. The link data member will now be implemented as an integer.
Given a set of key values to be represented in an index. the number of levels in the trie will depend on the strategy or key sampling technique used to determine the branching at each level. This can be defined by a sampling function. sample (x.i). which appropriately samples x for branching at the ith level. In the trie of Figure 10.50 and in the search algorithm Trie::Search (Program 10.16) this function is sample (x.i) = ith character of x. Some other choices for this function are
An optimal trie for the data of Figure 10.50 sampling 00 the first level ‘done by using the fourth character of the key values
Although all our examples of sampling have involved single-character sampling we need not restrict ourselves to this. The key value may be interpreted as consisting of digits using any radix we desire. Using a radix of 272 would result in two-character sampling. Other radixes would give different samplings
The maximum number of levels in a trie can be kept low by adopting a different strategy for element nodes. These nodes can be designed to hold more than one key value. If the maximum number of levels allowed is l, then all key values that are synonyms up to level/ – I are entered into the same element node. If the sampling function is chosen correctly, there will be only a few synonyms in each element node. The element node will therefore be small and can be processed in internal memory. Figure 10.54 shows the use of this strategy on the trie of Figure 10.50 with I = 3. In further discussion we shall. for simplicity. assume that the sampling function in use is sample (x,i) = ith character of x and that no restriction is placed on the number of levels in the trie
Insertion into a Trie
Insertion into a trie is straightforward. We shall illustrate the procedure by two examples and leave the formal writing of the algorithm as an exercise. Let us consider the trie of Figure 10.50 and insert into it the keys bobwhite and bluejay. First, we have x = bobwhite and we attempt to search for bobwhite. This leads us to node CJ, where we discover that CJ.fillk[‘o’) = O. Hence, x is not in the trie and may be inserted here (see Figure 10.55). Next, x = bluejay, and a search of the trie leads us to the element node that contains bluebird. The keys bluebird and bluejay are sampled until the sampling results in two different values. This happens at the fifth letter. Figure 10.55 shows the trie after both insertions .
Deletion from a Trie
Once again, we shall not present the deletion algorithm formally but will look at two examples to illustrate some of the ideas involved in deleting entries from a trie. From the trie of Figure 10.55, let us first delete bobwhite. To do this we set cr.link[‘o’] equal to O. No other changes need to be made. Next, let us delete bluejay. This deletion leaves us with only one key value in the subtrie, S3′ This means that the node S3 may be deleted, and p can be moved up one level. The same can be done for nodes 01 and S2′ FinaJly, the node o is reached. The subtrie with root e has more than one key value. Therefore, p cannot be moved up any more levels, and we set cr.link[T] equal to p. To facilitate deletions from tries, it is useful to add a count data member in each branch node. This data member contains the number of children the node has
As in the case of binary tries. we can define compressed tries in which each branch node has at least two children. In this case. each branch node is augmented to have an additional data member, skip, that indicates the number of levels of branching that have been eliminated (alternately. we can have a data member. sample. that indicates the sampling level to use).