Wann:
Oktober 5, 2017 um 1:00 pm – 11:59 pm
2017-10-05T13:00:00+02:00
2017-10-05T23:59:59+02:00
Wo:
Saarbrücken building E1 4
room 024
Kontakt:
Kurt Mehlhorn

I present a result by Iacono and Langerman. Let s1, s2, …, sm be a sequence
of number in [1..n] and let T be ANY binary search tree with leaves numbered 1
.. n. Let
C = sum_i d(s_{s-1},s_i),
where d(s_{i-1},s_i) is the distance between s_{i-1} and s_i in T. They show
that there is a class of self-adjusting binary search trees that serve the
sequence in cost O(C).

The algorithm has no advance knowledge of the sequence of requests. Its actions
do NOT depend on the reference tree T.