| |||||||||||||
Zeuthen: Writing a C library, part 1Zeuthen: Writing a C library, part 1Posted Jun 30, 2011 6:07 UTC (Thu) by dark (subscriber, #8483)In reply to: Zeuthen: Writing a C library, part 1 by MisterIO Parent article: Zeuthen: Writing a C library, part 1 You can do it in O(n) by abusing the child pointers of nodes that you've visited but not yet destroyed. For example if you always descend to the left node first, then you can put the current node on a linked list that's threaded through the left pointers. When you hit the bottom of the tree, you take a node out of the linked list, destroy it, and proceed to its right child. This way you visit each node a constant number of times (once to put it on the list, once to take it off) and you only need two temporary pointers: one for the start of the list and one for the child to visit next. You can optimize a bit for leaf nodes but that doesn't impact the time complexity. Managing the linked list is easy because you're just using it as a stack.
(Log in to post comments)
Zeuthen: Writing a C library, part 1 Posted Jun 30, 2011 10:28 UTC (Thu) by MisterIO (guest, #36192) [Link]
>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).
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]
|
|||||||||||||