Write-efficient updates for AVL trees

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 amortized 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.

We will present recent algorithms for updating AVL trees that bridge this gap: they run in a top-down way and/or require only an amortized constant number of write operations per update query; most of the presentation will be devoted to the latter aspect.