Efficient top-down updates in AVL trees
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910697943728128 |
|---|---|
| author | Jugé, Vincent |
| author_facet | Jugé, Vincent |
| contents | Since AVL trees were invented in 1962, two major open questions about rebalancing operations, which found positive answers in other balanced binary search trees, were left open: can these operations be performed top-down (with a fixed look-ahead), and can they use an amortised constant number of write operations per update? We propose an algorithm that answers both questions positively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09531 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient top-down updates in AVL trees Jugé, Vincent Data Structures and Algorithms Since AVL trees were invented in 1962, two major open questions about rebalancing operations, which found positive answers in other balanced binary search trees, were left open: can these operations be performed top-down (with a fixed look-ahead), and can they use an amortised constant number of write operations per update? We propose an algorithm that answers both questions positively. |
| title | Efficient top-down updates in AVL trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.09531 |