No big news yet. Still exploring though. Recently I have been trying to code a balanced binary tree. As for why; I am trying to solve ORDERS on SPOJ. Doing a naive with arrays and linked list are too slow. However, you can use the same approach with trees (balanced trees actually) and have your solution accepted. I already know how to solve it in my head, the only hindrance is actually creating a balanced binary tree. Well I think I’ll take a break from thinking about it for a while and move on to another problem. Then come back when my skills have matured (lord knows they have a lot of that to do).

Apart from balanced binary trees I’ve also read about heaps. The one I find most interesting is a variant called an interval tree. Basically suppose node X is the interval [a,b] with a<b, then its two children are the intervals [a,c] and [c+1,b], where c is the midpoint of [a,b]. I came across this structure when reading a TopCoder tutorial on how to solve the Range Minimum/Maximum Query problem. Though I have yet to actually practice using any of these methods, the tutorial did a good job of explaining so I don’t imagine it being all that hard.

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Saturday, July 25th, 2009 at 4:33 am and is filed under C++, Trees. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.