Re:Crit-bit Trees: the best way to store sets
by kragen on Monday September 19, 2011 @11:03PM
(#3016089)
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.
Re:Crit-bit Trees: the best way to store sets
by viraptor on Tuesday September 20, 2011 @06:43AM
(#3017043)
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 ;)
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[]. */
};
Re:Crit-bit Trees: the best way to store sets
by iam on Monday September 19, 2011 @10:45PM
(#3016048)
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.
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.