On Mon, Sep 16, 2013 at 11:15:16AM +0400, Michael V. Zolotukhin wrote:
> > Yes, splay tree can get totally unbalanced and you can have a linear lookup
> > time, the O(log n) lookup time is amortized. But, if you e.g. really do
> > lookup sorted keys (which is not given, the compiler puts vars into the
> > clauses based on the user order or in the order references to those vars are
> > discovered, plus for array sections pointer kinds which usually have
> > different addresses go immediately after the data ones), you really can have
> > one O(n) lookup if you've looked e.g. the highest address last time and now
> > you're looking up the lowest and the tree is totally unbalanced, but then
> > won't the following lookups be all O(1), because the keys you are looking up
> > will be always immediately in the right child?
> If the first time the lookup was in increasing keys order, and then we are
> looking up in decreasing keys order, then yes, there is no problem and at the
> beginning the element we are looking for would be very close to root, so it
> would be fast (at the end I guess there would be still O(log N)). The problem
> would be if the order of the 2nd lookup is the same as the order of the 1st
> lookup.
No. If you insert 1 to 100 into a splay tree in ascending order (that will
give you a totally unbalanced tree), and then lookup 1 to 100 in the
ascending order again, then the lookup of 1 will be expensive (100
comparisons), but then for each following lookup it
will cost just 2 comparisons, so for the 100 lookups you'll need 298
comparisons, i.e. ~ 3 comparisons per lookup on average (rather than the 6-7
lookups you'd get for balanced AVL tree or similar). Splay trees
actually behave very nicely if the lookups are done in sorted orders or
if you usually look up similar addresses in sequence (which is quite likely,
usually the splay tree will contain addresses of #pragma omp declare target
vars (and selected functions) and typically lookups for #pragma omp target
will be usually for function local variables which will have similar
addresses), and if what you lookup is completely random, then you wouldn't
end up with an unbalanced tree.
Jakub
