arXiv Open Access 2024

Efficient top-down updates in AVL trees

Vincent Jugé

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (1)

Vincent Jugé

Format Sitasi

APA MLA BibTeX

Jugé, V. (2024). Efficient top-down updates in AVL trees. https://arxiv.org/abs/2411.09531

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓