Another example structure: A modified binary tree

Next: The Static Analysis Up: Path naming Previous: Normalisation using Markov algorithms

Another example structure: A modified binary tree

**Figure 3:** Markov algorithm for illustrated binary tree
$\begin{figure} \begin{center} \fbox { \begin{minipage} {8cm} \begin{center} \in... ... & \rightarrow & \epsilon\end{eqnarray*}\end{minipage}} \end{center}\end{figure}$

Here we look at an example of a binary tree with additional pointers. Apart from the main l and r directions, we have a parent pointer, m and the nodes on each level are joined into a doubly linked cyclic list, with n and p directions. The algorithm for normalisation is shown in figure 3. Note that we can always travel in all directions from all nodes, the parent of the root node is defined as the root node, and the n and p fields wrap around to create a cyclic list.

Timothy Lewis
11/12/1997