From: Its Me <itsme213@...>
Date: 2004-10-09T02:59:44+09:00
Subject: Re: [ANN] ndb Object-Relational Mapper


"Brian Candler" <B.Candler@pobox.com> wrote in message
> This is a very cute data structure which I hadn't come across before.

Google for "ait-kaci lattice encoding" or "efficient tree encoding" and you
will see lots of work in this space, covering trees, DAGs, etc. and mapping
them to bit vectors, integers, integer ranges, etc.

> However, if I add a new subordinate to 'Bert' (say 'Bob'), don't I end up
> having to renumber almost the entire tree?
>
>             Albert
>              1,14
>          /          \
>      Bert            Chuck
>      2,5              6,13
>       |            /   |   \
>      Bob     Donna   Eddie  Fred
>      3,4      7,8     9,10  11,12
>

Add a couple of zero's (1,14 --> 100, 1400) and you suddenly have a whole
bunch of breathing room before you have to renumber the whole tree :-)