Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Weighted Dynamic Finger in Binary Search Trees by Iacono and Langerman (SODA '16)
Speaker:Kurt Mehlhorn
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (others' work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 5 October 2017
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Kurt Mehlhorn/AG1/MPII/DE, 09/21/2017 09:07 AMLast modified by:Uwe Brahm/MPII/DE, 10/05/2017 07:01 AM
  • Kurt Mehlhorn, 09/21/2017 09:07 AM -- Created document.