>> Well now, there's red-black trees, AVL trees, the BWS algorithm, 
>> B-trees... exactly *which* self-balancing tree algorithm are we talking 
>> about here?
> 
>   Does it matter?

Well, some operations are in different complexity classes depending on 
which one you pick - not unlike BST vs heap. ;-)

>   Btw, fun fact about balanced binary search trees: When traversing the
> tree from the smallest element to the largest, the computational
> complexity of one step (ie. moving from one element to the next larger
> element) is O(log n). Oviously since you are traversing all the elements
> in the tree, you are doing n such steps. Intuition would tell that the
> computational complexity of the whole traversal would, thus, be O(n*log n).
> However, it's only O(n).
> 
>   Proving this sounds difficult, but it's surprisingly simple.

I couldn't prove my way out of a paper bag. :-(

Where most normal people figure out that (a+b)^3 = a^3 + 3 a^2 b + 3 a 
b^2 + a^3 my shifting algebra, I was too stupid for that. I worked it 
out by drawing a set of 8 3D cubes and attempting to figure out the 
volume of each one. :-S

[Ever tried drawing a complex 3-dimenional figure by hand and annotating 
it with measurements? It's not actually very easy - especially if you 
can't draw...]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message