k-ary tree implemented in array

ive worked a bit on this problem and have come up with a proof for

this. I'll post it here.

defenition:

(1)

depth= how deep in tree,

thus root:depth=0.

e.g.

1 depth 0

2 3 depth 1

4 5 6 7 depth 2

...

(2)

position=in the row u are in, how far are u from the left side.

in the example, the position(4)=1;position(3)=2;position(7)=4, etc.

1. first child=k*i-k+2

(1)

the number of elements at depth=d=k^d

with recursion:

- d=0 => number of elements = 1 (root)

- lets say that it's true for d=n, now prove it's true for d=n+1

so in depth d=n there are k^n elements.everyone of those elements has

k children, so there are k*k^n=k^(n+1) elements

(2)

the first element at depth=d=1+ Sum( k^t, t=0 until t=(d-1) )

//Sum does what the big sigma sign does...

//have to use Sum as i cant put the big sigma on my screen

with recursion

- d=0 => 1+ 0=1

- true for d=n, prove it's true for d=n+1

as there are k^n elements in depth n the first element at depth n+1=

(first element at depth n) + k^n;

this proves what had to be proven

(3) now the real proof

i has a depth and position, if these two parameters are known, i is

known.

the first child i'll abreviate with Ch1.

position=p;depth=d

Ch1=(p-1)*k + k^d - p + i + 1

explanation:

the elements at depth d before position all have n children, this

explains (p-1)*n

the elements at depth d at the right of position all count for 1, this

explains n^d - p becaus n^d is number of elements in that row

we have to add these two to the element i and then add 1 to move to

the first child of element i.

with (2) we can write p as:

p=i + 1 - (1 + Sum( k^t, t=0 until t=(d-1) )

note that for d=0 the equation we have to prove holds

so, lets say d>0

Sum( k^t, t=0 until t=(d-1) )=1 + k + k^2 + ... + k^(d-1)

= (k^d - 1) / (k - 1)

=>

p= i - (k^d - 1) / (k - 1)

=>Ch1=k*i - k*(k^d - 1) / (k - 1) - k + k^d - i + (k^d - 1)/(k - 1) +

i + 1

=k*i + 2 - k

parent=(i+n-2)/n

first child=n*i-n+2=n*(i-1) + 2

2. parent= (i+ k - 2)/k

we know that

Ch1=k*parent + 2 - k

=> Ch1- 2 + k is divisable by k

=>parent= (Ch1-2+k)/k

as (Ch1 - 2 + k) is divisable by k, the next (k-1) elements wont be

and so the division will result in the parent.

<Bart>