Invisible <voi### [at] devnull> wrote:
> 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?

  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.

-- 
                                                          - Warp

Post a reply to this message