2015/06/11 by Mahdi Amani, Amani, Mahdi, Kevin A. Lai +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies
paper · pdf · doi:10.48550/arxiv.1506.03528
openalex publication_date 2015/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An AVL tree is the original type of balanced binary search tree. An insertion in an n-node AVL tree takes at most two rotations, but a deletion in an n-node AVL tree can take Θ(log n). A natural question is whether deletions can take many rotations not only in the worst case but in the amortized case as well. A sequence of n successive deletions in an n-node tree takes O(n) rotations, but what happens when insertions are intermixed with deletions? Heaupler, Sen, and Tarjan conjectured that alternating insertions and deletions in an n-node AVL tree can cause each deletion to do Ω(log n) rotations, but they provided no construction to justify their claim. We provide such a construction: we show that, for infinitely many n, there is a set E of \it expensive n-node AVL trees with the property that, given any tree in E, deleting a certain leaf and then reinserting it produces a tree in E, with the deletion having done Θ(log n) rotations. One can do an arbitrary number of such expensive deletion-insertion pairs. The difficulty in obtaining such a construction is that in general the tree produced by an expensive deletion-insertion pair is not the original tree. Indeed, if the trees in E have even height k, 2k/2 deletion-insertion pairs are required to reproduce the original tree.