> 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. Maybe you are right, so splay trees might be the best choice here indeed.
Michael > Jakub