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