468,146 Members | 1,429 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,146 developers. It's quick & easy.

Analytical solution to predict array size of binary tree

I'm constructing a binary tree for a sequence of data and the tree is store in a 1-based array. So if index of parent node is idx,
the left child is 2 * idx and the right is 2 * idx + 1.

Every iteration, I sort current sequence based on certain criteria, select the median element as parent, tree[index] = sequence[median], then do same operation on left(the sub sequence before median) and right(the subsequence after median) recursively.

Eg, if 3 elements in total, the tree will be:
1
/ \
2 3, the array size to store the tree is also 3

4 elements:

1
/ \
2 3
/
4 , the array size to store the tree is also 4

5 elements:

1
/ \
2 3
/ \ /
4 null 5 , the array size to store the tree has to be 6, since there is a hole between 4 and 5.


Thus, the array size is only determined by number of elements, I believe there is an anlytical solution for it, just can't prove it.

Any suggestion will be appreciated.
Thanks.
Jan 16 '19 #1
0 1934

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

7 posts views Thread by pembed2003 | last post: by
5 posts views Thread by pembed2003 | last post: by
15 posts views Thread by Foodbank | last post: by
9 posts views Thread by GiantCranesInDublin | last post: by
4 posts views Thread by whitehatmiracle | last post: by
8 posts views Thread by perdoname | last post: by
1 post views Thread by gcdp | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.