The tree that Patricia uses for searching should be contained in random-access memory, or it should be arranged on pages as suggested in Section 6.2.4. It consists of a header and N −1 nodes, where the nodes contain several fields:
KEY, a pointer to the text. This field must be at least lg C bits long, if the text contains C characters. In Fig. 33 the words shown within each node would really be represented by pointers to the text; for example, instead of “(JACK)” the node would contain the number 24 (which indicates the starting place of “JACK BUILT?” in the text string).
LLINK and RLINK, pointers within the tree. These fields must be at least lg N bits long.
LTAG and RTAG, one-bit fields that tell whether or not LLINK and RLINK, respectively, are pointers to children or to ancestors of the node. The dotted lines in Fig. 33 correspond to pointers whose TAG bit is 1.
SKIP, a number that tells how many bits to skip when searching, as explained below. This field should be large enough to hold the largest number k such that all keys with prefix σ agree in the next k bits following σ, for some string σ that is a prefix of at least two different keys; in practice, we may usually assume that k isn’t too large, and an error indication can be given if the size of the SKIP field is exceeded. The SKIP fields are shown as numbers within each non-header node of Fig. 33.
The header contains only KEY, LLINK, and LTAG fields.
~
TAOCP, v. 3, p. 499