An Optimal Insertion Algorithm for One-Sided
Height-Balanced BInary Search Trees

An algorithm for inserting an element into a one-sided height-balanced
(OSHB) binary search tree is presented.  The algorithm operates in time 
O(log n), where n is the number of nodes in
the tree.  This represents an improvement over the best previous
ly known insertion algorithms of Hirschberg and Kosaraju, which require
time O(log 2n).  Moreover, the O(log n) complexity is optimal. Earlier 
results have shown that deletion in such a structure can
also be performed in O(log n) time.  Thus the result of this paper
gives a negative answer to the question of whether such trees should
be the first examples of their kind, where deletion has a smaller time 
complexity than insertion.  Furthermore, it can now be concluded
that insertion, deletion, and retrieval in OSHB trees can
be performed in the same time as the corresponding operations for
the more general AVL trees, to within a constant factor.  However,
the insertion and deletion algorithms for OSHB trees appear much
more complicated than the corresponding algorithms for AVL trees.

CACM September, 1979

Raiha,K.
Zweben, S.

Insertion, one-sided height-balanced trees, height-balanced
trees, binary trees, search trees.

3.73. 3.74 4.34 5.25 5.31

CA790904 DB January 14, 1980  11:47 AM

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