I just noticed that in PDF, the slides that had the delayed “sticky” note added (starting at slide 7), it is always there and obstructs the slide. Is sharing the PowerPoint (OpenOffice Impress?) presentation an option?
@Pim: Yes, in the current implementation you do lose the ability to merge the marking with a normal graph traversal that the program would have done anyway. By decoupling it, the tradeoff is that you can choose to give that up in favor of that you don’t have to write the tracing logic yourself, and also gain more control over when/where tracing runs (e.g., it doesn’t have to wait for a caller to traverse, or be on a caller’s thread).
@Herb, thank you. Knowing which objects point to which other objects however, can’t you add a library function to traverse the graph marking the elements as well as executing a user provided functor and call collect minus the tracing step at the end? For simple cases this might alleviate the downside.
@Ray: Yup, I tried to break apart build slides into separate slides when a later build step would obscure an earlier part of the slide, for exactly this reason (so that handouts would be readable). Let me know if I missed any.
I think there’s a slight error on slides 19/20 about the iterative destructor, but please excuse me if I’m wrong.
Your algorithm iteratively finds a leaf and then destructs it, so the runtime should be O(N*h), where h is the height of the tree. Of course, for balanced trees h=log N, as you wrote. But your example of the linked list being a degenerate tree shows that this is actually worst-case O(N). Actually, the same holds for the default recursive destruction, which uses O(h) stack space. There you have listed it as “O(N) stack space”, not only O(log N) (in which case it probably would not be a problem).
So I think that the worst-case run-time for your iterative destruction (in this particular implementation) is actually O(N*N).
@Andre You are correct, and I’m pretty sure that in the talk I explained the worst-case of that slide, and definitely did a couple of slides later when talking about the linked list case as a tree of breadth 1.