Re: Back to Merkle Hash Trees...

>From: Bill Cox <[email protected]>
>                     1
>           |-----------------|
>           2                 3
>       |-------|         |---------|
>       4       5         6         7
>     |---|    |---|     |---|     |---|
>     8  -9- -10- -11- -12- -13- -14- -15-
>   |---|
> -16- -17-
> 
> The root node has index 1.  It's children are 2 and 3.  In general, your
> left child has index that's twice yours, and your right child is the
> next node after that.

There is another, similar tree construction worthy of consideration:

                                        15
                     |---------------------|
                    09                   -16-
           |-------------------|
          03                  11
      |---------|         |---------|
     01        05        09        13
   |----|    |----|    |----|    |----|
 -00- -02- -04- -06- -08- -10- -12- -14- -16-

Key property here. You can add on (feature planned for BT2), without 
changing internal node indicies.

Or for the heck of it, degree 3:

                                     13
           |--------------------------|--------------------------|
           04                         18                         31
   |--------|--------|        |--------|--------|        |--------|
   01       06       10       15       20       24       28       33
 |--|--|  |--|--|  |--|--|  |--|--|  |--|--|  |--|--|  |--|--|    |
 00 02 03 05 07 08 09 11 12 14 16 17 19 21 22 23 25 26 27 29 30  32 

(I hope no one's head explodes looking at this)

> Root node index: 1 (not 0)

2^H-1

> First piece node index: N

0

> Last piece node index: (N << 1) - 1

N << 1

> Index of piece n (with 0 as the first piece): N + n


> Node n's sibling: n ^ 1

n ^ 2

> Node n's parent: n >> 1

1 <<(h+1)  +1

> Node n's left child: n << 1

n - 1<<(h-1)

> Node n's right child: (n << 1) + 1

n + 1<<(h-1)


Sorry, still working on the ones for the n-ary tree.  %-)


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         [email protected] PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/