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