Séminaire

Efficient top-down updates in AVL trees

Orateur : Vincent Jugé
05 Novembre 2024 à 14:00 ; lieu : Salle de séminaire 4B125 (bâtiment Copernic)

Balanced binary search trees are a common data structure for implementing ordered sets, with three kinds of queries: checking whether a given value belongs to the set, inserting a value, and
deleting a value; the two latter queries require updating the data structure. Some implementations, like red-black trees or weak AVL trees, allow efficient update procedures, which run in a top-down way and require an amortised constant number of write operations per update query; by contrast, AVL trees still require bottom-up updating procedures, which may require a logarithmic number of write operations per query.

In this presentation, we will present new algorithms for updating AVL trees that bridge this gap: they run in a top-down way and/or require only an amortised constant number of few write operations per update query.

Localisation

Salle de séminaire 4B125 (bâtiment Copernic)

5 Boulevard Descartes 77420 Champs-sur-Marne