The Algorithm

Since the paths are built up a symbol at a time we merely require a way of adding a new symbol to a normalised path, and manipulating to produce a normalised version.

Suppose we have a path

$$P_{1} = x_{1},x_{2}, x_{3} \ldots x_{m}$$

and we want to add to it a new symbol b. The algorithm proceeds as in fig. 3.2

This can clearly be extended in the case where a path P has not been built up incrementally, we merely start with an empty path and add symbols from P to it using the above algorithm.

The algorithm is $\Omega (m)$, where m is the length of the path. This will represent an overhead in the final implementation whenever a node name is generated. This overhead will depend on the depth of the data structure, rather than the number of nodes in it.

 

Figure 3.2:   Add Symbol Algorithm