G5BADS Informal coursework 3
For tutorials in the week of the 1st-5th December:
- Prove by mathematical induction that a perfectly balanced binary tree with
k levels contains 2k-1 leaves.
Proof:
Basis of induction (k = 1): a perfectly balanced
tree with one level (just the root) has one leaf
(one node with no children). 1 = 20 = 21 - 1 so the
claim is correct for k = 1.
Inductive step : if the claim is true for perfectly balanced trees
with n levels, it is true
for prefectly balanced trees with n+1 levels.
Assume that in a perfectly balanced tree with n levels there are
2n-1 leaves. A perfectly balanced tree with n+1 levels
has twice more leaves (since every node on level n-1, which is a leaf in
a tree with n levels, now has two children which are leaves in a tree with
n+1 levels). So a pefectly balanced tree
with n+1 levels has 2 * 2n-1 = 2n leaves, which
is the same as 2(n+1)-1 leaves. If the claim holds for
a tree with n levels, it holds for a tree with n+1 levels.
- Calculate how many levels a complete binary tree of size x has.
First of all, recall that perfectly balanced trees contain 1, 3, 7, 15...
nodes, the number of nodes being of the form "some power of 2 - 1".
The number of levels in a perfectly balanced tree is log2(x+1),
where x is the number of nodes. For example, a perfectly balanced tree
of size 31 has 5 levels (25 = 32).
Now if we see a complete binary tree of size x, we need to ask ourselves
what would be the smallest perfectly balanced tree which could keep
at least that many nodes. For example, if x = 15 we know that the smallest
perfectly balanced tree which can keep 15 nodes is a perfectly balanced tree with 4
levels. If x = 17 the nodes would not fit in 4 levels, we need an extra
level so need to look at a perfectly balanced tree of size 31.
So the rule is: if x = 2n - 1 for some integer n, then
a complete binary tree of size x contains n levels. Otherwise find
the smallest n such that x <= 2n - 1.
Another way of saying the same thing: take log2(x+1) and
round it up to the nearest integer.