An Amortized Analysis of Insertions into AVL-Trees

DOI10.1137/0215002zbMath0589.68048OpenAlexW2021573024MaRDI QIDQ3718166

Kurt Mehlhorn, Athanasios K. Tsakalidis

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215002

zbMATH Keywords

balanced search treesrandom insertionsamortized behavior of AVL-trees under sequences of insertionsbalance changes

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (10)

Expected behaviour analysis of AVL trees ⋮ Gap terminology and related combinatorial properties for AVL trees and Fibonacci-isomorphic trees ⋮ Relaxed multi-way trees with group updates. ⋮ Improved bounds for the expected behaviour of AVL trees ⋮ An O(\(n\)) time algorithm for maximum matching on cographs ⋮ AVL trees with relaxed balance ⋮ Unnamed Item ⋮ Preprocessing Ambiguous Imprecise Points ⋮ Some Results for Elementary Operations ⋮ Exponentially decreasing number of operations in balanced trees

This page was built for publication: An Amortized Analysis of Insertions into AVL-Trees