News for hackers. Stuff that matters.
Re:Crit-bit Trees: the best way to store sets by cperciva on Tuesday September 20, 2011 @04:27AM (#3016796)
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[]. */
    };

There are no comments on this comment yet.