Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Question about Problem1.2.3
What exactly are we supposed to do here? The space efficiency of the two representations is the same imo. And how am I supposed to test this with my implementation? Or do you want to konw the space complexity of the computation, for example count the calls to construct for a list with x elements. This would not be space complexity then. I am a little confused, please help.
This question is thrown in for variety, just to make you think about your programs and binary trees a bit.
There is no perfect expected answer.
You should write 2-3 sentences about how numbers of nodes and leafs of a binary tree representation relate to efficiency.
“Solution” for Problem 1.2.3
The Musterlösung apparently also suffered from the poor formulation that leads in a wrong direction:
With the representation of trees given on the sheet every binary tree has the same space complexity as the number of leaves of any binary tree is the number of its nodes + 1, as can be shown easily by induction on the structure of the tree (this disproves the Musterlösung).
The exact same has already been said in the corresponding Präsenzübung where it apparently was ignored.
The subquestion is indeed worded poorly, and I won’t use it again.
But as I said before, it’s safe to ignore its details as long as it makes you think about trees and efficiency.