Recent Features
| |||||||||||||
Zeuthen: Writing a C library, part 1Zeuthen: Writing a C library, part 1Posted Jun 29, 2011 23:51 UTC (Wed) by njs (guest, #40338)In reply to: Zeuthen: Writing a C library, part 1 by MisterIO Parent article: Zeuthen: Writing a C library, part 1 The slightly inefficient way is to just do something like
while (there are nodes left) {
current_node = root;
while (has_children(current_node))
current_node = first_undeleted_child(current_node);
delete(current_node);
}
That deletes everything, needs no heap storage, and it's O(n (log n)^2), not so bad.
The more efficient way is to just preallocate a vector whose length is the same as your maximum tree height (resizing when necessary), and then in the destructor use it as the stack for a single-pass depth-first traversal. The extra memory required is pretty trivial. Not sure if it's worth the bother, though. Well, honestly I'm not sure that any of this is worth the bother. It's a nice puzzle to handle this sort of thing properly in a classic data structure with perfect encapsulation from the rest of the program, but in real life it doesn't help until you've solved a whole pile of harder and idiosyncratic problems too.
(Log in to post comments)
Zeuthen: Writing a C library, part 1 Posted Jun 30, 2011 10:33 UTC (Thu) by MisterIO (guest, #36192) [Link]
>That deletes everything, needs no heap storage, and it's O(n (log n)^2), not so bad.
There's no point to this, a simple remove(value_at_root)(value at root simply because it's the simplest to find) for a balanced binary tree already takes O(log(n)), so why would I create a different algorithm to achieve the same performance?
Zeuthen: Writing a C library, part 1 Posted Jun 30, 2011 18:01 UTC (Thu) by njs (guest, #40338) [Link]
If your rebalancing algorithm doesn't require any heap allocations then right, there is no point.
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 8:14 UTC (Sun) by vlovich (guest, #63271) [Link] I'm not understanding the claims that it takes anything other than O(n) in the worst case for a tree de-allocation.
function destroy_tree(tree) {
foreach child in tree
delete_tree(child)
free(tree)
}
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 11:35 UTC (Sun) by cladisch (✭ supporter ✭, #50193) [Link]
If a generic deletion function is used, it might rebalance the tree after each step.
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 18:35 UTC (Sun) by nix (subscriber, #2304) [Link]
When you're writing a tree deallocator, I'd expect it to have privileged access to the interior of the tree. There's no reason not to use a specialized high-speed node deletor in that case: rebalancing the tree between every deletion is silly, because it will never be accessed again. (Even a multithread-safe tree should probably block and warn on accesses once tree deallocation begins: any such accesses are racy and could easily access rubbish if they happened just an instant later.)
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 19:39 UTC (Sun) by vlovich (guest, #63271) [Link]
Rebalancing the tree would be enormously redundant - the extra 4-6 lines of really simple code is worth it (hell, if you're lazy, provide a boolean to the internal delete function that says whether or not to rebalance).
Thread-safety is irrelevant here - if you can access the tree after the destructor is already called, you've failed at thread safety (actually you've failed at maintaining the lifetime of the object properly).
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 22:04 UTC (Sun) by nix (subscriber, #2304) [Link]
I think we are in violent agreement.
Zeuthen: Writing a C library, part 1 Posted Jul 6, 2011 15:56 UTC (Wed) by jwakely (subscriber, #60262) [Link]
I'm glad someone sensible agrees with the point I made way back in http://lwn.net/Articles/449645/ ... I was starting to think I was going mad and everyone else knew something about RB trees that I didn't
Zeuthen: Writing a C library, part 1 Posted Jul 6, 2011 16:56 UTC (Wed) by vlovich (guest, #63271) [Link]
Same here. I mean it's been a while since I took data structures. Maybe things have changed ;).
|
|||||||||||||