Right Brother Trees

Insertion and deletion are provided for the
class of right (or one-sided) brother trees which 
have O (log n) performance.  The importance of these
results stems from the close relationship of right 
brother trees which have an insertion algorithm operating
in O (log2 n).  Further, although both insertion 
and deletion can be  carried out in O (log n) time for
right brother trees, it appears that the insertion 
algorithm is inherently much more difficult than the
deletion algorithm-the reverse of what one usually 
obtains.  

CACM September, 1978

Ottmann, T.
Six, H.
Wood, D.

Dictionary problem, search trees, AVL trees, brother
trees, right-balanced trees,one-sided height-balanced 
trees, insertion and deletion algorithms

3.73 3.74 5.31

CA780807 DH January 29, 1979 7:08 PM

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