Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1
Posted Jun 29, 2011 16:04 UTC (Wed) by MisterIO (guest, #36192)In reply to: Zeuthen: Writing a C library, part 1 by jwakely
Parent article: Zeuthen: Writing a C library, part 1
Anyway, no, it's not about rebalancing. Even on a normal tree removal of an object is an O(h) operation(with h equal to the height of the tree). In an rb-tree, being it a balanced tree, the height of the tree is (a*log(n))(with some "a" number which now I don't remember). Thus the removal of all the n elements becomes an O(nlog(n)) operation. If instead you do a find_minimum() followed by an inorder visit from there, you're gonna have a delete_tree() operation which is O(n).
Posted Jun 29, 2011 17:53 UTC (Wed)
by jwakely (subscriber, #60262)
[Link] (15 responses)
Posted Jun 29, 2011 19:16 UTC (Wed)
by MisterIO (guest, #36192)
[Link] (14 responses)
Posted Jun 29, 2011 23:51 UTC (Wed)
by njs (subscriber, #40338)
[Link] (9 responses)
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.
Posted Jun 30, 2011 10:33 UTC (Thu)
by MisterIO (guest, #36192)
[Link] (1 responses)
Posted Jun 30, 2011 18:01 UTC (Thu)
by njs (subscriber, #40338)
[Link]
Posted Jul 3, 2011 8:14 UTC (Sun)
by vlovich (guest, #63271)
[Link] (6 responses)
Posted Jul 3, 2011 11:35 UTC (Sun)
by cladisch (✭ supporter ✭, #50193)
[Link] (5 responses)
Posted Jul 3, 2011 18:35 UTC (Sun)
by nix (subscriber, #2304)
[Link] (4 responses)
Posted Jul 3, 2011 19:39 UTC (Sun)
by vlovich (guest, #63271)
[Link] (3 responses)
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).
Posted Jul 3, 2011 22:04 UTC (Sun)
by nix (subscriber, #2304)
[Link] (2 responses)
Posted Jul 6, 2011 15:56 UTC (Wed)
by jwakely (subscriber, #60262)
[Link] (1 responses)
Posted Jul 6, 2011 16:56 UTC (Wed)
by vlovich (guest, #63271)
[Link]
Posted Jun 30, 2011 6:07 UTC (Thu)
by dark (guest, #8483)
[Link] (3 responses)
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.
Posted Jun 30, 2011 10:28 UTC (Thu)
by MisterIO (guest, #36192)
[Link] (2 responses)
Posted Jul 3, 2011 20:48 UTC (Sun)
by dark (guest, #8483)
[Link] (1 responses)
I think your approach can get there too, with some refinement. How are you implementing the inorder visit?
Posted Jul 6, 2011 16:01 UTC (Wed)
by jwakely (subscriber, #60262)
[Link]
Zeuthen: Writing a C library, part 1
If you allocate a std::vector to do it you have to walk the entire map, then iterate across the vector too, for no good reason.
A RB tree's dtor can be O(n) without allocating memory.
Zeuthen: Writing a C library, part 1
The slightly inefficient way is to just do something like
Zeuthen: Writing a C library, part 1
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.
Zeuthen: Writing a C library, part 1
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
I'm not understanding the claims that it takes anything other than O(n) in the worst case for a tree de-allocation.
Zeuthen: Writing a C library, part 1
function destroy_tree(tree) {
foreach child in tree
delete_tree(child)
free(tree)
}
Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1
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.Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1
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).
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.Zeuthen: Writing a C library, part 1
Zeuthen: Writing a C library, part 1