An Optimal Method for Deletion in One-Sided Height-Balanced Trees

A one-sided height-balanced tree is a binary
tree in which every node's right subtree has a 
height which is equal to or exactly one greater than the
height of its left subtree.  It has an advantage 
over the more general AVL tree in that only one bit
of balancing information is required (two bits are 
required for the ACL tree).  It is shown that deletion of
an arbitrary node of such a tree can be accomplished 
in O(logn) operations, where n is the number of nodes
in the tree.  Moreover the method is optimal in 
the sense that its complexity cannot be reduced in order
of magnitude.  This result, coupled with earlier 
results by Hirschberg, indicates that, of the three basic
problems of insertion, deletion, and retrieval, 
only insertion is adversely affected by this modification of an AVL tree.   

CACM June, 1978

Zweben, S.
McDonald, M.

Balanced, binary, search, trees

3.73 3.74 4.34 5.25 5.31

CA780601 DH February 26, 1979  12:48 PM

2839	4	3096
3009	4	3096
3042	4	3096
3042	4	3096
3065	4	3096
3096	4	3096
3096	4	3096
3096	4	3096
3163	4	3096
3163	4	3096
3163	4	3096
2839	5	3096
2889	5	3096
3009	5	3096
3065	5	3096
3096	5	3096
3096	5	3096
3096	5	3096
3163	5	3096
2839	6	3096
2839	6	3096
2889	6	3096
3009	6	3096
3065	6	3096
3096	6	3096
3096	6	3096