Hacker News Reader

Comment by viraptor | Hacker News Reader

> A crit-bit tree for a nonempty prefix-free set S of bit strings has an external node for each string in S; an internal node for each bit string x such that x0 and x1 are prefixes of strings in S; and ancestors defined by prefixes.

And that's a perfect (missing) example for "a picture is worth a thousand words". Then again... this coming from DJB - I should be surprised the description is as verbose as it is.

View on HN

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[]. */
    };

The particular words you've quoted have managed to condense a thousand pictures — an infinite number, really — into 45 words. It's kind of a counterexample.

Some examples would certainly help, and probably diagrams would help understanding the examples.

That's assuming you take "nonempty prefix-free set", "internal node", "bit string x such that x0 and x1" (not sure if they're supposed to be subscripts or are 0 and 1 bits) for granted. A picture solves the problem in many ways giving you real examples.

It's 45 words with lots of assumed knowledge that you could write books about ;)

Yeah, I gotta say, I knew exactly how it worked the moment I looked at the radix tree picture on wikipedia. After reading more than half the linked article though I still had very little understanding of what it really did.

Reply on news.ycombinator.com