Each node in the tree stores the expressions that finish at the node, and pointers to nodes below them, if any have been created. Note, for any node there are a maximum of n pointers, where n is the number of bells, plus one; The extra case in this instance is for a ? or * expression to match any bell.
When a row is to be matched against the expressions stored, each bell in the row is examined individually. If a pointer to a node for the same number as the current bell exists, the matching passes onto the node pointed at. For all cases, if an 'any' pointer exists, then the matching will be passes onto the any node.
When the expression matching comes up against a node where an expression is specified to finish at that node, then the counter for matches against the node is incremented. If there are no matches to the current bell, and the any pointer does not exist, then the matching simply finishes and returns back up the tree.
This is probably better explained by means of an example. Suppose the expression 321654 is added to the TopNode. If + is a node, and |n is a pointer between the nodes, where n is the number of bell pointed to, then the following tree is formed:
TopNode
|3
+
|2
+
|1
+
|6
+
|5
+
|4
+ 321654 finishes here.
When the row 326154 is attempted to be matched, the following happens:
TopNode -> Pointer to 3 exists, so go to the next node.
|3
+ -> Pointer to 2 exists, so go to the next node.
|2
+ -> Pointer to 6 (or to any node) does not exist, so terminate.
|1
Now suppose 321* and ?2* is added to the list, the following tree is formed:
TopNode
|
-------------------------------
|3 |any
+ +
|2 |2
+ + ?2* finishes here.
|1
+ 321* finishes here.
|6
+
|5
+
|4
+ 321654 finishes here.
Now, when the row 321654 is put through the matching process, the following happens. Taking first the pointer to bell '3' option of TopNode:
TopNode -> Pointer to 3 exists, so go to the next node.
|3
+ -> Pointer to 2 exists, so go to the next node.
|2
+ -> Pointer to 1 exists, so go to the next node.
|1
+ -> 321* finishes here so increment, and then as pointer to 6
exists, carry on to the next node.
|6
+ -> Pointer to 5 exists, so go on.
|5
+ -> Pointer to 4 exists, so go on.
|4
+ -> 321654 finishes here so increment matches. No further
pointers, so go back up the tree checking for any pointers
When the matching gets back to the top of the tree and finds the any pointer in the top node, it will follow it as below:
TopNode -> Any pointer exists, so follow it
|any
+ -> Note, we are now on the second bell of the row, which in our case
is 2, pointer exists, so follow it.
|2
+ -> ?2* finishes here so increment matches.
From these examples it can be seen that an optimisation is performed when there is a single * left, which saves the matching algorithm going through exvery any node.