Search trees on trees

27^th July 2023, 13:00 Ashton Lecture Theatre
Benjamin Berendsohn
Freie Universität Berlin

Abstract

Search trees on trees (STTs) are a generalization of binary search trees (BSTs). Where the key space of a BST is a totally ordered set, the key space of an STT is a tree.
Both the dynamic and the static BST model can be adapted to the setting of STTs, and I will present some results from both areas. This includes approximation algorithms for STTs with optimal expected search time, and a generalization of the Splay Tree data structure to the STT setting.