Campus Event Calendar
Event Entry
What and Who
Weighted Dynamic Finger in Binary Search Trees by Iacono and Langerman (SODA '16)
Kurt Mehlhorn
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (others' work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 5 October 2017
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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.
Contact
Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only
Kurt Mehlhorn, 09/21/2017 09:07 -- Created document.