Access Restriction

Author Ottmann, Th. ♦ Six, H. W. ♦ Wood, D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Dictionary problem ♦ Avl trees ♦ Insertion and deletion algorithms ♦ Search trees ♦ Brother trees ♦ One-sided height-balanced trees ♦ Right-balanced trees
Abstract Insertion and deletion algorithms 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 to one-sided height-balanced 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.
Description Affiliation: Univ. of Karlsruhe, West Germany (Ottmann, Th.; Six, H. W.) || McMaster Univ., Hamilton, Ont., Canada (Wood, D.)
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 21
Issue Number 9
Page Count 8
Starting Page 769
Ending Page 776

Open content in new tab

   Open content in new tab
Source: ACM Digital Library