that's a perfect (missing) example for "a picture is worth a thousand words".I don't know if it helps, but here's the picture I drew at the top of my patricia trie code. (Crit-bit trees aren't the same as patricia tries, but they're close enough for expository purposes.)
/**
* Our Patricia tree structure can be thought of as operating on strings of
* 9-bit bytes, where 0x00 -- 0xFF are mapped to 0x100 -- 0x1FF and 0x00
* represents the end-of-string character (note that NUL can occur inside
* keys). The field (struct pnode).mask is either 0 or a power of 2; if 0,
* the left child, if non-NULL, is a pointer to the record associated with
* the key thus far. For example, the strings "hello", "hello colin",
* "hello world", and "wednesday", each associated with pointers to
* themselves, are stored in the following tree:
*
* [0x10, 0x60, 0, ""]
* | |
* [0x00, 0x00, 5, "hello"] [0x00, 0x00, 9, "wednesday"]
* | | | |
* "hello" [0x10, 0x60, 1, " "] "wednesday" NULL
* | |
* [0x00, 0x00, 5, "colin"] [0x00, 0x00, 5, "world"]
* | | | |
* "hello colin" NULL "hello world" NULL
*
*/
Edited to add: And here's the node structure:
/* Structure used to store a Patricia tree node. */
struct pnode {
struct pnode * left; /* Left child. */
struct pnode * right; /* Right child. */
uint8_t mask; /* Critical bit mask. */
uint8_t high; /* High bits of this node. */
uint8_t slen; /* Length of s[]. */
uint8_t s[]; /* Bytes since parent's s[]. */
};