Good afternoon, there are several approaches to solving this problem. I could not resolve it directly, which may have left the answer a bit confusing (hopefully not). I hope it helps you get a better view of the problem.
In a complete tree, about half of the nodes are on the lower level. Thus, about half of all searches or insertions or deletions require finding a node at the lowest level. The table below shows how many levels are required to maintain a
number of nodes.
ApparentlythetreewithLlevelshas[2^(L+1)]-1nodes.Moreformally,ifwemakeP(L)denotethenumberofnodesinlevelL,thenourassumptionwillbe:
P(L)=[2(L+1)]-1
Therefore,thenumberofsheetsinlevel3,usinglogic,forexample,willbeequalto:
P (L) -P (L-1)
= P (3) -P (3-1)
= P (3) -P (2)
= [(2 ^ (3 + 1))] 1] - [(2 ^ (2 + 1)
= [(2 ^ (4)) 1] - [(2 ^ (3)) 1]
= [15] - [7] = 8
Then, given a tree with 3 levels and 15 nodes, we will have 8 leaves and 7 nodes not leaves. One more leaf node. Now, how is it possible to generalize that P (L) = [(2 ^ l + 1) -1] is always valid for any L> = 0 in order to have security to use the logic above?
The basis of induction is to establish P (0), which results in equation
number of nodes = P (1) = [2⁽⁰⁺¹⁾] -1 = 1
Now let's assume that our premise is true for an arbitrary level k, that is, we assume that:
and we'll try to show that:
(k + 1) = 2 (k + 1) = [2 (k + 1 + 1)] - 1 {2}
The key to an induction demonstration is to find a way to relate what we want to show - P (k + 1), equation {2} - with what we assume to be true - P (k), equation {1} . The left side
of P (k + 1) can be rewritten to highlight the penultimate term:
(2 + 2) + 2 (2 + 2) + 2 (2 + 2) 2 +
Since we assume that P (k) in the equation {1} is true, we can replace [2 ^ k] in the expression below by the right side of the equation {1}, in this case [2 ^ (k + 1)] - 1 :
(2 + 2) + 2 + 2 + 2 + 2 +
2 + 2 2 + 2 3 + ... + [2 ^ (k + 1)] - 1+ [2 ^ (k + 1)]
= [2 ^ (k + 1)] - 1+ [2 ^ (k + 1)]
= 2 * [2 ^ (k + 1)] - 1
= 2 ^ (k + 1 + 1)] - 1
We conclude that the equation {3} is correct, hence the equation {2} also:
2 ^ (k + 1 + 1)] - 1 = [2 ^ (k + 1 + 1)] - 1
This script in python performs the calculation:
def nodes(level):
return (math.pow(2,(level+1))-1)
def leaves(height):
return nodes(height)-nodes(height-1)
Sources:
GERSTING, Judith L. Mathematical structures for computer science.
Macmillan, 2007.
LAFORE, Robert. Data structures and algorithms in Java. Sams
Publishing, 2017.
