Balance

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: