|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |