k-ary tree implemented in array
Author Message k-ary tree implemented in array

a k-ary tree (ex. 2-ary being binary), is stored in an array with root
at position 0 as follows:

{in a binary tree, for example...}
array is root, array is first child, array is second child,
array is first child of first child, array is second child of first
child... and so on and so on.

i need to find a formula or some way of finding the following:

- given the index of the parent, find the indexes of its children
- given the index of a child, find the index of its parent

thanx
- Poz

Sun, 30 Sep 2001 03:00:00 GMT  k-ary tree implemented in array
: a k-ary tree (ex. 2-ary being binary), is stored in an array with root
: at position 0 as follows:

: {in a binary tree, for example...}
:   array is root, array is first child, array is second child,
: array is first child of first child, array is second child of first
: child... and so on and so on.

: i need to find a formula or some way of finding the following:

:   - given the index of the parent, find the indexes of its children
:   - given the index of a child, find the index of its parent

Given a 1-based array and a binary tree, parent N has children 2N, 2N+1.
So for a zero-based array, you need to offset that by one.  k-trees are
a further extension.

Will

Sun, 30 Sep 2001 03:00:00 GMT  k-ary tree implemented in array
Poz schrieb:
Quote:

> a k-ary tree (ex. 2-ary being binary), is stored in an array with root
> at position 0 as follows:

> {in a binary tree, for example...}
>   array is root, array is first child, array is second child,
> array is first child of first child, array is second child of first
> child... and so on and so on.

wow, you must have a proper tree for doing that !
but okay ... if the tree is really "clean" (two children to each parent
except the last, symmetric on every node), then you have always parent,
first child and subsequent, second child and suibsequent.
so you might better do it recursively (or better still: with a
while-loop) by storing length and position:
get first child-tree: position++, length = length/2 + 1
get second child-tree: position+=length/2 + 1, length = length/2 + 1
so you get the "remaining tree" and proceed as long as you want (maybe
you have a string like "101110") and then get the first out of the
current list.
ex.:

int curPos=0, curLen = ARRLEN;
char searchStr[] = "0110";
int searchPos = 0;

for(;searchPos<4;searchPos++)
{
curLen = curLen / k;
curPos += (searchStr[searchPos]-'0')*curLen + 1;

Quote:
}

/* now, arr[curPos] will give you what you want; of course,
you should build some dumb-user-security
k-ary would be very similar:
for (...) {
curLen = curLen / k;
curPos += (searchStr[searchPos]-'0')*curLen + 1; }
*/

hope this helps ...

Mon, 01 Oct 2001 03:00:00 GMT  k-ary tree implemented in array

if: k=constant nr of children
if: 1=number of root (so not 0)
example : binary
1
2       3
...
if: i=position where u are at

then:
parent=(i+n-2)/n
first child=n*i-n+2=n*(i-1) + 2

notice that if u change parent into i and i into parent in the first
expression, u get the second...
<Bart>

Quote:
>a k-ary tree (ex. 2-ary being binary), is stored in an array with root
>at position 0 as follows:

>{in a binary tree, for example...}
>  array is root, array is first child, array is second child,
>array is first child of first child, array is second child of first
>child... and so on and so on.

>i need to find a formula or some way of finding the following:

>  - given the index of the parent, find the indexes of its children
>  - given the index of a child, find the index of its parent

>thanx
>  - Poz

Tue, 02 Oct 2001 03:00:00 GMT  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>

Tue, 02 Oct 2001 03:00:00 GMT  k-ary tree implemented in array
[snippety snip snip]

wow, I thought the solution to the orig post
was fairly easy until you managed to somehow
complicate it.

Ed Hill

Fri, 05 Oct 2001 03:00:00 GMT  k-ary tree implemented in array

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

the formula given for the children
2i, 2i+1
only works for binary trees.

Maybe i shouldnt have posted the proof, but it took some time and i
didnt want it to go to waste.

Really, nothing difficult about those simple formulas....

Quote:

>[snippety snip snip]

>wow, I thought the solution to the orig post
>was fairly easy until you managed to somehow
>complicate it.

>Ed Hill

Fri, 05 Oct 2001 03:00:00 GMT

 Page 1 of 1 [ 7 post ]

Relevant Pages