Insertions and Deletions In One-Sided Height-Balanced Trees Recently Hirschberg has established that insertions into one-sided height-balanced trees can be done in 0(log^2N) steps. It is proved here that deletions can also be performed in 0(log^2N) steps, which answers the open problem posed by Hirschberg. CACM March, 1978 Kosaraju, S. AVL trees, balanced trees, binary search, dynamic balancing 3.73 3.74 4.34 5.25 5.31 CA780304 JB March 28, 1978 1:12 PM 3009 4 3009 3042 4 3009 3065 4 3009 3096 4 3009 3163 4 3009 2839 5 3009 3009 5 3009 3009 5 3009 3009 5 3009 3096 5 3009 3163 5 3009 2839 6 3009 2839 6 3009 2889 6 3009 2889 6 3009 3009 6 3009 3009 6 3009 3065 6 3009 3096 6 3009