| |||||||||||||
Zeuthen: Writing a C library, part 1Zeuthen: Writing a C library, part 1Posted Jun 30, 2011 10:28 UTC (Thu) by MisterIO (guest, #36192)In reply to: Zeuthen: Writing a C library, part 1 by dark Parent article: Zeuthen: Writing a C library, part 1
>then you can put the current node on a linked list that's threaded through the left pointers
We were discussing about the problems caused by allocations in the destructor. And what exacly would I gain by doing this instead of, like I said in the first post, find_minimum(), then next() till the end and save pointers to elements on a vector, then free them all through the vector of pointers? Also, if my assumption in my second post is correct, you don't even need to save temporaries if you do an inorder visit, you just need to free the node once you've reached the parent, checking that the children have all its own children NULL(which means that you've already visited all the grandchildren).
(Log in to post comments)
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 20:48 UTC (Sun) by dark (subscriber, #8483) [Link] What you gain is a destructor that works in O(n) time and does no allocations. By reusing the child pointers as a linked list, you avoid having to make any allocations for it.I think your approach can get there too, with some refinement. How are you implementing the inorder visit?
Zeuthen: Writing a C library, part 1 Posted Jul 6, 2011 16:01 UTC (Wed) by jwakely (subscriber, #60262) [Link]
|
|||||||||||||