londonperlmongers at iandocherty.com
Thu Dec 31 15:42:01 GMT 2009
I am frustrated in that I think I know of an algorithm for a tree (not a
christmas tree!) but can't remember it's name and that makes it much
more difficult to google.
Anyone know (from my attempt at a description) what this algorithm is
called? Even better, is there a CPAN module for it?
* Every node has a left and a right value and a level
* For any given node, all of it's descendents left values lie between
the nodes left and right values.
* For a leaf node, it's right value equals it's left value + 1
* All children of a parent will therefore be those with node numbers
between the parents left and right values and one level deeper.
I remember it being easy to use this in a database since it makes it
possible to get (for example) all descendents or all children in a
single query, something not always possible with other algorithms. I
also seem to remember that it also makes it easier to move a sub-tree
since it is then just a matter of applying a constant offset to all the
left and right pointers of the sub-tree.
(After describing it here I could probably write the Perl code myself
now, but I would still like to know the name of the algorithm)
More information about the london.pm