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. Yet, AVL trees still require bottom-up updating procedures, which may require a logarithmic number of write operations per query.

We will present new algorithms for updating AVL trees, directly inspired from algorithms for weak 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.