Access Restriction

Author Räihä, Kari-Jouko ♦ Zweben, Stuart H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Height-balanced trees ♦ Search trees ♦ One-sided height-balanced trees ♦ Binary trees ♦ Insertion
Abstract 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 previously known insertion algorithms of Hirschberg and Kosaraju, which require time O(log2n). 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.
Description Affiliation: Univ. of Helsinki, Helsinki, Finland (Räihä, Kari-Jouko) || Ohio State Univ., Columbus (Zweben, Stuart H.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 22
Issue Number 9
Page Count 5
Starting Page 508
Ending Page 512

Open content in new tab

   Open content in new tab
Source: ACM Digital Library