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