|
Write-efficient updates for AVL trees| title | Write-efficient updates for AVL trees |
|---|
| start_date | 2025/03/04 |
|---|
| schedule | 10h45 |
|---|
| online | no |
|---|
| location_info | salle S3 351, 3e étage |
|---|
| summary | 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. |
|---|
| responsibles | Grandjean |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2025/02/25 10:23 UTC |
| |
|