G11 Computer Science at The Dragon Academy

Class' Summary Thu 25 Apr 2019

Worked out first exercise of Trees: Given N nodes, what are #levels / Height of 1)binary 2)ternary and 3)degree 5 trees.

Today we solved the case of a binary tree. Let's see: Each level i contains at most \(2^i\) nodes (a full binary tree). If we have \(k\) such levels, the total number \(N\) of nodes is: \(N=2^{1-1}\, +\, 2^{2-1}\, +\, \dots\, +\, 2^{k-1}\) . We need then to find out how to add such a sum (it's called a geometric series).

• A) Summation of geometric series with a factor of \(2\): \(2^0 + 2^1 + 2^2 + ... + 2^k = 2^{k+1} - 1\). Hence, the above sum gives: \(N = 2^k - 1\) for a full binary tree with \(N\) nodes and \(k\) levels. Check that indeed this formula works for the cases of \(N=1,\,3,8\). Sketch the full binary tree and count the levels in each case.
• B) log as inverse of power: \(2^3 = 8\) then \(\log_2(8) = 3\); \(3^4=81\) then \(\log_3(81) = 4\).
• C) log as repeated division: iLog !! (For more on iLog you may read my posts on it at https://teachers.io/MASantos/blog ): The results on B) can we restated as, 8 can be divided 3 times by 2 before we get a number smaller than 1; 81 can be divided 4 times by 3 before we get a number smaller than 1.
• Ok, but we wanted to get the number of levels, \(k\) in terms of the total number of nodes \(N\). What we got before is the reverse way, i.e., \(N\) in terms of \(k\). Let's then isolate \(k\). We have $$2^k\,=\,N\,+\,1\\ \mbox{from where, taking} \log_2 \mbox{on both sides, we get}\\k\,=\,\log_2(N+1)$$ See the slides for cases where the tree is not full. What happens when say \(N=5\)? How many levels does the tree have? What's its height? It turns out $$k=\lceil\log_2(N+1)\rceil\,=\,{ilog}_2(N+1)+1$$ Check that indeed this works for \(N=1,3,5,6,7,8,10\).

As usual, the slides can be found at http://mmsantos.sdf.org