Mr.SpOOn wrote:
Hi,
I'm searching for a clear explanation of binary tree properties,
expecially the ones related to logarithms.
For example, I know that in a tree with 2n-1 nodes, we have log(n)
levels, from 0 to log(n).
A *complete* binary tree with n levels has 2**n - 1 nodes. This is
easily shown by induction. (Try Wikipedia for induction proof if you are
not familiar with such.)
So, if k is the level, the nodes on a level have indexes between 2^k
and 2^(k+1)-1.
For k=0 we have 2 and 3.
For k=1 we have 4, 5, 6, 7
and so on.
Nodes only have single number indexes if you arrange them linearly.
Then the index depends on how you arrange them, whether you start the
array indexes with 0 or 1, and whether you start the level numbers with
0 or 1. Call the breadth-first sequence bf. Then the 1-based slice for
1-first level k is bf[2**(k-1):2**k)]. Again, proof by induction.
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
